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.

If you want to give information about online courses to other students, then share it with more and more on Facebook, Twitter, Google Plus. The more the shares will be, the more students will benefit. The share buttons are given below for your convenience.

SHOW CHAPTERS