Mathematics

Example: Using Euclids division algorithm, find the H.C.F. (Highest Common Factor)  
(i) 135 and 225 (ii) 196 and 38220 and (iii) 867 and 255

Solution:
(i) Starting with the larger number i.e., 225, we get:
225 = 135 × 1 + 90
Now taking divisor 135 and remainder 90, we get 135 = 90 × 1 + 45
Further taking divisor 90 and remainder 45, we get 90 = 45 × 2 + 0
∴ Required H.C.F. (Highest Common Factor) is equal to 45 (Answer)

(ii) Starting with larger number 38220, we get:
38220 = 196 × 195 + 0
Since, the remainder is 0
↠ Required H.C.F. (Highest Common Factor) is equal to 196 (Answer.)

(iii) Given number are 867 and 255
↠ 867 = 255 × 3 + 102 (Step-1)
255 = 102 × 2 + 51 (Step-2)
102 = 51 × 2 + 0 (Step-3)
↠ Highest Common Factor (H.C.F.) = 51 (Ans.)

Example: Show that every positive integer is of the form 2q and that every positive odd integer is of the from 2q + 1, where q is some integer.

Solution. According to Euclids division lemma, if a and b are two positive integers such that a is greater than b; then these two integers can be expressed as a = bq + r; where 0 ≤ r < b
Now consider
b = 2; then a = bq + r will reduce to a = 2q + r; where 0 ≤ r < 2,
i.e., r = 0 or r = 1
If r = 0, a = 2q + r ↠ a = 2q
i.e., a is even
and, if r = 1, a = 2q + r ↠ a = 2q + 1
i.e., a is add;
as if the integer is not even; it will be odd.
Since, a is taken to be any positive integer so it is applicable to the every positive integer that when it can be expressed as a = 2q. 
∴ a is even and when it can expressed as a = 2q + 1; a is odd. Hence the required result.

Example: Show that any positive odd integer is of the form 4q + 1 or 4q + 3, where q is some integer.

Solution: Let a is b be two positive integers in which a is greater than b. According to Euclids division algorithm; a and b can be expressed as a = bq + r, where q is quotient and r is remainder and 0 ≤ r < b.
Taking b = 4, we get: a = 4q + r, where 0 ≤ r < 4 i.e., r = 0, 1, 2 or 3
r = 0 ↠ a = 4q, which is divisible by 2 and so is even.
r = 1 ↠ a = 4q + 1, which is not divisible by 2 and so is odd.
r = 2 ↠ q = 4q + 2, which is divisible by 2 and so is even.
and r = 3 ↠ q = 4q + 3, which is not divisible by 2 and so is odd.
∴ Any positive odd integer is of the form 4q + 1 or 4q + 3; where q is an integer.
Hence the required result.

Example: Show that one and only one out of n; n + 2 or n + 4 is divisible by 3, where n is any positive integer.

Solution: Consider any two positive integers a and b such that a is greater than b, then according to Euclids division algorithm:
a = bq + r; where q and r are positive integers and 0 ≤ r < b
Let a = n and b = 3, then
a = bq + r ↠ n = 3q + r; where 0 £ r < 3.
r = 0 ↠ n = 3q + 0 = 3q
r = 1 ↠ n = 3q + 1 and r = 2 ↠ n = 3q + 2
If n = 3q; n is divisible by 3
If n = 3q + 1; then n + 2 = 3q + 1 + 2
= 3q + 3; which is divisible by 3
↠ n + 2 is divisible by 3
If n = 3q + 2; then n + 4 = 3q + 2 + 4
= 3q + 6; which is divisible by 3
↠ n + 4 is divisible by 3
Hence, if n is any positive integer, then one and only one out of n, n + 2 or n + 4 is divisible by 3.
Hence the required result.