3 Congruence - math.nyu.edu

1 Reasoning: Computers, Number Theory and Cryptography3 CongruenceCongruences are an important and useful tool for the study of divisibility. As we shall see,they are also critical in the art of a and b are integers andn>0,wewritea bmodnto meannj(b a). We read this as a is congruent to b modulo (or mod) example, 29 8 mod 7, and 60 0 mod notation is used because the properties of Congruence \ " are very similar to theproperties of equality \=". The next few result make this any integers a and b, and positive integer n, we Ifa bmodnthenb Ifa bmodnandb cmodnthena cmodnThese results are classically called: 1. Reflexivity; 2. Symmetry; and 3. Transitivity. (a a) since 0 is divisible by any integer. Thereforea Ifa bmodnthennj(b a). Therefore,nj( 1)(b a)ornj(a b). Therefore,b Ifa bmodnandb cmodnthennj(b a)andnj(c b). Using the linear combinationtheorem, we havenj(b a+c b)ornj(c a).

2 Thus,a following result gives an equivalent way of looking at Congruence . It replaces the con-gruence sign with an bmodnthenb=a+nqfor some integerq, and :Ifa bmodnthen by de nitionnj(b a). Therefore,b a=nqfor + +nq,thenb a=nqand sonj(b a) and hencea bmodnthenb=a+ will use often this theorem for calculations. Thus, we can write 15 2mod17bysubtracting 17 from 15: 2=15+( 1) 17. Similarly, 52 12 mod 20. Just subtract 40(2 times 20) from simple consequence is this: Any number is congruent modnto its remainder when +r, the above result shows thata rmodn. Thus for example, 23 2 mod 7 and 103 3 mod 10. For this reason, the remainder of a numberawhen dividedbynis calledamodn. In EXCEL, as in many spreadsheets, this is written "MOD(a,n)." Ifyou put the expression =MOD(23,7) in a cell, the readout will be simply 2. Try it!Another way of relating Congruence to remainders is as bmodnthenaandbleave the same remainder when divided ifaandbleave the same remainder when divided byn, thena :Supposea bmodn.

3 Then by Theorem ,b=a+ the remainderrwhen divided byn,wehavea=nQ+rwith 0 r<n. Therefore,b=a+nq=nQ+r+nq=n(Q+r)+r,andsob leaves the same remainder when divided is straightforward and we omit the can now show some useful algebraic properties of congruences. Briefly, congruences canbe added and bmodnandc +c b+ :Writeb=a+nq1andd=c+nq2, using Theorem Then adding equalities, wegetb+d=a+c+nq1+nq2=a+c+n(q1+q2). This shows thata+c b+dmodnbyTheorem , multiplying, we getbd=(a+nq1)(c+nq2)=ac+naq2+ncq1+ ,bd=ac+n(aq2+cq1+nq1q2,andsoac bdmodn, again by Theorem have noted that 23 2 mod 7. We can square this ( multiply this Congruence byitself) to get 232 4 mod 7. What a nice way to nd the remainder of 232when it is dividedby 7! Multiply again by 23 2 mod 7, to get233 8 1mod726(This string of congruences is similar to a string of inequalities. It is read 233is congruentto 8 which is congruent to 1 mod 7.))

4 By transitivity (Theorem ) this implies that 233iscongruent to 1 mod 7.) Once we know that 233 1 mod 7, we can raise to the 5th power( multiply this by itself 5 times) to get 2315 1 mod 7. The application of a few theoremsand we have found remainders of huge numbers rather easily!Example explained on page 26, this is the remainder when 17341is divided by have17 2mod5 Squaring, we have172 4 1mod5 Squaring again, we nd174 1mod5 Now, 1 to any power is 1, so we raise this last Congruence to the 85th power. Why 85? Justwait a moment to nd out. We then nd17340 1mod5 Finally, multiply by the rst Congruence to obtain17341 2mod5So the required remainder is strategy is to nd some power of 17 to be 1 mod 5. Here, the power 4 worked. Thewe divided 4 into 341 to get a quotient 85, and this is the power we used on the congruence174 1 mod 5. Note also the little trick of replacing 4 by 1 mod 5.

5 This gives an easiernumber to forx:5x method is as follows. We know that gcd(5,12) = 1, so some linear combination of 5and 12 is equal to 1. In Section 1 we had a general method for doing this, and we also hada spreadsheet approach. However, we can simply note by observation that1=5 5+( 2) 12So both sides of this equality are congruent to each other mod 12. Hence1 5 5+( 2) 12 5 5mod1227So one solution isx= 5. More generally, ifx 5mod12then5x 25 1mod12 Here is another approach: Start with the equation 5x 1 mod 12. If this were an equality,we would simply divide by 5 to getx=1/5. But we are in the realm of integers so thiswon't work. Instead wemultiplyby5toget25x 5 mod 12 orx 5 mod 12. Note thatwe multiplied by 5 to get a coe cient of 1: 5 5 1 mod algebra of congruences is sometime referred to as \clock arithmetic." This exampleillustrates this. Imagine you are a mouse and that each day you travel clockwise around aclock, passing through 25 minutes on the clock.

