Chapter 4

Elementary Number Theory

4.1 Division algorithm and its applications

In this section, we study some properties of integers. We start with the ‘division algorithm’.

Lemma 4.1.1. [Division algorithm] Let a and b be two integers with b > 0. Then there exist unique
integers q, r such that a = qb + r, where 0 ≤ r < b. The integer q is called the quotient and r, the
remainder.

Proof. Existence: Take S = {a + bx|x ∈ Z} ∩ W. Then a + |a|b ∈ S. Hence, S is a nonempty subset

of W. Therefore, by the well ordering principle, S contains its minimum, say s0. So, s0 = a + bx0, for
some x0 ∈ Z. Since s0 ∈ W, s0 ≥ 0.
If s0 ≥ b then 0 ≤ s0 − b = a + b(x0 − 1) ∈ S. This contradicts the minimality of s0. Hence
0 ≤ s0 < b. Take q = −x0 and r = s0. Then qb + r = −x0b + s0 = −x0b + a + bx0 = a, i.e., we have
obtained q and r such that a = qb + r with 0 ≤ r < b.
Uniqueness: Assume that there exist integers q1, q2, r1 and r2 satisfying a = q1b + r1, 0 ≤ r1 < b,
a = q2b+r2, and 0 ≤ r2 < b. Suppose r1 < r2. Then 0 < r2−r1 < b. Notice that r2−r1 = (q1−q2)b. So,
0 < (q1 − q2)b < b. This is a contradiction since (0, b) does not contain any integer which is a multiple
of b. Similarly, r2 < r1 leads to a contradiction. Therefore, r1 = r2. Then, 0 = r1 − r2 = (q1 − q2)b
and b ƒ= 0 imply that q1 = q2.

Definition 4.1.2. Let a, b ∈ Z with b ƒ= 0. If a = bc, for some c ∈ Z then b is said to divide a and
we write b|a (read as b divides a. ) When b|a, we also say that b is a divisor of a, and that a is a
multiple of b.

Remark 4.1.3. Let a be a nonzero integer. If b is a positive divisor of a, then 1 ≤ b ≤ |a|. Hence the
set of all positive divisors of a nonzero integer is a nonempty finite set.
Further, if a is a positive integer and b is a positive divisor of a, then a = kb for some k ∈ N so
that b ≤ a. It then follows that if a, b ∈ N such that a|b and b|a, then a = b.

Definition 4.1.4. 1. Let a and b be two nonzero integers. Then the set S of their common positive
divisors is nonempty and finite. Thus, S contains its greatest element. This element is called
the greatest common divisor of a and b and is denoted by gcd(a, b). The gcd is also called
the highest common factor.

2. An integer a is said to be relatively prime to an integer b if gcd(a, b) = 1. In this case, we also

say that the integers a and b are coprimes.

61
 The next result is often stated as ‘the gcd(a, b) is a linear combination of a and b’.

Theorem 4.1.5. [Bézout’s identity] Let a and b be two nonzero integers and let d = gcd(a, b).
Then there exist integers x0, y0 such that d = ax0 + by0.

Proof. Consider the set S = {ax + by : x, y ∈ Z} ∩ N. Then, either a ∈ S or −a ∈ S. Thus, S is a

nonempty subset of N. By the well ordering principle, S contains its least element, say d. As d ∈ S,
we have d = ax0 + by0, for some x0, y0 ∈ Z. We show that d = gcd(a, b).
By the division algorithm, there exist integers q and r such that a = dq + r, with 0 ≤ r < d. If
r > 0, then

r = a − dq = a − q(ax0 + by0) = a(1 − qx0) + b(−qy0) ∈ {ax + by : x, y ∈ Z}.

In this case, r is a positive integer in S which is strictly less than d. This contradicts the choice of d
as the least element of S. Thus, r = 0. Consequently, d|a. Similarly, d|b. Hence d ≤ gcd(a, b).
Now, gcd(a, b)|a and gcd(a, b)|b. Since d = ax0 + by0 for some x0, y0 ∈ Z, we have gcd(a, b)|d.
That is, d = k × gcd(a, b) for some integer k. However, both gcd(a, b) and d are positive. Thus k is a
positive integer. Hence d ≥ gcd(a, b).
Therefore, d = gcd(a, b).

