Modular arithmetic sheds light on the relation of integers to their remainders when they are divided by a given positive integer. It is useful in both number theory and computer science.

CONGRUENCE CLASSES MOD k

The integers behave in a periodic way when we examine their expressions as one of the forms, for example, 3n, 3n + 1, and 3n + 2. Every third integer is a multiple of 3 and can therefore be written 3n for some integer n. Thus, 3 = 3 × 1, 6 = 3 × 2, 9 = 3 × 3, 12 = 3 × 4, and so on. On the other hand, the numbers 4, 7, 10, 13, etc. can be written 3n + 1, since they are one more than some multiple of 3. Similarly, 5, 8, 11, 14, etc. can be written 3n + 2. Thus, the sequence of consecutive numbers 3, 4, 5 yield numbers of the form 3n, 3n + 1, and 3n + 2. The next number, 6, signifies that the pattern repeats. In fact, the next three numbers, 6, 7, 8, mimic their three predecessors perfectly, following the same format as 3n, 3n + 1, 3n + 2. Of course, the n changes from 1 to 2, but the pattern persists. Every third number is of the same format.

There are three classes of numbers: 3n, 3n + 1, and 3n + 2. All numbers belong to one of these mutually exclusive and jointly exhaustive classes. Even 0 is a member of one of the classes, namely, the 3n class. Negative numbers are included, as well, since n may be negative.

The entire analysis can be repeated for the coefficient 5 or any other coefficient. Every integer is in one of the forms 5n, 5n + 1, 5n + 2, 5n + 3, and 5n + 4. Of course, if we continued this consecutive sequence to 5n + 5, we would needlessly be introducing an extra class, since 5n + 5 = 5(n + 1), which is in the same class as 5n. One could let m = n + 1, in which case 5n + 5 = 5m. There’s nothing sacred about n.

Notice there are five classes when we use the coefficient 5 and, more generally, there are k classes when we use the coefficient k. Instead of the word coefficient, mathematicians refer to the modulus k. The k classes are called congruence classes mod k, and the whole subject is called modular arithmetic. Two numbers, a and b, in the same class are called congruent mod k. This is written a = b (mod k). If a and b belong to different classes, they are called incongruent mod k. This is written a ≠ b (mod k).

The chart below, employing the modulus 4, demonstrates the periodic nature of modular arithmetic. The three dots in the first and last box indicate that the chart extends in both directions forever.

Every number in the first column is of the form 4n, that is, it is a multiple of 4. Every number in the second column is of the form 4n + 1, that is, one more than a multiple of 4, and so on. The bold numbers 0, 1, 2, and 3 are called least residues. Each is the remainder when any positive number in its column is divided by 4.

Two numbers are in the same column if and only if their difference is a multiple of 4. Thus, 21 and 9 are in the same column, since 21 − 9 = 12, which is a multiple of 4. Alternatively, 21 = 9 (mod 4) since these numbers are in the same congruence class—namely, the class whose least residue is 1. Observe that this is the remainder when either number is divided by 4.

If we employ the modulus 2, we get a chart with only two columns. The least residues are 0 and 1. These are the remainders, of course, when we divide numbers by 2. Notice that n = 0 (mod 2) when n is even and n = 1 (mod 2) when n is odd. The parity of a number (whether it is odd or even) is the congruence class (mod 2) to which it belongs.

LAWS OF MODULAR ARITHMETIC

The following five statements are different ways of saying the same thing:

1. a = b (mod n).
2. a − b is a multiple of n, that is, n | a − b, or n divides a − b.
3. a and b are in the same column of a modular chart for n, that is, a and b are in the same congruence class mod n.
4. a and b have the same remainder when they are divided by n.
5. a and b have the same form, that is, one is kn + r and the other is jn + r, where r satisfies 0 ≤  r ≤ n − 1.

It is quite interesting to note that congruence equations have most of the properties of ordinary equations. Here are a few of them:

1. If a = b (mod n), then b = a (mod n).
2. If a = b (mod n) and b = c (mod n), then a = c (mod n).
3. If a = b (mod n), then a ± c = b ± c (mod n).
4. If a = b (mod n) and c = d (mod n), then a ± c = b ± d (mod n).
5. If a = b (mod n), then ac = bc (mod n).
6. If a = b (mod n) and c = d (mod n), then ac = bd (mod n).
7. If a = b (mod n), then a^c = b^c (mod n).

