Euclid's Division Lemma (Divisibility, number system)

Euclid's Division Lemma

1. Real Numbers

> Euclid’s Division Lemma

Maths Learning Centre,

Jalandhar

2. Euclid’s Division Lemma
For any two given positive integers a and b,
there exist unique whole numbers q and r such that

a=bq+r, where 0<r<b 0,1,2..b-1

is

a-dividend -117 b - divisor 4 OS
q-quotient -29 r-remainder -1

117 = (4x29) +1 1<4

À

Dividend = (divisor x quotient) + remainder

Lemma is a proven statement
used for proving another
statement.

3. A number when divided by 73 gives 34 as quotient and 23 as remainder.
Find the number.

divisor = 73 quotient = 34 remainder = 23.

dividend = (divisor xquotient)+ remainder

Py
= (73 x 34) + 23 = (2482 + 23) = 2505. (oe

4. Let n be an arbitrary positive integer.

On dividing n by 2,
m- quotient r-remainder.

n=2m+r,where0 <r<2.

» 2m r=0

* 2m+1 r=1

Show that every positive even integer is of the form 2m and that every
positive odd integer is of the form (2m + 1) , where m is some integer.

Casel: Whenn = 2m. nis even. (ato

Case Il: Whenn = 2m +1. nis odd. Ni

5. Show that any positive integer is of the form 3m or (3m + 1) or (3m + 2)

for some integer m.
Let n be an arbitrary positive integer.
On dividing n by 3,
m- quotient r - remainder.
n=3m+r,where0<r<3 r=0, 1, 2

(rte

(EE n=3m or (3m+1) or (3m+2)

O= bg+2

6. Show that any positive odd integer is of the form (4m + 1) or (Am + 3)
for some integer m.

Let n be an arbitrary odd positive integer.

On dividing n by 4, m - quotient r - remainder.

Um =2 (an)
n=4m+r, where 0 <r<4 Ps 2\ um
r=0 4, 2 or 3 (ane Um+2 = (2)(2m+1

GERD 2) 4mt2

n = 4m or (4m + 1) or (4m + 2) or (4m +3).
4m and (4m + 2) are even son + 4m and n + (4m +2).

n= (4m + 1) or (4m + 3)

7. If n is an odd integer then show that n? — 1 is divisible by 8.
Every odd integer is of the form 4q + 1 or 4q + 3 for some integer q.
Case | When n = 4q + 1. WW

n?-1=(4q +1)? -1=16q? +8q+1-1

= 164? + 8q = 8(q + 2q?) which is divisible by 8.
rag
Case Il When n = 4q + 3. 82 9? 43 )

n? —1= (4 +3)? -1=16q? +24q+9-1
= 16q? + 24q +8 ee E _3q sE D which is divisible by 8.

uy + HN