We prove three useful corollaries to Bézout’s identity.

Corollary 4.1.6. Let a, b ∈ Z and let d ∈ N. Then, d = gcd(a, b) if and only if d|a, d|b, and each
common divisor of a and b divides d.

Proof. Suppose d = gcd(a, b). Then d|a and d|b. By Bézout’s identity, d = ak + bm for some k, m ∈ Z.
Thus, any common divisor of a and b divides d = gcd(a, b).
Conversely, suppose d|a, d|b and each common divisor of a and b divides d. Since d is a common
divisor of a and b, by what we have just proved, d| gcd(a, b). Further, gcd(a, b) is a common divisor of
a and b; so, by assumption gcd(a, b)|d. By Remark 4.1.3, d = gcd(a, b).

Corollary 4.1.7. Let a, b be nonzero integers. Then gcd(a, b) = 1 if and only if there exist integers
x0 and y0 such that ax0 + by0 = 1.

Proof. If gcd(a, b) = 1, then by Bézout’s identity, there exist integers x0 and y0 such that ax0 +by0 = 1.
Conversely, suppose there exist integers x0 and y0 such that ax0 + by0 = 1. If gcd(a, b) = k, then k is
a positive integer such that k|1. It follows that k ≤ 1; consequently, k = 1.

Corollary 4.1.8. Let n1, . . . , nk be positive integers which are pairwise coprimes. If a ∈ Z is such
that n1|a, . . . , nk|a, then n1 · · · nk|a.

Proof. The positive integers n1, . . . , nk are pair wise coprimes means that if i ƒ= j, then gcd(ni, nj ) = 1.
Let a ∈ Z be such that n1|a, . . . , nk|a. We show by induction that n1 · · · nk|a. For k = 2, it is given
that n1 |a, n2 |a and gcd(n1 , n2 ) = 1. By Bézout’s identity, there exist x, y ∈ Z such that n1 x+n2 y = 1.
. Σa
Multiplying by a, we have a = an1x + an2y = n1n2 x( n ) + y( na ) .
. 2
Σ1

Since n2|a and n1|a, we see that a ,n a ∈nZ so that x( a ) + y(

2 1 n 2
a
) ∈nZ. Hence n1n2|a.
1

Assume the induction hypothesis that the statement is true for k = m. Let each of n1, . . . , nm+1
divide a and that they are pairwise coprimes. Let n1 · · · nm = A. Then gcd(A, nm+1) = 1. By the
induction hypothesis, A|a. By the basis case, (k = 2 as proved), we conclude that A nm+1|a. That is,
n1 · · · nm+1|a.
4.1. DIVISION ALGORITHM AND ITS APPLICATIONS 63

The division algorithm helps to algorithmically compute the greatest common divisor of two
nonzero integers, commonly known as the Euclid’s algorithm.
Let a, and b be nonzero integers. By the division algorithm, there exists integers q and r with
0 ≤ r < |b| such that a = |b|q + r. We apply our observation that a common divisor of two integers
divides their gcd.
Now, gcd(|b|, r) divides both |b| and r; hence it divides a. Again, gcd(|b|, r) divides both a and |b|.
Hence gcd(|b|, r)| gcd(a, |b|).
Similarly, with r = a − |b|q, we see that gcd(a, |b|) divides both a and |b|; hence gcd(a, |b|)|r.
Consequently, gcd(a, |b|)| gcd(|b|, r).
Further, the gcd of any two integers is positive. Thus, gcd(a, b) = gcd(a, |b|). So, we obtain

gcd(a, b) = gcd(a, |b|) = gcd(|b|, r).

Euclid’s algorithm applies this idea repeatedly to find the greatest common divisor of two given
nonzero integers, which we now present.

Euclid’s algorithm
Input: Two nonzero integers a and b; Output: gcd(a, b).

