Transcription of Congruences and Modular Arithmetic
1 Congruences and Modular ArithmeticRyan C. DailedaTrinity UniversityNumber TheoryDailedaCongruencesIntroductionModu lar Arithmetic is the Arithmetic of remainders. The somewhat surprising fact is that Modular Arithmetic obeysmost of the same laws that ordinary Arithmetic explains, for instance, homework exercise on theassociativity of will later see that because of this the set of equivalence classesunder congruence moduloncan be given the structure of Nanda,b Z. We say thata is congruent to b modulon, denoteda b(modn), providedn|a have: 7 22 (mod 5), 4 3 (mod 7), 19 119(mod 100), 37 1 (mod 4).
2 For anya,b Z:a b(mod 1).Notice that:a b(modn) a b=nk a=b+nkfor somek first result concerning Congruences should be familiar fromIntro to 1 Let n N. Then congruence modulo n is an equivalence (Sketch).Leta,b,c :Sincen|0,a a(modn).Symmetry:Ifn|a b, thenn| (a b) =b a. Soa b(modn) impliesb a(modn).Transitivity:Ifn|a bandn|b c, thenn|(a b) + (b c) =a c. Thusa b(modn) andb c(modn) together imply thata c(modn).DailedaCongruencesRecall that every equivalence relation on a setS partitionsthat setinto disjoint subsets (theequivalence classes).Givenn N, an equivalence class under congruence moduloniscalled acongruence will denote the congruence class ofa Zbyaora+nZ(whichever is more convenient):a=a+nZ={b Z|a b(modn)}={a+nk|k Z}.
3 We will denote the collection of congruence classes byZ/nZ:Z/nZ={a+nZ|a Z}.DailedaCongruencesBefore we give more examples, it will be convenient to give acomplete description 2 Let n Nand a,b Z. Then a b(modn)iff a and b leave thesame remainder when divided by n. In particular, every a iscongruent to its remainder when divided by n, and no two distinctremainders are congruent modulo n. Therefore the (distinct)elements ofZ/nZare0 +nZ,1 +nZ,2 +nZ, .. ,(n 1) + have the following immediate 0 (modn) iffn|a. Z/nZ = of Theorem +r1,b=q2n+r2, with0 ri< b= (q1n+r1) (q2n+r2) = (q1 q2)n+ (r1 r2).
4 Ifa b(modn), thenn|(a b) and we find thatn|(a b) (q1 q2)n=r1 |r1 r2|<n, so this can only occur ifr1 r2= 0 orr1= , ifr1=r2, thena b= (q1 q2)n, so thatn|a b,anda b(modn).The remaining statements follow at 2, the only remainders are 0 and 1. According toTheorem 2, we find thata b(mod 2) iffaandbare botheven or both odd. In this case we sayaandbhave the integer is congruent to either 0, 1 or 2 modulo 3 (andthese options are mutually exclusive).Every integer is congruent to (exactly) one of the decimaldigits modulo 10. In fact, since every integer whose decimalexpansion ends in 0 is divisible by 10, every integer iscongruent to itsfinaldigit modulo N.
5 Theorem 2 tells us that there are exactlyncongruenceclasses set containing exactly one integer from each congruence class iscalled acomplete system of residues modulo set{0,1,2, .. ,n 1}of remainders is a completesystem of residues modulon, by Theorem set{0, 1, 2}is a complete system of residuesmodulo generally, the set{a Z:|a| n/2} \ { n/2}is acomplete system of residues ArithmeticOne of the facts that makes Congruences so useful in arithmeticisthat they respect the operations of addition and 3 Let n Nand a,b,c,d Z. If a b(modn)andc d(modn), then:1a+c b+d(modn);2ac bd(modn).
6 B=nkandc d=n withk, Z. Then(a+c) (b+d) = (a b) + (c d) =nk+n =n(k+ ),so thata+c b+d(modn).DailedaCongruencesThe proof that multiplication is respected is only slightly lessstraightforward:ac bd=ac ad+ad bd=a(c d) + (a b)d=an +nkd=n(a +kd),so thatac bd(modn).Corollary 1 Let n Nand a,b Z. If a b(modn), thenak bk(modn)for all k part 2 of Theorem 3 and induct 1 Prove that ifa Z, thena2 0,1 (mod 4). know thatais equivalent to one of 0, 1, 2 or 3modulo 4, so we simply check each case:a 0 (mod 4) a2 02 0 (mod 4),a 1 (mod 4) a2 12 1 (mod 4),a 2 (mod 4) a2 22 0 (mod 4),a 3 (mod 4) a2 32 1 (mod 4).
7 DailedaCongruencesExample 2 Prove that 53103+ 10353is divisible by that53 14 25 (mod 39),103 25 (mod 39),so that53103+ 10353 ( 25)103+ 2553 5206+ 5106(mod 39).Now we compute the first few powers of 5 modulo 39:52 25 (mod 39),53= 125 8 (mod 39),54 5 8 1 (mod 39).DailedaCongruencesNow divide the exponents 206 and 106 by 4: 5206+ 5106 54 51+2+ 54 26+2(mod 39) (54)5152+ (54)2652(mod 39) 151 25 + 126 25 (mod 39) 25 + 25 0 (mod 39). computing the remainder whenakis divided byn,especially by hand, it is usually best to:1 Replaceaby its remainder when divided find the remainders whena2,a3,a4.
8 Are dividedbyn, by multiplying the preceding remainder byaat of Modular Arithmetic ensure that this process yields thecorrect in Modular ArithmeticBecauseZis a domain, we have the cancellation lawab=acanda6= 0 b= lawfailsfor Modular Arithmetic . For instance, we have2 3 2 8 (mod 10) and 26 0 (mod 10),yet 36 8 (mod 10).The problem is that the common factor 2 and the modulus 10 arenot relatively we take the GCD into account, we get valid cancellation laws formodular 1 Let n,k Nand a,b Z. Thena b(modn) ak bk(modnk). b(modn), thena b=n for some through bykyieldsak bk=nk , so thatak bk(modnk).
9 Conversely, ifak bk(modnk), thenak bk=nk for some is,k(a b) =kn . Sincek6= 0, it can be cancelled, yieldinga b=n , and hencea b(modn).DailedaCongruencesEuclid s lemma yields the following useful 2 Let n Nand a,b,c Z. If(c,n) = 1, thenac bc(modn) a b(modn). bc(modn), thenn|ac bc= (a b) (c,n) = 1, Euclid s lemma implies thatn|a b, which meansa b(modn).The reverse implication follows immediately from part 2 ofTheorem our lemmas together we obtain:Theorem 4 Let n Nand a,b,c Z. Thenac bc(modn) a b(modn/(c,n)). we writec=c (c,n) andn=n (c,n), then we knowthat (c ,n ) = lemmas 1 and 2 we haveac bc(modn) ac (c,n) bc (c,n) (modn (c,n)) ac bc (modn ) a b(modn ).
10 Sincen =n/(c,n), this completes the can cancel a common factor in an arbitrary congruenceprovided we divide the modulus by its GCD with that to our earlier example, in the congruence2 3 2 8 (mod 10)we can cancel the 2 provided we replace 10 with10(10,2)=102= yields the valid congruence3 8 (mod 5).DailedaCongruencesBefore we turn to another example, we point out an importantcorollary to Theorem 4 (or Lemma 2), which applies whenever themodulus is 2 Let p Nbe prime and let a,b,c Z. If p c , thenac bc(modp) a b(modp). prime,p cimplies that (c,p) = 1.
