3 Congruence

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.

2 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). 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.

3 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.

4 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.)

5 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. 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!

6 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.

7 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.

8 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. 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.

9 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.

10 And so the mouse must travel 57 days to reach 9 minutes beforethe hour. 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.