a = b q0 + r0 with 0≤ r0 < b
b = r0 q1 + r1 with 0≤ r1 < r0
r0 = r1 q2 + r2 with 0≤ r2 < r1
r1 = r2 q3 + r3 with 0≤ r3 < r2
.
rA−1 = rA qA+1 + rA+1 with 0 ≤ rA+1 < rA
rA = rA+1 qA+2.
gcd(a, b) = rA+1

The process will take at most b − 1 steps as 0 ≤ r0 < b. Also, note that rA+1 can be expressed in
the form rA+1 = a x0 + b y0 for integers x0, y0 using backtracking. That is,

rA+1 = rA−1 − rAqA+1 = rA−1 − qA+1 (rA−2 − rA−1qA) = rA−1 (1 + qA+1qA) − qA+1rA−2 = · · · .

Example 4.1.9. We apply Euclid’s algorithm for computing gcd(155, −275) as follows.

−275 = (−2) · 155 + 35 (so, gcd(−275, 155) = gcd(155, 35))

155 = 4 · 35 + 15 (so, gcd(155, 35) = gcd(35, 15))
35 = 2 · 15 + 5 (so, gcd(35, 15) = gcd(15, 5))
15 = 3·5 (so, gcd(15, 5) = 5).

To write 5 = gcd(155, −275) in the form 155x0 + (−275)y0, notice that

5 = 35 − 2 · 15 = 35 − 2(155 − 4 · 35) = 9 · 35 − 2 · 155 = 9(−275 + 2 · 155) − 2 · 155 = 9 · (−275) + 16 · 155.

Also, note that 275 = 5 · 55 and 155 = 5 · 31 and thus, 5 = (9 + 31x) · (−275) + (16 + 55x) · 155, for all
x ∈ Z. Therefore, we see that there are infinite number of choices for the pair (x, y) ∈ Z2, for which
d = ax + by.
EXERCISE 4.1.10. 1. Let a, b ∈ N with gcd(a, b) = d. Then gcd( ad, bd) = 1.
2. Prove that the system 15x + 12y = b has a solution for x, y ∈ Z if and only if 3 divides b.
4.2. MODULAR ARITHMETIC

3. [Linear Diophantine equation] Let a, b, c ∈ Z \ {0}. Then the linear system ax + by = c, in

the unknowns x, y ∈ Z has a solution if and only if gcd(a, b) divides c. Furthermore, determine
all pairs (x, y) ∈ Z × Z such that ax + by is indeed c.
4. Prove that gcd(a, bc) = 1 if and only if gcd(a, b) = 1 and gcd(a, c) = 1, for any three nonzero
integers a, b and c.
5. Euclid’s algorithm can sometimes be applied to check whether two numbers which are dependent
on an unknown integer n, are relatively prime or not. For example, we can use the algorithm to
prove that gcd(2n + 3, 5n + 7) = 1 for every n ∈ Z.
6. Suppose a milkman has only 3 cans of sizes 7, 9 and 16 liters. What is the minimum number of
operations required to deliver 1 liter of milk to a customer? Explain.

To proceed further, we need the following definitions.

Definition 4.1.11. 1. The integer 1 is called the unity (or the unit element) of Z.
2. An integer p > 1 is called a prime, if p has exactly two positive divisors, namely, 1 and p.
3. An integer r > 1 is called composite if r is not a prime.

We are now ready to prove an important result that helps us in proving the fundamental theorem
of arithmetic.

Lemma 4.1.12. [Euclid’s Lemma] Let a, b ∈ Z and let p be a prime. If p|ab then p|a or p|b.

Proof. Suppose p|ab. If p|a, then there is nothing to prove. So, assume that p ‡ a. As p is a prime,
gcd(p, a) = 1. Thus there exist integers x, y such that 1 = ax + py. Then b = abx + pby. Since p|ab
and p|pb, we see that p|b.

One also has the following result.

Proposition 4.1.13. Let a, b, n ∈ Z be such that n|ab. If gcd(n, a) = 1, then n|b.