Note that ac = bc (mod n) does not permit us to conclude that a = b (mod n). As an illustration, canceling a 6 in the congruence equation 12 = 18 (mod 6) yields the false equation 2 = 3 (mod 6). When can one cancel with impunity? When the factor and the modulus are relatively prime. Consider the equation 20 = 50 (mod 6). Upon canceling the factor 5, we obtain the correct equation 4 = 10 (mod 6). Of course, 5 and 6 are relatively prime, so the cancelation was assured to be legitimate. Another situation that permits cancelation is ac = bc (mod nc). This means that nc | ac − bc, or nc | c(a − b), implying that n | a − b, or a = b (mod n). The price we pay in this case, however, is a change in the modulus from cn to n.

The earlier comments about the “form” of a number may be modified to take into account the following alternate classification. All numbers may be written as 3n, 3n + 1, or 3n − 1. After all, a number of the form 3n + 2, which is two more than a multiple of three, is one less than the next multiple of three, that is, it is of the form 3n − 1. Similarly, all numbers are in one of the five classes 5n, 5n ± 1, and 5n ± 2. In other words, no number is more than two away from a multiple of 5. One sees similarly that no number is more than three away from a multiple of 7. More generally, no number is more than k away from a multiple of the odd number 2k + 1.

MODULAR EQUATIONS

ax = b (mod n), where a, b, and n are given, is a modular equation. An example such as 3x = 7 (mod 11) should make you recall the ordinary equation 3x = 7. We are looking for an integer solution, as 7/3 is unacceptable in modular arithmetic. You might guess that x = 6 is a solution, since 3 × 6 = 18 = 7 (mod 11). We shall develop a method for solving modular equations but only after we determine when they are solvable. We shall also see that there may be several distinct solutions, that is, solutions that are unequal mod n. Consider 2x = 8 (mod 16). This modular equation has two distinct, or different, solutions x = 4 and x = 12 since 4 ≠ 12 (mod 16). We wouldn’t consider x = 20 to be an additional solution since 20 = 4 (mod 16), that is, it isn’t distinct from the solution x = 4. The same is true for x = 28, 36, 44, and so on.

Here is a theorem on linear modular equations, that is, modular equations of first degree (as opposed to x² = 1 (mod 7), which is quadratic).

FERMAT’S LITTLE THEOREM

Given the prime modulus p, the set of numbers {1, 2, 3, …, p − 1} represents each nonzero congruence class of p, with no repetition. Thus, no two of the numbers in the set are congruent mod p. If 1 ≤ i < j ≤ p − 1 and i = j (mod p), we would have the ludicrous statement p | (j − i).

We claim that the set of numbers {a, 2a, 3a, …, (p − 1)a} also does this, that is, it represents each nonzero congruence class of p, with no repetition, provided that gcd(a,p) = 1, that is, as long as p does not divide a. To prove this, assume, to the contrary, that for some i and j satisfying 1 ≤ i < j ≤ p − 1, we have ia = ja (mod p). But when we cancel the a, this becomes i = j (mod p), which is impossible.

Now, let us equate the products of the members of the two “representative” sets of the nonzero congruence classes mod p, since the second set is a permutation of the first, mod p. This yields

or

After canceling the common factor, (p − 1)!, which we have a right to do since p does not divide (p − 1)!, we get Fermat’s little theorem:

FERMAT’S LITTLE THEOREM

Let p be prime, and let gcd(a,p) = 1. Then a^p−1 = 1 (mod p).

MULTIPLICATIVE INVERSES

Given an equation such as 5x = 7, we solve by multiplying both sides by 1/5, since this number is the “multiplicative inverse” of 5, that is, it is the number that yields 1 when we multiply it by 5. Indeed, we get (1/5) × 5x = (1/5) × 7, which becomes 1x = (1/5) × 7, or x = 7/5. When n is prime, the next theorem tells us when we can do this with modular equations of the form ax = b (mod n).

WILSON’S THEOREM

The real numbers have the property that ab = 0 implies that a = 0 or b = 0. This permits us to cancel a nonzero factor c in the equation cx = cy. This can be seen as follows. If cx = cy, then cx − cy = 0, which becomes c(x − y) = 0. Since c ≠ 0, the other factor, x − y, must equal zero, that is, x = y. This doesn’t work when c = 0, or we would have the following screwy “proof” that 1 = 0. Let a = b. Then a² = ab. So a² − b² = ab − b², or (a − b)(a + b) = b(a − b). Canceling a − b yields a + b = b, which becomes 2b = b, under the assumption that a = b. Division by b yields the ridiculous conclusion that 2 = 1. The mistake is the cancelation of a − b. This number is zero.

