Processing math: 100%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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=243+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 n2 be a fixed integer. We say the two integers m1 and m2 are congruent modulo, denoted m1m2(modn) if and only if n(m1m2). 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 n2 be a fixed integer. For any two integers m1 and m2, m1m2 (mod~n)m1modn=m2modn.

Remark

Do not confuse the two notations. The notation “(mod n)” after m1m2 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 m1m2 (mod n). The definition of congruence implies that we have n(m1m2). Hence, m1m2=nq for some integer q. Let m1=nq1+r1 and m2=nq2+r2 for some integers q1,q2,r1,r2, such that 0r1,r2<n. Then nq=m1m2=n(q1q2)+r1r2. Since r1r2=n(qq1+q2), we conclude that nr1r2. However, 0r1,r2<n implies that |r1r2|<n. Therefore, we must have r1r2=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 0r<n. Then m1m2=(nq1+r)(nq2+r)=n(q1q2). Therefore, n(m1m2).

Corollary 5.7.2

Let n2 be a fixed integer. Then a0(modn)na.

Theorem 5.7.1 tells us m1m2 (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,,n1}. 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 n2 be a fixed integer. If ab (mod n) and cd (mod n), then a+cb+d(modn),acbd(modn).

Proof

Assume ab (mod n) and cd (mod n). Then n(ab) and n(cd). We can write ab=ns,andcd=nt for some integers s and t. Consequently, (a+c)(b+d)=(ab)+(cd)=ns+nt=n(s+t), where s+t is an integer. This proves that a+cb+d (mod n). We also have acbd=(b+ns)(d+nt)bd=bnt+nsd+n2st=n(bt+sd+nst), where bt+sd+nst is an integer. Thus, n(acbd), which means acbd (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, 23702370(mod11),and02200(mod11). Applying Theorem 5.7.3, we obtain 237023702200=170(mod11). What this means is: we can keep subtracting appropriate multiples of n from m until the answer is between 0 and n1, 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 170170110=60(mod11). Since 6055=5, we determine that 23705 (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, 278278+300=52(mod11). it is obvious that 525244=8 (mod 11). Thus, 2788 (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 n1.

Example 5.7.4

Reduce 37241532 modulo 7.

Solution

Take note that 373735=2(mod7),414142=1(mod7),535349=4(mod7). Therefore, 3724153222(1)42=12(mod7). We determine that 372415322 (mod 7).

hands-on exercise 5.7.4

Evaluate 563221735481 (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 n21 is always divisible by 3. Equivalently, show that if an integer n is not divisible by 3, then n210 (mod 3).

Solution 1

Let n be an integer not divisible by 3, then either n1 (mod 3), or n2 (mod 3).

Case 1. If n1 (mod 3), then n21121=0(mod3).

Case 2. If n2 (mod 3), then n21221=30(mod3).

In both cases, we have found that n21 is divisible by 3.

Solution 2

Let n be an integer not divisible by 3, then either n1 (mod 3), or n2 (mod 3). This is equivalent to saying n±1 (mod 3). Then n21(±1)21=11=0(mod3), which means n21 is divisible by 3.

hands-on exercise 5.7.5

Use modular arithmetic to show that 5(n5n) 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=51658545.

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=253(mod 11)5432=9=2(mod 11)5892(2)2=4(mod 11)51642=165(mod 11) It follows that 529=5165854554(2)5(mod11). After simplification, we find 5299 (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,,n1} 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,

ab=(a+b)modn,andab=(ab)modn.

The addition and multiplication tables for Z6 are listed below.

012345001234511234502234501334501244501235501234012345000000010123452024024303030340420425054321

Compare them to the tables for Z7.

012345600123456112345602234560133456012445601235560123466012345012345600000000101234562024613530362514404152635053164260654321

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.

  1. Both and are commutative, meaning ab=baandab=ba for all a,bZn.
  2. Both and are associative, meaning that (ab)c=a(bc)and(ab)c=a(bc) for all a,b,cZn.
  3. The operations and satisfy the distributive laws a(bc)=(ab)(ac)and(bc)a=(ba)(ca) for all a,b,cZn.
  4. The integer 0 is the additive identity, meaning that a0=0a=a for all aZn.
  5. For every aZn, there exists a unique integer aZn such that aa=0. This integer a is called the additive inverse or negative of a, and is denoted by a.
  6. The integer 1 is the multiplicative identity, meaning that a1=1a=a for all aZn.
  7. For every integer aZn (hence, a0), there exists a unique nonzero integer aZn such that aa=1. This integer a is called the multiplicative inverse or reciprocal of a, and is denoted by a1.

Example 5.7.7

From the tables above, only 1 and 5 have multiplicative inverses in Z6. In fact, 11=1and55=1in Z6 imply that 11=1, and 51=5 in Z6. On the other hand, every nonzero integer in Z7 has a multiplicative inverse: 11=1,22=4,31=5,41=2,51=3,and61=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 aZ 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 a1s (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 71 (mod 29).

Solution

We want to find a number a such that 7a1 (mod 29). Note that gcd(7,29)=1. Using extended Euclidean algorithm, we find 7(4)+291=1. Since 2910 (mod 29), after reducing modulo 29, we find 7(4)1(mod29). This implies that 71425 (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 81 (mod 45).

Example 5.7.9

Solve the equation 7x3=5 over Z29.

Solution

From 7x3=5, we find 7x=8. Recall that what this equation really means is 7x8(mod29). The answer is not x=87, because Z29 only contains integers as its elements. This is what we should do: multiply 71 to both sides of the congruence: 717x718(mod29). Since 7171 (mod 29), we now have x718(mod29). In a way, we use multiplicative inverse to simulate division. In this case, 717 (mod 29). Hence, x7826 (mod 29).

hands-on exercise 5.7.10

Solve the equation 8x+23=12 over Z45.

Example 5.7.10

Explain why 31 does not exist in Z24.

Solution

Suppose 31 exists in Z24, say, 31z (mod 24). This means 3z1 (mod 24). Hence, 3z=24q+1 for some integer q. This in turn implies that 1=3z24q=3(z8q), which is clearly impossible because z8q is an integer. This contradiction shows that 31 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 n1.
  • 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,,n1}, together with modular arithmetic modulo n, is denoted as Zn.
  • For aa1 (mod n), we say that a is the multiplicative inverse of a, and denote it a1.
  • For some aZn, the multiplicative inverse a1 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

  1. using the fact that 45=335
  2. using repeated squaring

Exercise 5.7.8

Use repeated squaring to evaluate 523 (mod 11).

Exercise 5.7.9

Solve these equations

  1. 2x+5=10 over Z13
  2. 37x+28=25 over Z57
  3. 1224x=15 over Z35

Exercise 5.7.10

Let p and q be odd primes.

  1. 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 p6k+3.

  1. What could p be congruent to, modulo 24?
  2. Show that if pq5, then 24(p2q2).
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 n41 is divisible by 5.

Exercise 5.7.12

Use modular arithmetic to prove that 8(52n+7) for any integer n0.

Exercise 5.7.13

Use modular arithmetic to prove that 3(22n1) for any integer n0.

Exercise 5.7.14

Use modular arithmetic to prove that 5(33n+1+2n+1) for any integer n0.


This page titled 5.7: Modular Arithmetic is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Harris Kwong (OpenSUNY) .

  • Was this article helpful?

Support Center

How can we help?