Proof. Suppose gcd(n, a) = 1. There exist x0, y0 ∈ Z such that nx0 + ay0 = 1. Then b = aby0 + nbx0.
Since n|ab and n|nb, we have n|b.
Now, we are ready to prove the fundamental theorem of arithmetic that states that ‘every positive
integer greater than 1 is either a prime or is a product of primes. This product is unique, except for
the order in which the prime factors appear’.

Theorem 4.1.14. [Fundamental theorem of arithmetic] Let n ∈ N with n ≥ 2. Then there exist
prime numbers p1 > p2 > · · · > pk and positive integers s1, s2, . . . , sk such that n = p s1p1 ·2s·2 · p ,kfor
sk

some k ≥ 1. Moreover, if n also equals q t11 qt22 · · · q tAÆ , for distinct primes q1 > q2 > · · · > qA and positive
integers t1, t2, . . . , tA then k = A and for each i ∈ {1, . . . , k}, pi = qi and si = ti.

Proof. See Example 2.2.6 for a proof.

Theorem 4.1.15. [Euclid: Infinitude of primes] The number of primes is infinite.

Proof. On the contrary assume that the number of primes is finite, say p1 = 2, p2 = 3, . . . , pk. Consider
the positive integer N = p1p2 · · · pk + 1. We see that none of the primes p1, p2, . . . , pk divides N . This
contradicts Theorem 4.1.14.
√
Proposition 4.1.16. [Primality testing] Let n ∈ N with n ≥ 2. If no prime p ≤ n divides n, then
n is prime.
4.2. MODULAR ARITHMETIC

√ √
Proof. Suppose n = xy, for 2 ≤ x, y < n. Then, either x ≤ n or y ≤ n. Without loss of generality,
√ √
assume x ≤ n. If x is a prime, we are done. Else, take a prime divisor p of x. Now, p ≤ n and p
divides n.

EXERCISE 4.1.17. 1. Prove that there are infinitely many primes of the form 4n − 1.
2. Fix N ∈ N, N ≥ 2. Then, there exists a consecutive set of N natural numbers that are composite.
Definition 4.1.18. The least common multiple of integers a and b, denoted as lcm(a, b), is the
smallest positive integer that is a multiple of both a and b.

Lemma 4.1.19. Let a, b ∈ Z and let A ∈ N. Then, A = lcm(a, b) if and only if a|A, b|A and A divides
each common multiple of a and b.

Proof. Let A = lcm(a, b). Clearly, a|A and b|A. Let x be a common multiple of both a and b. If A ‡ x,
then by the division algorithm, x = A · q + r for some integer q and some r with 0 < r < A. Notice that
a|x and a|A. So, a|r. Similarly, b|r. That is, r is a positive common multiple of both a and b which is
less than lcm(a, b). This is a contradiction. Hence, A = lcm(a, b) divides each common multiple of a
and b.
Conversely, suppose a|A, b|A and A divides each common multiple of a and b. By what we have
just proved, lcm(a, b)|A. Further, lcm(a, b) is a common multiple of a and b. Thus A| lcm(a, b). By
Remark 4.1.3, we conclude that A = lcm(a, b).

Theorem 4.1.20. Let a, b ∈ N. Then gcd(a, b) · lcm(a, b) = ab. In particular, lcm(a, b) = ab if and
only if gcd(a, b) = 1.

Proof. Let d = gcd(a, b). Then a = a1d and b = b1d for some a1, b1 ∈ N. Further,

ab = a1d b1d = (a1b1d) · gcd(a, b).

Thus, it is enough to show that lcm(a, b) = a1b1d.

Towards this, notice that a1b1d = ab1 = a1b, that is, a|a1b1d and b|a1b1d. Let c ∈ N be any
common multiple of a and b. Then c , c ∈ Z. Further, by Bézout’s identity, d = as + bt for some
ab
s, t ∈ Z. So,
c cd c(as + bt) c c
= = = s + t ∈ Z.
a 1b1 d (a1d) · (b1d) ab b a
Hence a1b1d|c. That is, a1b1d divides each common multiple of a and b. By Lemma 4.1.19,
a1b1d = lcm(a, b).

