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.

SHOW CHAPTERS