In modular arithmetic, it is not necessarily the case that ab = 0 (mod n) implies that a = 0 (mod n) or b = 0 (mod n). An example is afforded by ab = 0 (mod 6), which is satisfied by a = 2 and b = 3. When the modulus is prime, however, this state of affairs does not persist.

Observe that . We have

Taking the products of the left and right sides of these equations yields 6! = −1 (mod 7). Let’s compute 10! (mod 11). We get

Taking the products of the left and right sides yields 10! = −1 (mod 11). These two examples indicate a general procedure for computing (p − 1)! (mod p). Obtain a system of (p + 1)/2 equations, the first of which is 1 = 1 (mod p) and the last of which is p − 1 = −1 (mod p), while the intermediate equations are of the form ab = 1 (mod p). Each of the numbers 1, 2, …, p − 1 occurs exactly once among the left members of the system of equations. (Do not fear that any of the numbers between 2 and p − 2 are self-inverse, that is, do not fear that for some x such that 2 ≤ x ≤ p − 2, we have x² = 1 (mod p). If this were the case, we would have x² − 1 = 0 (mod p), or p | (x − 1)(x + 1), implying that p | (x − 1), in which case x = 1 (mod p), or p | (x + 1), in which case x = −1 = p − 1 (mod p).) Taking the products of the left and right sides of the system of equations yields (p − 1)! = −1 (mod p). We have just proven the following beautiful theorem.

WILSON’S THEOREM

Let p be a prime. Then (p − 1)! = −1 (mod p).

This often appears in the equivalent formulation p | (p − 1)! + 1, since (p − 1)! + 1 = 0 (mod p).

Assume for a moment that Wilson’s theorem is true when the modulus is not prime, and let the composite modulus n have the proper divisor d ≥ 2. Then since d | n and n | (n − 1)! + 1, it follows that d | (n − 1)! + 1. But since d < n, we have d | (n − 1)!, which is impossible. So Wilson’s theorem only applies to primes. It may, therefore, be restated as follows.

WILSON’S THEOREM (2ND VERSION)

Let n ≥ 2. Then (n − 1)! = −1 (mod n) if and only if n is prime.

When n = 4, note that 3! = 6 = 2 (mod 4). On the other hand, when n > 4 and n is composite, it can be shown that (n − 1)! = 0 (mod n). For example, 5! = 120 = 0 (mod 6).

SQUARES AND QUADRATIC RESIDUES

Consider the squares of the four nonzero least residues, 1, 2, 3, and 4, of the modulus 5. They are 1, 4, 9, and 16, respectively. When we reduce these numbers, mod 5 (i.e., we compute their least residues), we get 1, 4, 4, and 1, respectively.

Let’s consider another (odd) prime modulus, say, 7. The six nonzero least residues, 1, 2, 3, 4, 5, and 6, when squared and reduced mod 7 yield 1, 4, 2, 2, 4, and 1, respectively.

Let’s consider just one more (odd) prime modulus, 11. The 10 nonzero least residues, 1 through 10, when squared and reduced mod 11 yield 1, 4, 9, 5, 3, 3, 5, 9, 4, and 1, respectively.

Notice that in each of the above odd primes, each reduced square occurs twice. As a consequence, only half of the nonzero least residues have “square roots.” (These least residues are called quadratic residues.) Put another way, when p = 5, 7, or 11, the modular equation x² = a (mod p), which calls for the square root of a, has a solution for only half of the possible values of a. Thus, for example, x² = a (mod 5) has a solution when a is 1 or 4, but has no solution when a = 2 or 3, that is, 1 and 4 are quadratic residues, while 2 and 3 are not. Moreover, the nonzero a’s for which the modular equation x² = a (mod p) has a solution are quite special. There are two solutions for each such a, while there is no solution for the other a’s.

The three lists of squares we obtained are palindromes. A palindrome is a word or phrase that doesn’t change when read backward. An example is “Eva can I stab bats in a cave.” The list of squares mod 11 is 1, 4, 9, 5, 3, 3, 5, 9, 4, 1, which is certainly a palindrome. If you square the nonzero residues, mod 11, in ascending order, that is, 1, 2, 3, …, 10 and your friend squares them in descending order, that is, 10, 9, 8, …, 1, both of you will obtain analogous results.