4.2 Modular arithmetic

Definition 4.2.1. Fix a positive integer n. Let a, b ∈ Z. If n divides a−b, we say that a is congruent
to b modulo n, and write a ≡ b (mod n).

Example 4.2.2. 1. Notice that 2|(2k − 2m) and also 2|[(2k − 1) − (2m − 1)]. Therefore, any two
even integers are congruent modulo 2; and any two odd integers are congruent modulo 2.
2. The numbers ±10 and 22 are congruent modulo 4 as 4|(22 − 10) and 4|(22 − (−10)).
3. Let n be a fixed positive integer. Recall the notation [n − 1] := {0, 1, 2, . . . , n − 1}.
(a) Then, by the division algorithm, for any a ∈ Z there exists a unique b ∈ [n − 1] such that
a ≡ b (mod n). The number b is called the residue of a modulo n.
4.2. MODULAR ARITHMETIC

S
n−1
(b) Further Z = {a + kn : k ∈ Z}, i.e., every integer is congruent to an element of [n − 1].
a=0
The set [n − 1] is taken as the standard representative for the set of residue classes
modulo n.

Theorem 4.2.3. Fix n ∈ N, and let a, b, c, d ∈ Z. Then the following are true:
1. If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n).
2. If a ≡ b (mod n), then a + c ≡ b + c (mod n), a − c ≡ b − c (mod n) and ac ≡ bc (mod n).
3. If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ b + d (mod n), a − c ≡ b − d (mod n) and
ac ≡ bd (mod n). In particular, a ≡ b (mod n) implies am ≡ bm (mod n) for all m ∈ N.
4. If ac ≡ bc (mod n) for nonzero a, b, c, and d = gcd(c, n), then a ≡ b (mod n/d). In particular,
if ac ≡ bc (mod n) for nonzero a, b, c, and gcd(c, n) = 1, then a ≡ b (mod n).

Proof. We will only prove two parts. The readers should supply the proof of other parts.
3. Note that ac − bd = ac − bc + bc − bd = c(a − b) + b(c − d). Thus, n|ac − bd, whenever n|a − b
and n|c − d. In particular, taking c = a and d = b and repeatedly applying the above result, one has
am ≡ bm (mod n), for all m ∈ N.

4. Let gcd(c, n) = d. Then, there exist nonzero c1, n1 ∈ Z with c = c1d, n = n1d. Then n|ac − bc
implies n1d|c1d(a − b), which implies n1|c1(a − b). By Proposition 4.1.13, n1|a − b, i.e.,gcd(c,n)
n
|a − b.

Example 4.2.4. 1. Note that 3 · 9 + 13 · (−2) ≡ 1 (mod 13). If x satisfies 9x ≡ 4 (mod 13) then

x ≡ x · 1 ≡ x · (3 · 9 + 13 · (−2)) as 3 · 9 + 13 · (−2) ≡ 1 (mod 13)

≡ 3 · 9x as 13 ≡ 0 (mod 13)
≡ 3·4 as 9x ≡ 4 (mod 13)
≡ 12 (mod 13).

To verify, if x ≡ 12 (mod 13), then 9x ≡ 108 ≡ (13 × 8 + 4) ≡ 4 (mod 13). Therefore, the
congruence equation 9x ≡ 4 (mod 13) has solution x ≡ 12 (mod 13).
2. Verify that 9 · (−5) + 23 · (2) = 1. Hence, the equation 9x ≡ 1 (mod 23) has the solution

x ≡ x · 1 ≡ x (9 · (−5) + 23 · (2)) ≡ (−5) · (9x) ≡ −5 × 1 ≡ 18 (mod 23).

3. Verify that the equation 3x ≡ 15 (mod 30) has solutions x = 5, 15, 25; where as the equation
7x = 15 (mod 30) has only one solution x = 15; and that the equation 3x ≡ 5 (mod 30) has no
solution.