6 You start at 12 o'clock. Here is what youjourney will look like:StartDay 1 Day 2 Day 3 Day 4 Day 512 Midnight5 o'clock10 o'clock3 o'clock8 o'clock1 o'clockNote that the transition from 10 o'clock was not to 15 o'clock, but (working mod 12) to15 mod 12 or 3 o'clock. In terms of clocks, we asked when the mouse would land at the 1o'clock spot on the can quickly nd when the mouse will land at 4 o`clock. The equation is5x 4mod12 Multiply by 5 to get 25x 20 mod 12 or simplyx 8 mod 12. It take 8 clock, different mouse. This mouse goes 23 minutes a day and startsat 12 o clock. How many days before she reaches 9 minutes before 12?The appropriate Congruence is 23x 9 mod 60. We'll use the gcd method and nd 1 as alinear combination of 23 and 60. A spreadsheet calculation gives1= 13 23 + 5 60 Taking this mod 60, we nd23( 13) by 9toget23(117) 117 57 mod 60. And so the mouse must travel 57 days to reach 9 minutes beforethe hour.

7 Note that 57 3 mod 60 so the mouse will take 3 days if she goes in the to now, all of our congruences have been modulo one xedn. The following results showhow to change the modulus in certain bmodn, andcis a positive integer, thenca cbmodcnProof:This is little more than a divisibility theorem. Sincenj(b a), we havecnjc(b a)orcnj(cb ca), converse is also valid. Thus, ifca cbmodcnwithc>0thena results can be stated: A Congruence can by multiplied through (including the modulus)and similarly, it can be divided by a common , we can mention that ifa bmodnand ifdjn,thena can now tackle the general question of solving a linear congruenceax bmodn. We will nd when this Congruence has a solution, and how many solutions it has. We rst considerthe case gcd(a, n) = 1. (In the examples above, this was the situation.) The followingtheorem answers this question and also shows how to nd the (a, n)=1, then the congruenceax bmodnhas a solutionx= this case, the general solution of the Congruence is given byx :Sinceaandnare relative prime, we can express 1 as a linear combination of them:ar+ns=1 Multiply this bybto getabr+nbs= getabr+nbs bmodnorabr bmodnThusc=bris a solution of the congruenceax bmodn.

8 In general, ifx cmodnwehaveax ac now claim thatanysolution ofax bmodnis necessarily congruent bmodn. Subtract to getax ac 0modnora(x c) 0modnBut this means thatnja(x br). But sinceaandnare relatively prime, this implies thatnj(x c)andx cmodn. This completes the important special case occurs whennis a a prime, the congruenceax bmodphas a unique solutionxmodpprovideda6 reason we single this case out is that this result is almost exactly like the similar resultin high school algebra: The equationax=bhas a unique solution provideda6=0. Weshallsoon delve further into this analogy. The reason this is true is that if an integerais notdivisible byp, it is relatively prime to p. Thus, ifa6 0modp,thenaandpare the course of the proof of theorem , we proved the following useful acmodnand ifgcd(a, n)=1, then we haveb short, we can cancel the factorafrom both sides of the Congruence so long as gcd(a, n)= algebra, we learn that we \can divide an equationax=aybya"ifa6=0.

9 Herewecan\cancel the factorafrom both sides of the congruenceax aymodn"ifaandnarerelatively prime. This theorem is sometimes called the cancelation law for suppose that we wish to solve the congruenceax bmodnwhered=gcd(a, n)> example, consider the Congruence 18x 12 mod 24. Hered=gcd(18,24) = 6. We candivide this Congruence by 6 to get the equivalent15congruence 3x 2mod4. Soweendupwith the Congruence 3x 2 mod 4, in which gcd(3,4) = 1 and which has general solutionx 2 mod 4. So this is the solution of the original Congruence 18x 12 mod 24. Thisworked because the gcd also divided the constant term 12. If it didn't there would be nosolution. This is the content of the following theorem which generalizes this the congruenceax (a, n). Then1. Ifddoes not divideb, the Congruence has no Ifdjbthen the Congruence is equivalent to the Congruence (a/d)x (b/d)mod(n/d)which has a unique solution :Suppose there were a solution ofax bmodn.

10 Then we would haveax bmoddordjb. So a necessary conditionfor a solution is thatdjb. This prove part 1. As for part 2, divide the entire Congruence bydas in the above example. The reduced Congruence has a unique solution modn/dsincea/dandn/dare relatively on a Small has an interesting interpretation{ifpis a prime and we work modp,theintegers modpbehave algebraically like the real numbers. In the real number system theequationax=bhas a solutionx=b/a=ba 1wherea 1=1/ais the reciprocal ofaand isthe solution of the equationax= 1. What is the situation if we try to do this modp?15It is equivalent, since we can multiply the resulting Congruence by 6 to get back the original is the value of5 1mod 7? is required to nd the solution of 5x 1 mod 7. We can do this using themethod of Example 3. Since3 5+( 2)7 = 1be observation, we have3 5 1mod7So 5 1 3 mod 7, or simply 5 1= 3 mod 7, where equality if used because it is understoodthat we are working mod we are working mod 7, there are only 7 di erent numbers mod 7, namely the remainders0 through 6 when a number is divided by 7.}