Are these observations for the odd primes 5, 7, and 11 coincidental? Hardly. When p is an odd prime, there are an even number of nonzero residues, 1, 2, …, p − 2, and p − 1. Now, for each a, satisfying 1 ≤ a ≤ p − 1, we find that p − a = −a (mod p). Squaring both sides yields (p − a)² = a² (mod p). For example, when p = 11 and a = 3, we find that 8² = 3² (mod 11).

You might wonder whether more than two nonzero least residues of an odd prime can have the same square. This is impossible. Suppose the three nonzero least residues, a, b, and c, of the odd prime p satisfy the equations a² = b² (mod p) and a² = c² (mod p). Then the first equation becomes a² − b² = 0 (mod p), or (a − b)(a + b) = 0 (mod p), implying by a previous theorem that either b = a (mod p) or b = −a (mod p). By the same reasoning, the equation a² = c² (mod p) implies that either c = a (mod p) or c = −a (mod p). Then the only solutions are a and −a.

On the other hand, the above analysis is not true mod n where n is composite. We have, for example, 1² = 3² = 5² = 7² = 1 (mod 8). Here, the four different inputs 1, 3, 5, and 7 have the same output, namely, 1 (mod 8).

In the set of real numbers, −1 has no square root. When is –1 a quadratic residue mod p? In other words, for which odd primes does the equation x² = −1 (mod p) have a solution? Recall that odd primes have one of the forms 4k + 1 or 4k + 3. Alternatively, any odd prime satisfies exactly one of the equations p = 1 (mod 4) or p = 3 (mod 4). Let’s assume that a² = −1 (mod p). Now, gcd(a,p) = 1, in which case we may invoke Fermat’s little theorem. We get the following equation:

or

This implies that is even, since –1 raised to an odd power is −1. Then , for some k, implying that p − 1 = 4k and p = 4k + 1. We infer that −1 is not a quadratic residue when p is a prime of the form 4k + 3. Thus, for example, x² = −1 (mod 7) has no solution. Now, if p is of the form 4k + 1, is −1 guaranteed to be a quadratic residue? We have the following reasoning. Observe that

Since p − a = −a (mod p), we can rewrite this as

Notice that there are negative signs that permits us to rewrite this, once again, as

(5.1)

Since we are assuming that p = 4k + 1, it follows that and we can dispense with the last factor on the right side of (5.1). Furthermore, by Wilson’s theorem, (p − 1)! = −1 (mod p). Then (5.1) becomes

which shows that −1 is a quadratic residue when p = 4k + 1. When p = 13, for example, we have k = 3, and (2k)! = 6! = 720 = 5 (mod 13). Then 5² = 25 = −1 (mod 13), establishing that –1 is indeed a quadratic residue, mod 13. To summarize this discussion, we have the following theorem.

LAGRANGE’S THEOREM

Recall from Chapter 4 that given integers a and b, where a is positive, there exists a pair of numbers, q and r, where 0 ≤ r < a, such that b = qa + r. The number q is the quotient and r is the remainder when we divide b by a. An analogous equation applies to polynomials with integer coefficients. When dividing f(x) by g(x), we obtain f(x) = q(x)g(x) + r(x), where q(x) is the quotient and r(x) is the remainder. The degree of r(x) is less than the degree of g(x). Furthermore, q(x) and r(x) have integer coefficients. Let’s look at an example to make this clear.

When g(x) = x − a, the division equation becomes f(x) = q(x)(x − a) + r, where r is an integer. Letting x = a in this equation shows us that r = f(a). If a is a root of f(x), that is, if f(a) = 0, then we have

implying that the degree of q(x) is n − 1, where n is the degree of f(x).

We state Lagrange’s theorem on the number of solutions of modular equations involving polynomials when the modulus is prime.

LAGRANGE’S THEOREM

Let p be prime and let , where a_n ≠ 0 (mod p); all of the coefficients are integers, and n ≥ 1. Then the equation f(x) = 0 (mod p) has at most n distinct solutions mod p.

REDUCED PYTHAGOREAN TRIPLES