Theorem 4.2.5. [Linear Congruence] Let n be a positive integer and let a, b be nonzero integers.
Then the congruence equation ax ≡ b (mod n) has at least one solution if and only if gcd(a, n)|b.
Moreover, if d = gcd(a, n)|b, then ax ≡ b (mod n) has exactly d number of solutions r1, . . . , rd ∈
{0, 1, 2, . . . , n − 1}, where ri ≡ rj (mod n/d) for all i, j = 1, 2, . . . , d.

Proof. Write d = gcd(a, n). Let x0 be a solution of ax ≡ b (mod n). Then, by definition, ax0 − b = nq,
for some q ∈ Z. Thus, b = ax0 − nq. Since d|a and d|n, we have d|ax0 − nq = b.
Conversely, suppose d|b. Then, b = b1 d, for some b1 ∈ Z. By Bézout’s identity, there exist
x0, y0 ∈ Z such that ax0 + ny0 = d. Hence,

a(x0b1) ≡ b1(ax0) ≡ b1(ax0 + ny0) ≡ b1d ≡ b (mod n).

4.2. MODULAR ARITHMETIC

That is, x0b1 is a solution of ax ≡ b (mod n). This proves the first statement.
To proceed further, assume that d|b. By what we have just proved, there exists a solution x1 of
ax ≡ b (mod n). By the division algorithm, there exist p, r ∈ Z with 0 ≤ r < n such that x1 = pn + r.
Now, ar ≡ a(x1 − pn) ≡ ax1 ≡ b (mod n). Thus, r is also a solution of ax ≡ b (mod n), i.e., there
exists r ∈ {0, 1 . . . , n − 1} satisfying ar ≡ b (mod n).
If x2 ∈ {0, 1, . . . , n − 1} is any other solution of ax ≡ b (mod n), then ax2 ≡ b ≡ ar (mod n).
Thus, by Theorem [Link], x2 ≡ r (mod n/d). Conversely, if x2 ≡ r (mod n/d), then x2 = r + m(n/d)
for some m ∈ Z. Then ax2 = ar + am(n/d) = ar + mn(a/d). as d|a, the number a/d is an integer.
Hence, ax2 ≡ ar (mod n) so that x2 is a solution of ax ≡ b (mod n).
Therefore, all solutions of ax ≡ b (mod n) in {0, 1, . . . , n − 1} are of the form r + k(n/d) for k ∈ Z.
However, there are exactly d number of integers in {0, 1, . . . , n − 1} which are congruent to r modulo
(n/d). Hence there are d number of solutions of ax ≡ b (mod n) in {0, 1, . . . , n − 1}.

Remark 4.2.6. Observe that a solution of the congruence ax ≡ b (mod n) is a number in {0, 1, . . . , n−
1}. This set is not to be confused with the congruence class [n − 1]. When d = gcd(a, n), we may write
the distinct solutions in [n − 1] in increasing order as r1 = r, r2 = r + n/d, r3 = r + 2n/d, . . . , rd =
r + (d − 1)n/d. It means that the solutions are xi ≡ ri (mod n) for i = 1, 2, . . . , d.

EXERCISE 4.2.7. 1. Complete the proof of Theorem 4.2.3.

2. Determine the solutions of the system 3x ≡ 5 (mod 65).
3. Determine the solutions of the system 5x ≡ 95 (mod 100).
4. Prove that the system 3x ≡ 4 (mod 28) is equivalent to the system x ≡ 20 (mod 28).
5. Consider the congruence pair 3x ≡ 4 (mod 28) and 4x ≡ 2 (mod 27).
(a) Prove that the given pair is equivalent to the pair x ≡ 20 (mod 28) and x ≡ 14 (mod 27).
(b) Prove that solving the congruence pair in (a) is equivalent to solving one of the congruences
20 + 28k ≡ 14 (mod 27) or 14 + 27k ≡ 20 (mod 28) for the unknown quantity k.
(c) Verify that k = 21 is the solution for the first case in (b) and k = 22 for the second case.
(d) Conclude that x = 20 + 28 · 21 = 14 + 27 · 22 is a solution for the given congruence pair.
p!
6. Prove that if p is a prime, then p|C(p, k) := for 1 ≤ k ≤ p − 1.
k!(p − k)!

