Law of trichotomy :For any m, n N, either m n or m n or n m.Well ordering principle (WOP) :Every non-empty subset of N has a least member. That is, if S is any non-empty subset of N, then there is an element S such that for all S.Divisibility :Let a and b be any two integers with a 0. Then we say that ‘a divides b’ if there is an integer c such that b ac and we write this as a | b.In case ‘a does not divide b’ we write this as a b.Properties of divisibility :Every non-zero integer a is divisor of zero. Given a Z, a 0 it is clear that 0 a 0. by definition of divisibility a|0. 1, - 1, a, - a are divisors of every non-zero integer a.We can write a a 1 and a (- a) (- 1).Thus every non-zero integer ‘a’ has four divisors viz. 1, a. These are called the improper divisors of ‘a’.Any divisors other than these is called a proper divisor of a.If a, b are non-zero integers such that a | b then .Since a | b b a c where c Z = = Alsob 0 c 0 1Hence = i.e. Let a 0, b 0 be in Z. If a | b and b | a then a b.a b Z such that b aand b | a y Z such that a by ……….. ⊛a (a) ya ay1 yas and y are integers, y 1 or y - 1. a b from .. ⊛ If a | b then a | bc for any integer c.a | b m Z such that b amMultiply both sides by c Z we getbc amc as m, c Z mc Z a (mc) a | bc by definition of divisibility.If a | b and a | c then a | ( for any integers and y.a | b m Z S t b am⊛a | c n Z S t c anConsider From * as m, n, and y Z Z a | by definition of divisibility.If a | b and c | d then ac | bda | b m Z S t b amc | d n Z S t d cnConsider bd amcn acmnAs m, n Z mn Z ac | bd by definition of divisibility.If a | b and b | c then a | ca | b m Z S t b amb | c n Z S t c bnConsider c bn amnas m, n Z mn Z a | c by definition of divisibility.If c 0 integer and a | b then ac | bca | b m Z S t b amMultiply both sides by c Zbc amc ac (m) ac | bc by definition of divisibility.Similarly if ac | bc then a | b.Division Algorithm : If a and b are any two integers with a 0 then there exist unique integers q and r such thata = aq + r, where a r .Case (i) :We first consider the case a 0.Let S { Z 0, Z }Since a 0 a 1 we have a 1as 0 adding b to both sidesb + a b + 0b + a 0b – (– ) a 0b – a (– ) 0 b – a (– ) S S in non-empty subset of non-negative integer. By WOP, S has a least element say r. Then r S and r y for all y SBut r S r b – aq for some q Z b aq + r 0 r as r SNow, suppose r a, then r – a 0.But r – a (b – aq) – a b – aq – a b – a (q + 1). Thus r – a 0and is of the form of the elements in S. Therefore r – a S.But r – a r as a 0 aBy our assumption r is the least element of S which is contradiction to the choice of a. Therefore r a.Thus, we have a, r Z S t b aq + r 0 r ( a)Case (ii) :If a 0 then 0, So replacing ‘a’ by we can apply case (i) to b and . We have from (i) aboveb q + r 0 r For q , r Z Now – a, 0So we get b (– a) q + r a (– q ) + r Put – q qThus in any case we have q, r Z S t b aq + r 0 r .Uniqueness of q and r :Suppose we have two pairs on integers q and r; q and r such that b aq + r where a r and b aq + r where a r On subtracting, we get b – b 0 aq + r – aq – r b – b 0 aq – qq + r – r 0 a (q – q) + (r – r) 0 – a (q – q) + (r – r) 0 a (q – q) (r – r) a (q – q) ………….. * with a (r – r) with But this is possible only when r – r 0i.e. r rFrom ⊛ a (q – q) 0 q – q 0 q qHence the uniqueness of q and r.The Greatest Common Divisor :Common Divisor :Let a and b be any two integers not both zero. An integer d is said to be common divisor of a and b if d|a and d|b.G.C.D. :Let a and b be two non-zero integers. An integer d is said to be the greatest common divisor of a and b ifd a and d b andif c Z such that c a and c b then c d.If d is g.c.d. of a and b, then – d is also g.c.d.g.c.d. of a and b is denoted by (a, b) i.e. if d is g.c.d. of a and b, d (a, b)The term Highest Common Factor (H.C.F.) is also used for g.c.d.GCD theorem :Any two non-zero integers a and b have a unique (positive) g.c.d., d (a, b) and can be expressed in the form d (a, b) ma + nb for some m, n Z.Proof :Let S { , y Z and 0 }Since a and b are non-zero,and a + b b 0As we consider a and y b we get .Hence S is non-empty subset of N.So by WOP, S has a least element, say d. i.e. d S and d Z for all Z S.Also d S d ma + nb for some m, n Z.Now we prove that d is common divisor of a and b.Applying division algorithm to a and b there exists q and r in Z such thata dq + r where 0 r dIf r 0 r a – dq with 0 r d a – (ma + nb) q a – maq – nbq a (1 – mq) – nq b (1 – mq) a + (– mq) b 0 r dConsider 1 – mq y – nqSo r can be written as r r SBut this is contradiction to the choice of d as r d, Hence r 0 a = dq + r = dq d aSimilarly applying division algorithm to d and d we get d b.Thus d is common divisor of a and b.Now we want to show that d is g.c.d. For that consider c is common divisor of a and b i.e. c a a ck1 k1 Zand c b b ck2 k2 ZWe know that d ma + nb m (ck1) + n (ck2) c (mk1 + nk2) mk1 + nk2 Zwhich show that c dThus d is g.c.d. of a and b.Now uniqueness of d : Suppose d is another g.c.d. of a and b. d a and d b as d is g.c.d. and d is common divisor.Suppose d is another g.c.d. if a and b, d is cd of a and b. d a and d b as d is g.c.d. d dSimilarly d is g.c.d. of a and b d a , d bHence d d as d is g.c.d. of a and bThus d d and d d , Hence d dBut both d and d are positive. d d.Euclidean Algorithm (E.A) :The process of finding g.c.d. of a given two integers by applying D.A. successively, is known as Euclidean Algorithm.Let a and b be two non-zero integers. Applying D.A. to a and b unique integers q1 and r1 such thatb aq1 + r1 where 0 r1 …….. *If r1 0 then b aq1 a | b (a, b) If r1 0 i.e. r1 0 from * cd of a and r1 is also divisor of b. Hence cd of a and b (a, r1) | (a, b) Alsob aq1 + r1 r1 b – aq1 This shows that cd of a and b is also divisor of r1. Hence cd of r and a (a, b) | (a1 r1)Therefore (a, b) (a1 r1)Applying D.A. to a and r1 unique q2 and r2 such thata r1q2 + r2 where 0 r2 r1By similar argument as applied to a, b and r1 we apply to a, r1, r2 we get(r1 r2) (a, r1) (a, b)This process of finding q1, r1 ends in finite steps. Suppose this process ends at nth step i.e. say rn+1 0r1 r2 q3 + r3 0 r3 r2 r2 r3 q4 + r4 0 r4 r3:rn-2 rn-1 qn + rn 0 rn rn-1rn-1 rn qn+1 + 0As argued before we havern (rn-1, rn) (rn-2, rn-1) …… .. (r1, r2) (b, r1) (a, b)Thus rn (a, b) the g.c.d. of a and b.Relative :Two integers a and b are said to be relatively prime, if (a, b) 1The fact that (a, b) 1 is sometimes expressed by saying that a and b are coprime or by saying that a is prime to b.Least common multiple :Let a and b be non-zero integers. Then the least common multiple (L.C.M.) of a and b is defined to be a positive integer d such that i) a | d and b | d and ii) If a | c and b | c then d | cWe write L.C.M. of a and b as [a, b].Ex. [6, 10] 30If c | ab and (b, c) 1 then prove that c | a 0.5Since c | ab k Z St ab ckAlso (b, c) 1 By g.c.d. theorem m, n Z such that bm + cn 1Multiplying by a we getabm + acm ackm + acm ac (km + an) ac | a where km + an Z 0.6If (a, b) d then 1Let (a, b) d d | a and d | ba dk1 and b dk2 where k1, k2 ZNow since d (a, b)By g.c.d. theorem , y Z St d dk1 + dk2y d d (k1 + k2y) 1 k1 + k2y (k1, k2) 1As a dk1 k1 and b dk2 k2 which gives 1If a | m, b | m and (a, b) 1 then ab | mBy data (a, b) 1 , y Z such that ma + mby mNow as a | m m aq1And b | m m bq2 q1 q2 Z bq2a + aq1by m ab (q2) + ab (q1y) m ab (q2 + q1y) m ab | mFor any Z , (a, b) (a, b + a)Let (a, b) d and (a, b + a) eSince d (a, b) d | a and d | b d | a and d | b + a d | (a, b + a) d | eNext since e (a, b + a)We have e | a , e | b + a a ek1 and b + a ek2 k1, k2 Z a ek1 and b + (ek1) ek2 a ek1 and b e (k2 – k1) k2 – k1 Z e | a and e | b e | (a, b) i.e. e | dAs d | e and e | d e di.e. (a, b) (a, b + a)Show that 4999 and 1109 are relatively prime. Also find integer and y such that4999 + 1109y (4999, 1109) We find (4999, 1109) by Euclidean algorithm as follows 4999 1109 x 4 + 563 1109 563 x 1 + 546 563 546 x 1 + 17 546 17 x 32 + 2 17 2 x 8 + 1 2 1 x 2 + 0 (4999, 1109) 1g.c.d. of 4999 and 1109 is 1.Now by g.c.d. theorem we have 1 17 – 2 x 8 17 – (546 – 17 x 32) x 8 17 x 257 – 546 x 8 (563 – 546) x 257 – 546 x 8 563 x 257 – 546 x 265 563 x 257 – (1109 – 563) x 265 (4999 – 1109 x 4) x 522 – 1109 x 265 (4999 x 522 – 1109 x 2353 522 and y – 2353Find g.c.d. of 3997 and 2947 such that g.c.d. 3997 + 2947 yAns : – 97 and y 118 g.c.d. 7Find g.c.d. of 121 and 385 such that g.c.d m (121) + n (385)Ans : m 16 and n – 5 g.c.d. 11Find (243, 198) and express it in the form (243, 198) m (243) + n (198)Ans : m 243 and n – 11 g.c.d. 9Find g.c.d. of (819, 658) and express it in the form m (819) + n (658)Ans : m 45 and n – 56 g.c.d. 7Show that no two integers exists satisfying + y 200 and (, y) 7Suppose there exists two integers satisfying + y 200 and (, y) 7Since (, y) 7 7 | and 7 | y 7m and y 7n m, n ZAlso + y 200 7m + 7n 200 7 (m +n) 200 m + n But since m, n Z m + n ZHere m + n Z.Hence our assumption i.e. , y Z such that + y 200 and (, y) 7 is wrong. There does not exists two integers satisfying + y 200 and (, y) 7Show that we can find infinitely many pairs of and y satisfying + y 100 and (, y) 5.Let + y 100 and (, y) 5Since (, y) 5 5 | and 5 | y 5m and y 5n m, n ZNow since + y 100 5m + 5n 100 m + n 20 m 20 – n m, n ZNow we find infinitely many values of m and n such that m 20 – n.Primes :Prime integer :A non-zero integer P ( 1) is called prime if it has no divisors other than 1 and P.Composite integer :A non-zero integer ‘a’ is called composite if ‘a’ has a proper divisor i.e. ‘a’ can be written asa bc where 1 .Theorem : If P is a prime and P a then (P, a) 1.Let d (P, a) then d | P and d | aBut P is prime, therefore d 1 or d PIf we take d P then from d | a we get P | aBut P x a d 1Theorem : Euclid’s lemma :If P is prime and a, b are integers such that P | ab then P | a or P | b.P | ab and P is prime, then P | a or P aIf P | a then there is nothing to prove.Let P x a then by above theorem (P, a) 1Hence by g.c.d. theorem we have 1 p + qy, y Z ………………….. (1)Now P | ab q Z St ab pqMultiplying eqn (1) by b we get b pb + qby pb + pqy p (b + qy) b + qy Z P| bCoro : If P is a prime and P | a1 a2 …………… an then P | aiFor at least one i 1 i n.Unique Factorization theorem :Every positive integer a 1 can be expressed as a product of a finite number of positive primes not necessarily distinct. Further this expression is unique apart from the order in which the factor appears.We may write ‘a’ as a ….. ………. *where P1, P2, ….. Pr are all distinct primes and i 0 are integers.For any integer ‘a’ the expression * is called “Canonical form”.Ex. 6750 2 x 33 x 53 x 70Theorem : The number of primes is infinite.Suppose there are only a finite number of primes say P1, P2, ….. PrNow consider the integer a 1 + P1 P2 ……….. PrIf Pi | a ; 1 i r and Pi | P1 P2 ………. Prthen Pi | a – P1 P2 ………. Pr Pi | 1 which is contradiction.Therefore Pi x a. Thus P1, P2, …… Pr cannot divide a.Hence any prime divisor P of a is distinct from P1, P2, …… Pr The number of primes is infinite.Congruences :Let m Z , m 0 and a, b Z then a is said to be congruent to b modulo m if m | a – b andDenoted by a b (modm)For ex. 17 5 (mod 4) Since 4 | 17 – 5Theorem : Let a and b be any two integers and n N. Then a b (mod n) if a and b leave the sameRemainder when divided by n.Suppose a b (mod n). Then we have to show that a and b leave the same remainder when divided by n.Now a b (mod n) a – b nk , k Z a b + nk …………………. (1)Applying division algorithm to b and n, there exist q and r such that b nq + r 0 r n …………….. (2)i.e. r is the remainder when b is divided by n.From (1) and (2) we have a (nq + r) + nk n (q + k) + r 0 r nwhich shows that r is also the remainder when a is divided by n.Conversely, suppose a and b leave the same remainder when divided by n, that is by division algorithm, we have a nq + r and b nq + r 0 r n and r, q, q ZThen a – b (nq + r) – (nq + r) nq – nq n (q – q) n | a – b a b (mod n)Let n 0 be fixed integer and a, b, c any three integers, then following propertiesa a (mod n) reflexiveSince we have n | a – a 0 i.e. a – a 0n a a (mod n) a b (mod n) b a (mod n) symmetrica b (mod n) a – b kn k Z b – a (– k) n – k Z b a (mod n) a b (mod n) and b c (mod n) a c (mod n) transitive a – b k1n and b – c k2n k1, k2 Z (a – b) + (b – c) k1n + k2n a – c (k1 + k2) n a c (mod n) k1 + k2 Za b (mod n) and c d (mod n) a + c b + d (mod n) , ac bd (mod n) a – b k1n , c – d k2n k1, k2 Z a – b + c – d k1n + k2n n (k1 + k2) (a + c) – (b + d) (k1 + k2) n a + c (b + d) mod nAlso a b + k1n , c d + k2nac (b + k1n) (d + k2n) bd + (bk2 + dk1 + k1k2n) n bk2 + dk2 + k1k2n Z ac bd (mod n)Also d2 (y, m) d2 | y and d2 | m d2 | mk1 d2 | y + mk1 d2 | d2 | and d2 | m d2 | (x, m) d2 | d1 ………………………… (2)From (1) and (2) d1 d2 But d1, d2 are g.c.d. and d1, d2 0 d1 d2 i.e.(x, m) (y, m)If a b (mod n) and c d (mod n) a + cy b + dy (mod n) a – b k1n , c – d k2n k1, k2 ZWe have (a + cy) – (b + dy) (a – b) + (cy – dy) (a – b) + (c – d) y k1n + k2ny n (k1 + k2y)Hence (a + cy) (b + dy) (mod n)If a b (mod m) and d | m, d 0 then a b (mod d)Given that a b (mod m) m | a – bAlso d | m d | a – b a b (mod d)If a ay (mod m) and (a, m) 1 then y (mod m)Given that a ay (mod m) m | a – ay m | a ( – y)But (a, m) 1 m | ( – y) y (mod m)If y (mod m) then (, m) (y, m)Let d1 (, m) and d2 (y, m)By data y (mod m) m | – y – y mk1 , k1 Z d1 (, m) d1 | and d1 | m d1 | mk1 d1 | – mk1 d1 | y d1 | y and d1 | m d1 | (y, m) d1 | d2 ………………… (1)Residue classes :For a Z, the set { Z | a (mod n) } is called ‘Congruent class of a modulo n’ or ‘residue class of a mod n’.We have { Z | a (mod n) } { Z | a + kn , k Z } { ….. , a – 2n, a – n, a, a + n, a + 2n, ….. }At a 3, n 5 { ……. – , – , , , } c a (mod m) iff There are exactly n distinct residue classes mod n namely , , ……. .Let a Z applying the division algorithm to a and n we can write, a nq + r 0 r n a – r nq so that n | a – r Hence a r (mod n) and 0 r nHence modulo n, the residue class of every integer is one of the classes , , , ……….., ().Next we want to show that , , ……. are all distinct.Let, y Z and 0 , y n – 1 and y then y (mod n) n | – y 0 yThus , , ……….., () are all distinct, proving that there are precisely n distinct residue classes modulo n.Prime residue class :If a is any integer such that 0 a n and if (a, n) 1 then is called a prime residue class in Zn.The set of all prime { , , , }Euler’s function :Given n N , n 1. The number of prime residue classes in Zn is denoted by the function (n). This functionis called Euler’s - function. (n) number of elements in . (n) | { 1, 5 } | 2Binary Operations :Let R denote a set. A mapping : R x R R is called a binary operation on R.Addition and Multiplication in Zn :Let n N. Then for any , Zn we define sum of the classes and denoted by + as the class i.e. + Similarly we define the multiplication of and denoted by as the class i.e. . For , Z7 we have + Since in Z7 , and x Since in Z7.Composition table for addition and multiplication Z5 :+5X501234000001234001234234010241334012031424012304321Properties of addition and multiplication in Zn :Let , , ZnAddition in Zn is commutative i.e. + + .Addition in Zn is associative i.e. ( + ) + + ( + ).0 is identity element in Zn with respect to addition. i.e. + + ZnFor Zn there is in Zn such that + () () + Multiplication in Zn is commutative i.e. , Zn.Multiplication in Zn is associative i.e. ( ) ( ) . Zn is an identity element w.r.t. multiplication in Zn.Multiplication is distributes over addition in Zn i.e. ( + ) ( ) + ( ).Show that is irrational for any prime P.On contrary, suppose is rational. There exists two integers a and b, b 0 such that and g.c.d. of (a, b) is 1.Now since P P P| P|a c Z such that a P c From P we have P ( P P P P| P|b We get P|a and P|b P|(a, b) (a, b) 1 ( P is prime)Contradiction to the fact that g.c.d. of (a, b) 1 Our assumption that is rational is wrong. Hence is irrational for any prime P.Fermat’s theorem :Let P denote a prime. If Pa then 1 (mod P) a ZConsider the first P – 1 multiplies of a viz. a, 2a, 3a, …………… (P – 1) a ………………. (1)No two of these numbers are congruent modulo P.For ifa ya (mod P) 1 < y P – 1 then P | (a – ya) or P|( – y) aHence as prime P does not divide a, we get P|( – y). But this is impossible since 0 < | – y| < P.Hence no two of the numbers in eqn. (1) are congruent modulo P.Therefore all the numbers a, 2a, 3a, ……….. (P – 1) a belongs to distinct residue classes modulo P.This means a, 2a, 3a, ……….. (P – 1) a are congruent modulo P to 1, 2, 3, ……… P – 1 in some order. Therefore we have a x 2a x 3a x ……. x (P – 1) a 1 2 3 ………. (P – 1) (mod P) x (1 x 2 x 3 x ……… x (P – 1) 1 2 3 …… (P – 1) (mod P) x (P – 1) ! (P – 1) ! (mod P) 1 (mod P) Since ((P – 1) !, P) = 1.Corollary : Euler’s theoremIf P is a prime and a is any integer then a (mod P)Find the remainder when 437 + 82 is divided by 7.Since 7 is prime and 7 4 by Fermat’s theoremWe have 47–1 = 46 1 (mod 7)Since 437 = 436 4 = (46)6 4We have (46)6 16 (mod 7) (46)6 4 1 4 (mod 7) 437 4 (mod 7)Also 82 5 (mod 7)Hence 437 + 82 4 + 5 (mod 7) 9 (mod 7) 2 (mod 7)Hence remainder is 2.Find the remainder when 7200 + 11800 is divided by 101.Since 101 is prime and 101 7 also 101 11 By Fermat’s theorem 7101–1 1 (mod 101)i.e. 7100 1 (mod 101) (7100)2 12 (mod 101) 7200 1 (mod 101) ………………… (1)Also 11101–1 1 (mod 101)i.e. 11100 1 (mod 101) (11100)8 18 (mod 101) 11800 1 (mod 101) ………………… (2)From (1) and (2) we have 7200 + 11800 1 + 1 (mod 101) 2 (mod 101)Hence the remainder is 2.Find the remainder when 111333 is divided by 7.Here 7 is a prime and 7 111. By Fermat’s theorem, we have 1117–1 = 1116 1 (mod 7) 111333 = 1155x6+3 (1116)55 (111)3 (mod 7) 1 (6 – 1)3 (mod 7) – 1 (mod 7) 6 (mod 7)Hence remainder is 6.