The Pythagorean theorem was first proven in the sixth century B.C. by Pythagoras, though it was known to the Mesopotamian mathematicians of 2000 b.c. While the theorem belongs to geometry, it is of interest to number theorists when a, b, and c are positive integers that satisfy a² + b² = c². It is remarkable that the sum of two squares can be a square. A set of positive integers {a, b, c} satisfying the equation a² + b² = c² is called a Pythagorean triple.

Are there infinitely many Pythagorean triples? Yes. For any k, we have {3k, 4k, 5k}. After all, (3k)² + (4k)² = 9k² + 16k² = 25k² = (5k)². We are disappointed. All right triangles with sides of lengths 3k, 4k, and 5k are similar to the original “3, 4, 5” right triangle. A reduced Pythagorean triple, or RPT, consists of a Pythagorean triple, {a, b, c}, such that a, b, and c have no common factor. Each RPT adds something new to our list of such triples and produces a uniquely shaped right triangle. This raises two questions. (i) Are there infinitely many RPTs? (ii) How do we find them? We require several small theorems, called lemmas, before we get to the answers.

Let {a, b, c} be an RPT. By Lemma 1, let a be even and let b be odd. Then c must be odd, since c² is the sum of the even number a² and the odd number b². Then c − b and c + b are even. Then let c − b = 2u and c + b = 2v. We then have a² = c² − b² = (c − b)(c + b) = 4uv, which implies that (a/2)² = uv. Claim: u and v are relatively prime. To see this, note that the equations c − b = 2u and c + b = 2v imply that c = v + u and b = v − u. If u and v had a common divisor, so would b and c. Then a would also have this divisor, contradicting the fact that {a, b, c} is an RPT. Since (a/2)² = uv and gcd(u,v) = 1, it follows by Lemma 2 that u and v are squares. Then let u = t² and let v = s². Then a² = 4uv = 4s²t², implying that a = 2st. Furthermore, gcd(s,t) = 1. The equations c = v + u and b = v − u become c = s² + t² and b = s² − t². Finally, note that the equation b = s² − t² implies that s and t have opposite parity or b would be even. To summarize this discussion, the following theorem outlines a procedure that will generate infinitely many RPTs.

generates an RPT and all RPTs are generated this way.

When s = 2 and t = 1, we obtain a = 4, b = 3, and c = 5, while when s = 3 and t = 2, we obtain a = 12, b = 5, and c = 13. On the other hand, when s = 3 and t = 1, we obtain a = 6, b = 8, and c = 10, a multiple of the RPT, {3, 4, 5}.

Recall from Chapter 2 that if x = a² + b² and y = c² + d², then xy = (a² + b²) (c² + d²) = (ac − bd)² + (ad + bc)². If a = c and b = d, this becomes (a² + b²)² = (a² − b²)² + (2ab)².

It is harder to produce infinitely many RPTs for which a − b = 1, the possibility of which is guaranteed by our next theorem.

Here is a theorem whose proof uses RPTs. First, we require a definition. A sequence of k numbers, a₁, a₂, …, a_k, is an arithmetic progression if there exists a number d, the difference, such that a₂ − a₁ = a₃ − a₂ = … = a_k − a_k−1 = d. The number of terms, k, is the length of the progression. The sequence 3, 7, 11 is an arithmetic progression of length 3 with a difference of 4.

When s = 2 and t = 1, for example, we get x = 1, y = 5, and z = 7, yielding the arithmetic progression 1, 25, 49, with common difference 24.

CHINESE REMAINDER THEOREM

Here is an interesting problem asked by a Chinese mathematician 2000 years ago. Find a number whose remainders when divided by 3, 5, and 7, are 2, 3, and 2, respectively. In other words, solve the simultaneous modular equations:

A solution is x = 23, as we can quickly verify. But how do we obtain a solution? Is the solution unique, or are there more solutions? Are there infinitely many solutions? Before we present the so-called Chinese remainder theorem, we require a definition. The integers a₁, a₂, …, a_k are called pairwise relatively prime if gcd(a_i,a_j) = 1 for i ≠ j. In other words, any two of these numbers are relatively prime. This is stronger than the following statement: the integers a₁, a₂, …, a_k have no common factor greater than 1. Thus while the integers 3, 6, 7, and 8 have no common factor greater than 1, they are not pairwise relatively prime, since gcd(3,6) = 3. On the other hand, the integers 2, 5, 9, and 77 are pairwise relatively prime. (It follows that they also obey the weaker condition, that is, they have no common factor greater than 1.) Here is the theorem.

CHINESE REMAINDER THEOREM