7. Let p be a prime. Write Zp := {0, 1, 2, . . . , p − 1} and Z∗p := {1, 2, . . . , p − 1} = Zp \ {0}. Show

that Zp has the following properties:
(a) For all a, b ∈ Zp, a + b (mod p) ∈ Zp.
(b) For all a, b ∈ Zp, a + b = b + a (mod p).
(c) For all a, b, c ∈ Zp, a + (b + c) ≡ (a + b) + c (mod p).
(d) For all a ∈ Zp, a + 0 ≡ a (mod p).
(e) For all a ∈ Zp, a + (p − a) ≡ 0 (mod p).
(f ) For all a, b ∈ Z∗p , a · b (mod p) ∈ Z∗p .
(g) For all a, b ∈ Z∗p , a · b = b · a (mod p).
(h) For all a, b, c ∈ Z∗p , a · (b · c) ≡ (a · b) · c (mod p).
(i) For all a ∈ Z∗p , a · 1 ≡ a (mod p).
(j) For each a ∈ Z∗p , there exists b ∈ Z∗p such that a · b ≡ 1 (mod p).
4.2. MODULAR ARITHMETIC

(k) For all a, b, c ∈ Zp, a · (b + c) ≡ (a · b) + (a · c) (mod p).

Any nonempty set containing at least two elements such as 0 and 1, in which ‘addition’ and
‘multiplication’ can be defined in such a way that the above properties are satisfied, is called a
field. So, Zp = {0, 1, 2, . . . , p − 1} is an example of a field. The well known examples of fields
are:
(a) Q, the set of rational numbers.
(b) R, the set of real numbers.
(c) C, the set of complex numbers.

8. Let p be an odd prime. Prove the following:

(a) The equation x2 ≡ 1 (mod p) has exactly two solutions in Zp.
(b) Corresponding to any a ∈ {2, 3, . . . , p − 2}, if there exists b ∈ Z∗p such that a · b ≡ 1 (mod p),
then b ∈ {2, 3, . . . , p − 2} and b ƒ= a.
(c) If a, b, c, d ∈ {2, 3, . . . , p − 2} satisfy a ƒ= c, a · b ≡ 1 (mod p) and c · d ≡ 1 (mod p), then
b ƒ= d.
(d) Let p > 3. Write q = (p − 3)/2. There exist two-element sets {a1 , b1 }, {a2 , b2 }, . . . , {aq , bq }
Sq
that are pairwise disjoint satisfying ai · bi ≡ 1 (mod p) for 1 ≤ i ≤ q, and {ai, bi } =
i=1
{2, 3, . . . , p − 2}.
(e) If p > 3, then 2 · 3 · · · · · (p − 2) ≡ 1 (mod p).

9. [Wilson’s Theorem] If p is any prime, then (p − 1)! ≡ −1 (mod p).

10. [Primality Testing] Any integer n > 1 is a prime if and only if (n − 1)! ≡ −1 (mod n).

4.3 Chinese Remainder Theorem

Theorem 4.3.1. [Chinese remainder theorem] Fix a positive integer m. Let n1, n2, . . . , nm be
pairwise coprime positive integers. Write M = n1n2 · · · nm. Then, the system of congruences

x ≡ a1 (mod n1)
x ≡ a2 (mod n2)
.
x ≡ am (mod n m)

has a unique solution modulo M .

M
Proof. For 1 ≤ k ≤ m, define Mk = . Then, gcd(Mk, nk) = 1 and hence there exist integers xk, yk
nk
such that Mkxk + nkyk = 1 for 1 ≤ k ≤ m. Let 1 ≤ i, j ≤ m. Then

M i xi ≡ M i xi + n i yi ≡ 1 (mod n i); i ƒ= j ⇒ ni|Mj ⇒ M j xj ≡ 0 (mod n i).

