5.7: Modular Arithmetic
( \newcommand{\kernel}{\mathrm{null}\,}\)
Modular arithmetic uses only a fixed number of possible results in all its computation. For instance, there are only 12 hours on the face of a clock. If the time now is 7 o’clock, 20 hours later will be 3 o’clock; and we do not say 27 o’clock! This example explains why modular arithmetic is referred to by some as clock arithmetic.
Example 5.7.1
Assume the current time is 2:00 p.m. Write this as 14:00. Sixty five hours later, it would be 79:00. Since 79=24⋅3+7, it will be 7:00 or 7 a.m.
hands-on exercise 5.7.1
Designate Sunday, Monday, Tuesday, …, Saturday as Day 0, 1, 2, …, 6. If today is Monday, then it is Day 1. What day of the week will it be two years from now? Assume there are 365 days in a year.
In the clock example, we essentially regard 27 o’clock the same as 3 o’clock. They key is, we are only interested in the remainder when a value is divided by 12.
Definition: congruent modulo
Let n≥2 be a fixed integer. We say the two integers m1 and m2 are congruent modulo, denoted m1≡m2(modn) if and only if n∣(m1−m2). The integer n is called the modulus of the congruence.
What does this notion of congruence have to do with remainders? The next result describes their connection.
Theorem 5.7.1
Let n≥2 be a fixed integer. For any two integers m1 and m2, m1≡m2 (mod~n)⇔m1modn=m2modn.
Remark
Do not confuse the two notations. The notation “(mod n)” after m1≡m2 indicates a congruence relation, in which “mod n” are enclosed by a pair of parentheses, and the notation is placed at the end of the congruence. In contrast, the “mod” between m1 and n, without parentheses, is a binary operation that yields the remainder when m1 is divided by n.
- Proof
-
(⇒) Assume m1≡m2 (mod n). The definition of congruence implies that we have n∣(m1−m2). Hence, m1−m2=nq for some integer q. Let m1=nq1+r1 and m2=nq2+r2 for some integers q1,q2,r1,r2, such that 0≤r1,r2<n. Then nq=m1−m2=n(q1−q2)+r1−r2. Since r1−r2=n(q−q1+q2), we conclude that n∣r1−r2. However, 0≤r1,r2<n implies that |r1−r2|<n. Therefore, we must have r1−r2=0, or r1=r2. It follows that m1modn=m2modn.
(⇐) Assume m1modn=m2modn. According to the Division Algorithm, the remainder in an integer division is unique. Thus, m1=nq1+r and m2=nq2+r for some integers q1,q2,r such that 0≤r<n. Then m1−m2=(nq1+r)−(nq2+r)=n(q1−q2). Therefore, n∣(m1−m2).
Corollary 5.7.2
Let n≥2 be a fixed integer. Then a≡0(modn)⇔n∣a.
Theorem 5.7.1 tells us m1≡m2 (mod n) if and only if m1 and m2 share the same remainder when they are divided by n. Given any integer m, mmodn∈{0,1,2,…,n−1}. We call these values the residues modulo . In modular arithmetic, when we say “reduced modulo ,” we mean whatever result we obtain, we divide it by n, and report only the smallest possible nonnegative residue.
The next theorem is fundamental to modular arithmetic.
Theorem 5.7.3
Let n≥2 be a fixed integer. If a≡b (mod n) and c≡d (mod n), then a+c≡b+d(modn),ac≡bd(modn).
- Proof
-
Assume a≡b (mod n) and c≡d (mod n). Then n∣(a−b) and n∣(c−d). We can write a−b=ns,andc−d=nt for some integers s and t. Consequently, (a+c)−(b+d)=(a−b)+(c−d)=ns+nt=n(s+t), where s+t is an integer. This proves that a+c≡b+d (mod n). We also have ac−bd=(b+ns)(d+nt)−bd=bnt+nsd+n2st=n(bt+sd+nst), where bt+sd+nst is an integer. Thus, n∣(ac−bd), which means ac≡bd (mod n).
Because of Theorem 5.7.3, we can add or multiply an integer to both sides of a congruence without altering the congruences.
Example 5.7.2
We can use subtraction to reduce 2370 modulo 11. Any multiple of 11 is congruent to 0 modulo 11. So we have, for example, 2370≡2370(mod11),and0≡−2200(mod11). Applying Theorem 5.7.3, we obtain 2370≡2370−2200=170(mod11). What this means is: we can keep subtracting appropriate multiples of n from m until the answer is between 0 and n−1, inclusive. It does not matter which multiple of 11 you use. The point is, pick one that you can think of quickly, and keep repeating the process. Continuing in this fashion, we find 170≡170−110=60(mod11). Since 60−55=5, we determine that 2370≡5 (mod 11).
hands-on exercise 5.7.2
Reduce 12457 to the smallest nonnegative residue modulo 17.
Example 5.7.3
In a similar manner, if m is negative, we can keep adding multiples of n to it until the answer is positive. For example, −278≡−278+300=52(mod11). it is obvious that 52≡52−44=8 (mod 11). Thus, −278≡8 (mod 11).
hands-on exercise 5.7.3
Evaluate −3275mod11. This is the same as reducing −3275 to the smallest nonnegative residue modulo 11.
In a complicated computation, reduce the result from each intermediate step before you carry on with the next step. This will simplify the computation tremendously. To further speed up the computation, we can use negative values in the intermediate step. Nonetheless, the final answer must be between 0 and n−1.
Example 5.7.4
Reduce 372⋅41−53⋅2 modulo 7.
- Solution
-
Take note that 37≡37−35=2(mod7),41≡41−42=−1(mod7),53≡53−49=4(mod7). Therefore, 372⋅41−53⋅2≡22⋅(−1)−4⋅2=−12(mod7). We determine that 372⋅41−53⋅2≡2 (mod 7).
hands-on exercise 5.7.4
Evaluate 563⋅22⋅17−35⋅481 (mod 9).
Tedious computation may become rather simple under modular arithmetic.
Example 5.7.5
Show that if an integer n is not divisible by 3, then n2−1 is always divisible by 3. Equivalently, show that if an integer n is not divisible by 3, then n2−1≡0 (mod 3).
- Solution 1
-
Let n be an integer not divisible by 3, then either n≡1 (mod 3), or n≡2 (mod 3).
Case 1. If n≡1 (mod 3), then n2−1≡12−1=0(mod3).
Case 2. If n≡2 (mod 3), then n2−1≡22−1=3≡0(mod3).
In both cases, we have found that n2−1 is divisible by 3.
- Solution 2
-
Let n be an integer not divisible by 3, then either n≡1 (mod 3), or n≡2 (mod 3). This is equivalent to saying n≡±1 (mod 3). Then n2−1≡(±1)2−1=1−1=0(mod3), which means n2−1 is divisible by 3.
hands-on exercise 5.7.5
Use modular arithmetic to show that 5∣(n5−n) for any integer n.
hands-on exercise 5.7.6
Use modular arithmetic to show that n(n+1)(2n+1) is divisible by 6 for any integer n.
Raising an integer to a large power poses a serious problem. We cannot just raise an integer to a large power, because the result could be so large that the calculator or computer has to convert it into a decimal value and start using scientific notation to handle it. Consequently, the answer will not be accurate.
A better solution is to reduce the intermediate results modulo n after each multiplication. This will produce an accurate result, but it will take a long time to finish if the power is huge. Fortunately, there is a much faster way to perform exponentiation that uses a lesser number of multiplications.
Example 5.7.6
Evaluate 529 (mod 11).
- Solution
-
First, write the exponent 29 as a sum of powers of 2. We can do it by inspection. Start with the highest power of 2 that is less than or equal to 29, and then work with whatever is left in the sum: 29=16+13=16+8+5=16+8+4+1. We are essentially expressing 29 in base 2. We can now write
529=516+8+4+1=516⋅58⋅54⋅5.
These powers of 5 can be obtained by means of repeated squaring:
51=5,52=52,54=(52)2,58=(54)2,516=(58)2,⋮⋮
The iteration is simple: each new power is obtained by squaring the previous power. Since we are doing modular arithmetic, we want to reduce each intermediate result modulo 11: 5=5(mod 11)52=25≡3(mod 11)54≡32=9=−2(mod 11)58≡92≡(−2)2=4(mod 11)516≡42=16≡5(mod 11) It follows that 529=516⋅58⋅54⋅5≡5⋅4⋅(−2)⋅5(mod11). After simplification, we find 529≡9 (mod 11).
hands-on exercise 5.7.7
Use repeated squaring to find 745 (mod 11).
hands-on exercise 5.7.8
Use repeated squaring to evaluate 958 (mod 23).
In modular arithmetic, we are basically working with the remainders only. The set of integers {0,1,2,…,n−1} is called the set of integers modulo , and is denoted by Zn (pronounced as Z mod n). In addition, we define two new arithmetic operations on Zn. They are called “addition” and “multiplication” because they work like the usual addition and multiplication, except that we have to apply the mod operation to the results. To distinguish them from the usual addition and multiplication, we denote them by ⊕ and ⊙, and are called “circled plus” and “circled dot,” respectively. Formally,
a⊕b=(a+b)modn,anda⊙b=(a⋅b)modn.
The addition and multiplication tables for Z6 are listed below.
⊕012345001234511234502234501334501244501235501234⊙012345000000010123452024024303030340420425054321
Compare them to the tables for Z7.
⊕012345600123456112345602234560133456012445601235560123466012345⊙012345600000000101234562024613530362514404152635053164260654321
In both addition tables, all possible values appear in every row and every column. The same is true in the nonzero rows and nonzero columns in the multiplication table for Z7. However, some of the rows in the multiplication table for Z6 do not contain all the integers in Z6. This suggests that the algebraic properties of Zn depend on the value of n.
In fact, whenever n is prime, the addition and multiplication tables of Zn behave like the ones in Z7. It can be shown that when n is prime, Zn has the following properties.
- Both ⊕ and ⊙ are commutative, meaning a⊕b=b⊕aanda⊙b=b⊙a for all a,b∈Zn.
- Both ⊕ and ⊙ are associative, meaning that (a⊕b)⊕c=a⊕(b⊕c)and(a⊙b)⊙c=a⊙(b⊙c) for all a,b,c∈Zn.
- The operations ⊕ and ⊙ satisfy the distributive laws a⊙(b⊕c)=(a⊙b)⊕(a⊙c)and(b⊕c)⊙a=(b⊙a)⊕(c⊙a) for all a,b,c∈Zn.
- The integer 0 is the additive identity, meaning that a⊕0=0⊕a=a for all a∈Zn.
- For every a∈Zn, there exists a unique integer a′∈Zn such that a⊕a′=0. This integer a′ is called the additive inverse or negative of a, and is denoted by −a.
- The integer 1 is the multiplicative identity, meaning that a⊙1=1⊙a=a for all a∈Zn.
- For every integer a∈Z∗n (hence, a≠0), there exists a unique nonzero integer a′∈Zn such that a⊙a′=1. This integer a′ is called the multiplicative inverse or reciprocal of a, and is denoted by a−1.
Example 5.7.7
From the tables above, only 1 and 5 have multiplicative inverses in Z6. In fact, 1⋅1=1and5⋅5=1in Z6 imply that 1−1=1, and 5−1=5 in Z6. On the other hand, every nonzero integer in Z7 has a multiplicative inverse: 1−1=1,2−2=4,3−1=5,4−1=2,5−1=3,and6−1=6. Be sure to verify these inverses.
In general, given any set of numbers, we can define arithmetic operations in any way we like, provided that they obey certain rules. This produces an algebraic structure. For example, we call a set of elements S with two binary operations denoted ⊕ and ⊙ a field, and write ⟨S,⊕,⊙⟩ or (S,⊕,⊙), if it satisfies all seven properties listed above. Both ⟨R,+,⋅⟩ and ⟨Q,+,⋅⟩ are fields, but ⟨Z,+,⋅⟩ is not, because multiplicative inverse of a does not exist if a≠±1.
Theorem 5.7.4
The algebraic structure ⟨Zn,⊕,⊙⟩ is a field if and only if n is prime.
- Proof
-
Verification of most of the properties is rather straightforward, with the exception of the existence of the multiplicative inverse, which we shall prove here. Since n is a prime, any a∈Z∗ must be relatively prime to n. Hence, as+nt=1 for some integers s and t. Modulo n, we find nt=0, hence, as+nt=1 becomes as=1. Therefore a−1≡s (mod n).
The theorem tells us that if n is prime, then Zn is a field, hence, every nonzero integer has a multiplicative inverse.
Example 5.7.8
Determine 7−1 (mod 29).
- Solution
-
We want to find a number a′ such that 7a′≡1 (mod 29). Note that gcd(7,29)=1. Using extended Euclidean algorithm, we find 7(−4)+29⋅1=1. Since 29⋅1≡0 (mod 29), after reducing modulo 29, we find 7(−4)≡1(mod29). This implies that 7−1≡−4≡25 (mod 29).
When n is composite, Zn is not a field. Then not every nonzero integer in it has a multiplicative inverse. Of course, some special nonzero integers may still have multiplicative inverses.
hands-on exercise 5.7.9
Determine 8−1 (mod 45).
Example 5.7.9
Solve the equation 7x−3=5 over Z29.
- Solution
-
From 7x−3=5, we find 7x=8. Recall that what this equation really means is 7x≡8(mod29). The answer is not x=87, because Z29 only contains integers as its elements. This is what we should do: multiply 7−1 to both sides of the congruence: 7−1⋅7x≡7−1⋅8(mod29). Since 7−1⋅7≡1 (mod 29), we now have x≡7−1⋅8(mod29). In a way, we use multiplicative inverse to simulate division. In this case, 7−1≡7 (mod 29). Hence, x≡7⋅8≡26 (mod 29).
hands-on exercise 5.7.10
Solve the equation 8x+23=12 over Z45.
Example 5.7.10
Explain why 3−1 does not exist in Z24.
- Solution
-
Suppose 3−1 exists in Z24, say, 3−1≡z (mod 24). This means 3z≡1 (mod 24). Hence, 3z=24q+1 for some integer q. This in turn implies that 1=3z−24q=3(z−8q), which is clearly impossible because z−8q is an integer. This contradiction shows that 3−1 does not exist in Z24.
Both R and Q are infinite fields, while Zn is a finite field when n is prime. The next result is a truly amazing one, because it proclaims that the number of elements in any finite field (one with finitely many elements) must be the power of a certain prime. Unfortunately, we are unable to prove it here, because it is beyond the scope of this course.
Theorem 5.7.5
There exists a finite field of n elements if and only if n is the power of a prime.
- Modular arithmetic modulo n uses the mod operation to reduce the answers of all computation to within 0 through n−1.
- Instead of waiting until we obtain the final answer before we reduce it modulo n, it is easier to reduce every immediate result modulo n before moving on to the next step in the computation.
- We can use negative integers in the intermediate steps.
- The set of integers {0,1,2,…,n−1}, together with modular arithmetic modulo n, is denoted as Zn.
- For a⋅a′≡1 (mod n), we say that a′ is the multiplicative inverse of a, and denote it a−1.
- For some a∈Zn, the multiplicative inverse a−1 may not exist. If it exists, we can use it to simulate division.
Exercise 5.7.1
Construct the addition and multiplication tables for Z8. Which nonzero elements have multiplicative inverses (reciprocals)? What are their multiplicative inverses?
Exercise 5.7.2
Repeat the last problem with Z9.
Exercise 5.7.3
Find the sum and product of 1053 and 1761 in Z17.
Exercise 5.7.4
Some of the results we derived earlier can be easily proven via modular arithmetic. For example, show that if an integer n is not divisible by 3, then n≡±1 (mod 3). What can you say about n2 (mod 3)? Therefore what form must n2 take?
Exercise 5.7.5
Show that no integer of the form m2+1 is a multiple of 7.
- Hint
-
What are the possible values of m (mod 7)? Compare this to the last problem.
Exercise 5.7.6
What are the possible values of m (mod 13) such that m2+1 is a multiple of 13?
- Hint
-
Compute m2+1 (mod 13) for each value of m.
Exercise 5.7.7
Find the value of 445 in Z11
- using the fact that 45=3⋅3⋅5
- using repeated squaring
Exercise 5.7.8
Use repeated squaring to evaluate 523 (mod 11).
Exercise 5.7.9
Solve these equations
- 2x+5=10 over Z13
- 37x+28=25 over Z57
- 12−24x=15 over Z35
Exercise 5.7.10
Let p and q be odd primes.
- Show that p takes the form of either 6k+1 or 6k+5.
- Hint
-
First, explain why being odd restricts p to the form of 6k+1, 6k+3, and 6k+5. Next, argue why p≠6k+3.
- What could p be congruent to, modulo 24?
- Show that if p≥q≥5, then 24∣(p2−q2).
- Hint
-
What are the possible values of p2 and q2 modulo 24?
Exercise 5.7.11
Use modular arithmetic to prove that, if n is an integer not divisible by 5, then n4−1 is divisible by 5.
Exercise 5.7.12
Use modular arithmetic to prove that 8∣(52n+7) for any integer n≥0.
Exercise 5.7.13
Use modular arithmetic to prove that 3∣(22n−1) for any integer n≥0.
Exercise 5.7.14
Use modular arithmetic to prove that 5∣(33n+1+2n+1) for any integer n≥0.