Let the positive integers n₁, n₂, …, n_k be pairwise relatively prime, and let . Then the system of modular equations

has a simultaneous solution that is unique mod n.

As a consequence of the last paragraph, there are infinitely many solutions, that is, all members of the congruence class of X mod n.

3, 5, and 7 are pairwise relatively prime, so there exists a solution (which is unique mod n, where n = 3 × 5 × 7 = 105). Now, m₁ = 105/3 = 35, m₂ = 105/5 = 21, and m₃ = 105/7 = 15. Then we must solve the modular equations

yielding x₁ = 2, x₂ = 1, and x₃ = 1. Then X = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233. This is 23 (mod 105).

EXERCISES

An asterisk (*) indicates that the exercise can be developed into a research project.

1. Show that n³ = 0 or ±1 (mod 9). The first few cubes 1, 8, 27, 64, 125, and 216 suggest the pattern 0, 1, −1, 0, 1, −1, …. Does this pattern persist for the first 100 cubes?
2. Show that n³ = 0 or ±1 (mod 7) for n ≤ 100.
3. Show that n⁴ = 0 or 1 (mod 5) for n ≤ 100. Then prove it.
4. ^*Show that x⁴ + y⁴ + z⁴ is not divisible by 5 unless x = y = z = 0 (mod 5).
5. Solve 5x = 2 (mod 26), 7x = 3 (mod 13), 4x = 14 (mod 27), and 2x = 5 (mod 7).
6. Find all seven distinct solutions of 14x = 21 (mod 35).
7. Find all four distinct solutions of 8x = 12 (mod 36).
8. Prove properties 1 through 7 listed in the section titled “Congruence Classes Mod k.”
9. Find the multiplicative inverses of the numbers from 1 through 10 (mod 11) and use these inverses to solve 3x = 2 (mod 11), 5x = 7 (mod 11), and 6x = 9 (mod 11).
10. ^*The numbers 11, 111, 1111, … are called repunits. Show that no repunit is a square by showing that if n is a repunit, then n = 3 (mod 4).
11. Show that r² = s² (mod n), where 1 ≤ r ≤ s < n does not imply that r = s (mod n).
12. Solve the equation x⁵ = 1 (mod 11). It has exactly five solutions.
13. Find 10 RPTs for which b − a = 1.
14. ^*For a and b less than 20, show that exactly one of a, b, a + b, and a − b in any RPT is divisible by 7. Does this pattern persist?
15. Show that the numerator and denominator of the sum of the reciprocals of consecutive odd numbers are the legs of an RPT. For example, , and 8 and 15 belong to the RPT (8, 15, 17).
16. ^*Find 10 arithmetic progressions of length three whose terms are squares and whose first term is 1. An example is 1, 841, 1681. (This is 1², 29², 41².)
17. Show that is not an integer for 2 ≤ n ≤ 20. In fact, it is never an integer after 1.
18. What is the remainder when 2¹⁰⁰ is divided by 7? Hint: 2³ = 1 (mod 7).
19. Use number theory to find the remainder when is divided by 24. How much running time is involved if this is done by computing the sum and then dividing by 24?
20. ^*Show that , where p is a prime less than 50.
21. Show that none of the first 1000 triangular number ends with the digits 2, 4, 7, or 9.
22. Is t_n ever the sum of three consecutive squares for n ≤ 20?
23. ^*Show that no x simultaneously satisfies x = 5 (mod 6) and x = 7 (mod 15) for x ≤ 1000.
24. Solve the simultaneous equations x = 1 (mod 3), x = 1 (mod 5), and x = 1 (mod 7).
25. Using the binomial theorem for (1 + 1)^p, show that 2^p = 2 mod p, where p is a prime.
26. Write a program to determine the truth or falsehood of the modular equation a = b (mod n), given a, b, and n. See the program at the end of the chapter.
27. By squaring the numbers from 1 to 100, find the last two digits (i.e., the unit’s and ten’s digits) of any square. This information will be useful in showing that a given number is not a square. No square ends with 15, for example, showing that 67,915 is not a square.
28. Write a program that determines whether ax = b (mod n) is solvable. If it is solvable, your program should yield a complete set of distinct solutions, each of which is a least residue mod n. See the program at the end of the chapter. You are encouraged to try an alternate approach and compare.
29. Find numbers a and p such that p is prime, a and p are relatively prime, and a^p−1 = 1 (mod p²). As an example, when a = 3 and p = 11, we have 3¹⁰ = 1 (mod 121). Note that it is usually not the case that a^p−1 = 1 (mod p²). Fermat’s little theorem only guarantees that a^p−1 = 1 (mod p). Use the following values of p: 3, 5, 7, 11, and 13.
30. ^*While Wilson’s theorem guarantees that p | (p − 1)! + 1, sometimes, p² | (p − 1)! + 1. For which primes p ≤ 17 is this true?
31. Note that (n − 1)! + 1 is a square when n = 5, 6, and 8. Verify that there are no other solutions for n ≤ 10.
32. Write a program that produces all RPTs for which a − b = 1 and a < N, where N is a given positive integer.