Σ
m
Now, x0 := Mkxkak ≡ Mixiai ≡ 1 · ai ≡ ai (mod ni). That is, x0 is a solution to the given
k=1
system of congruences.
If y0 is any solution to the system of congruences, then for each integer k with 0 ≤ k ≤ m, we have
y0 ≡ ak (mod nk) so that y0 − x0 ≡ ak − ak ≡ 0 (mod nk). Since n1, . . . , nk are pairwise coprimes and
their product is M , Corollary 4.1.8 implies that y0 − x0 ≡ 0 (mod M ). Therefore, x0 is the unique
solution of the system of congruences module M .
4.3. CHINESE REMAINDER THEOREM 69

Example 4.3.2. Consider the system of congruences x ≡ 20 (mod 28) and x ≡ 14 (mod 27) in
Exercise [Link]. In this case, a1 = 20, a2 = 14, n1 = 28 and n2 = 27 so that M = 28 · 27 = 756, M1 =
27 and M2 = 28. Then, x1 = −1 and x2 = 1 show that M1x1 + M2x2 = 27 · −1 + 28 · 1 = 1. Hence

x0 = 27 · −1 · 20 + 28 · 1 · 14 ≡ −540 + 392 ≡ −148 ≡ 608 (mod 756).

EXERCISE 4.3.3. 1. Find the smallest positive integer which when divided by 4 leaves a remainder
1 and when divided by 9 leaves a remainder 2.
2. Find the smallest positive integer which when divided by 8 leaves a remained 4 and when divided
by 15 leaves a remainder 10.
3. Does there exist a positive integer n such that n ≡ 4 (mod 14) and n ≡ 6 (mod 18)? Give
reasons for your answer. What if we replace 6 or 4 with an odd number?

4. Let n be a positive integer. Show that the set Zn := {0, 1, 2, . . . , n−1} has the following properties:

(a) For all a, b ∈ Zn, a + b (mod n) ∈ Zn.

(b) For all a, b ∈ Zn, a + b = b + a (mod n).
(c) For all a, b, c ∈ Zn, a + (b + c) ≡ (a + b) + c (mod n).
(d) For all a ∈ Zn, a + 0 ≡ a (mod n).
(e) For all a ∈ Zn, a + (n − a) ≡ 0 (mod n).
(f) For all a, b ∈ Zn, a · b (mod n) ∈ Zn.
(g) For all a, b ∈ Zn, a · b = b · a (mod n).
(h) For all a, b, c ∈ Zn, a · (b · c) ≡ (a · b) · c (mod n).
(i) For all a ∈ Zn, a · 1 ≡ a (mod n).
(j) For all a, b, c ∈ Zn, a · (b + c) ≡ (a · b) + (a · c) (mod n).

Any set, say R, with 0, 1 ∈ R, 0 ƒ= 1, in which ‘addition’ and ‘multiplication’ can be defined in
such a way that the above properties are satisfied, is called a commutative ring with unity.
So, Zn = {0, 1, 2, . . . , n − 1} is an example of a commutative ring with unity. The well known
examples of commutative ring with unity are:
(a) Z, the set of integers.
(b) Q, the set of rational numbers.
(c) R, the set of real numbers.
(d) C, the set of complex numbers.

5. Let m and n be two coprime positive integers. By Exercise [Link], the sets Zm, Zn, and Zmn are
commutative rings with unity. Now, define addition and multiplication in Zm × Zn component-
wise. Also, define the function

f : Zmn → Zm × Zn by f (x) = (x (mod m), x (mod n)) for all x ∈ Zmn.

Then, prove the following:

(a) Zm × Zn is a commutative ring with unity. What are the 0 and 1 here?
(b) For all x, y ∈ Zmn, f (x + y) = f (x) + f (y).
(c) For all x, y ∈ Zmn, f (x · y) = f (x) · f (y).
(d) For each (a, b) ∈ Zm×Zn there exists a unique x ∈ Zmn such that x ≡ a (mod m)
and x ≡ b
(mod n).
(e) |Zm × Zn| = |Zmn| = mn.

Such a function f is called a ring isomorphism, and thus, the two rings Zm × Zn and
Zmn are isomorphic.