Testing Truth or Falseness of a Modulo Equation

<!DOCTYPE HTML>
<html>
<meta charset="UTF-8">
<head>
<title>Testing mod eq</title>
<script>
 var placeref;

//ax = b (mod n) is solvable if and only 
 //if d | b, where d = gcd(a,n). 
function truefalse(){
 placeref = document.getElementById("place");
 placeref.innerHTML = "";
 a = parseInt(document.f.numA.value);
 n = parseInt(document.f.numn.value);
 b = parseInt(document.f.numB.value);
 ans = (a-b) % n;
 if (ans==0){
   placeref.innerHTML = "The equation is true."
 }
 else {
   placeref.innerHTML = "The equation is false."
 }
 return false;
}
</script>
</head>
<body>
Enter 3 integers for mod equation a = b mod(n) <br/>
<form name="f" onsubmit="return truefalse();">
 a: <input type="number" name="numA" value=""/>  
 b: <input type="number" name="numB" value=""/>  

 n: <input type="number" name="numn" value=""/><br/>
 <input type="submit" value="Enter"/>
</form>
<p id="place">
 Messages will go here.
</p>
</body>
</html>
Solvability of Modulo Equation and Finding Solutions
<!DOCTYPE HTML>
<html>
<meta charset="UTF-8">
<head>
<title>Solving mod eq</title>
<script>
 var placeref;
 
 //ax = b (mod n) is solvable if and only if d | b, where //d = gcd(a,n). 
function solvable(){
 placeref = document.getElementById("place");
 placeref.innerHTML = "";
 a = parseInt(document.f.numA.value);
 n = parseInt(document.f.numn.value);
 d = gcd(a,n);
 b = parseInt(document.f.numB.value);
 if ((b % d)==0) {
  placeref.innerHTML="Solvable";
  //now to solve it
  a = a / d;
  b = b / d;
  n = n / d;
  //determine a solution
  messages = "Solving "+String(a)+"x = "+String(b)+    " (mod "+String(n)+") <br/>";
  placeref.innerHTML = messages;
  k=-1;
  do {
   k++;
   f = (k*n+b);
   r = f % a;

   // also trying -k. Note when k is zero, this is //redundant
   kk = -k;
   ff = (kk*n+b);
   rr = ff % a;
  }
  while ((r!=0) && (rr!=0));
  if (r==0) {
   x = f / a;
  }
  else {
   x = ff / a;
  }
  if (d==1) {
    messages+="<br/> Unique solution (mod "+
       String(n)+") is " +String(x);
    placeref.innerHTML = messages;
  }
  else {
   messages+= "<br/> Initial solution x0 is "+String(x);
   placeref.innerHTML = messages;
  
   for (j=1;j<d;j++){
   x = x+n;
   messages+="<br/> Another solution is "+String(x);
   placeref.innerHTML = messages;
   }
  }
  return false;
 }
 else {
  placeref.innerHTML="not solvable";
 
 }
 return false;
}
function gcd(a,b){
 var holder;
 var r;
 if (b < a) {

  //switch
  
  holder = a;
  a = b;
  b = holder;
 }
 r = b % a;
 if (r==0){
   
   return a;
 }
 
 else {
   return gcd(r,a);
 
 }
}
 
 
</script>
</head>
<body>
Enter 3 integers for mod equation ax = b mod(n) <br/>
<form name="f" onsubmit="return solvable();">
 a: <input type="number" name="numA" value=""/>  
 b: <input type="number" name="numB" value=""/>  
 n: <input type="number" name="numn" value=""/><br/>
 <input type="submit" value="Enter"/>
</form>
<p id="place">
 Messages will go here.
</p>
</body>
</html>