Residues#
Contents#
Residues#
RESIDUE CLASS MODULO M
Let \(m \in \mathbb{N}\) and define the residue class \(\bar{r} \text{ modulo } m\) by
\(\bar{r} = \{ x \in \mathbb{Z} : m \mid (x - r) \}\)
\( \begin{aligned} \bar{0} &= \{ x \in \mathbb{Z} : m \mid x \} && \text{residue class } \bar{0} \mod m \\ \bar{1} &= \{ x \in \mathbb{Z} : m \mid (x - 1) \} && \text{residue class } \bar{1} \mod m \\ \bar{2} &= \{ x \in \mathbb{Z} : m \mid (x - 2) \} && \text{residue class } \bar{2} \mod m \\ \vdots \\ \overline{m - 1} &= \{ x \in \mathbb{Z} : m \mid (x - m + 1) \} && \text{residue class } \overline{m - 1} \mod m \\ \end {aligned} \)
COMPLETE SYSTEM OF RESIDUES MODULO M
By the division algorithm every integer is in one of
\(\overline{0}, \overline{1}, \dotsc, \overline{m - 1}\)
This is called a complete system of residues modulo \(m\).
Arithmetic can be performed on residue classes just as if they were numbers.
The residue class \(\bar{0}\) behaves like the number \(0\), since \(\bar{0}\) is the set of multiples of \(m\), and adding any one of them to an element of \(\bar{r}\) does not change the remainder.
Thus for any \(r\)
\(\bar{0} + \bar{r} = \bar{r} = \bar{r} + \bar{0}\)
Suppose we are given any two residue classes \(\bar{r}\) and \(\bar{s}\) modulo \(m\):
\( \begin{aligned} \bar{r} &= \{ x \in \mathbb{Z} : m \mid (x - r) \} \\ \bar{s} &= \{ y \in \mathbb{Z} : m \mid (y - r) \} \\ \end {aligned} \)
Let \(t\) be the remainder of \(r + s\) on division by \(m\):
\(r + s = mz + t\)
Then the elements of \(\bar{r}\) and \(\bar{s}\) are of the form \(r + mx\) and \(s + my\) and it is known that \(r + s = t + mz\) for some \(z\). Thus
\( \begin{aligned} r + mx + s + my = t + m(x + y + z) \in \bar{t} \end {aligned} \)
Thus it makes sense to write \(\bar{r} + \bar{s} = \bar{t}\) and then we have \(\bar{r} + \bar{s} = \bar{s} + \bar{r}\).
It is also the case that \(\overline{r} + \overline{-r} = \overline{0}\)
Reduced Residues#
THEOREM [Vaughan Theorem 3.]
Suppose that \(m \in \mathbb{N}\), \(k \in \mathbb{Z}\), \(\gcd(k, m) = 1\), and
\( \begin{aligned} \overline{a_1} &= \{ x \in \mathbb{Z} : m \mid (x - a_1) \} = \{ mx + a_1 : x \in \mathbb{Z} \} \\ \overline{a_2} &= \{ x \in \mathbb{Z} : m \mid (x - a_2) \} = \{ mx + a_2 : x \in \mathbb{Z} \} \\ \vdots \\ \overline{a_m} &= \{ x \in \mathbb{Z} : m \mid (x - a_m) \} = \{ mx + a_m : x \in \mathbb{Z} \} \end {aligned} \)
forms a complete system of residues modulo \(m\). Then so does
\( \begin{aligned} \overline{ka_1} &= \{ x \in \mathbb{Z} : m \mid (x - ka_1) \} = \{ mx + ka_1 : x \in \mathbb{Z} \} \\ \overline{ka_2} &= \{ x \in \mathbb{Z} : m \mid (x - ka_2) \} = \{ mx + ka_2 : x \in \mathbb{Z} \} \\ \vdots \\ \overline{ka_m} &= \{ x \in \mathbb{Z} : m \mid (x - ka_m) \} = \{ mx + ka_m : x \in \mathbb{Z} \} \end {aligned} \)
Proof
Since there are \(m\) residue classes it need only be checked that they are disjoint.
Consider any two residue classes \(\overline{ka_i}\) and \(\overline{ka_j}\) and let \(ka_i + mx\) and \(ka_j + my\) be typical members of each, respectively.
If they were the same integer then \(ka_i + mx = ka_j + my \iff ka_i - ka_j = my - mx \iff k(a_i - a_j) = m(y - x)\).
But then \(m \mid k(a_i - a_j)\) and since \(\gcd(k, m) = 1\) it would be the case that \(m \mid a_i - a_j\); that \(\overline{a_i}\) and \(\overline{a_j}\) be the same residue class; and that \(i = j\).
\(\blacksquare\)
EXAMPLE
\(\bar{0}, \bar{1}, \bar{2}\) is a complete system of residues modulo \(3\)
\( \begin{aligned} \bar{0} &= \{ x \in \mathbb{Z} : 3 \mid (x - 0) \} = \{ 3x \} \\ \bar{1} &= \{ x \in \mathbb{Z} : 3 \mid (x - 1) \} = \{ 3x + 1 \} \\ \bar{2} &= \{ x \in \mathbb{Z} : 3 \mid (x - 2) \} = \{ 3x + 2 \} \\ \end {aligned} \)
\(\gcd(3, 2) = 1\)
\(\bar{0}, \bar{2}, \bar{4}\) is a complete system of residues modulo \(3\)
\( \begin{aligned} \bar{0} &= \{ x \in \mathbb{Z} : 3 \mid (x - 2.0) \} = \{ 3x \} \\ \bar{2} &= \{ x \in \mathbb{Z} : 3 \mid (x - 2.1) \} = \{ 3x + 2 \} \\ \bar{4} &= \{ x \in \mathbb{Z} : 3 \mid (x - 2.2) \} = \{ 3x + 4 \} = \{ 3(x + 1) + 1 \} \\ \end {aligned} \)
\(\gcd(3, 5) = 1\)
\(\bar{0}, \bar{5}, \bar{10}\) is a complete system of residues modulo \(3\)
\( \begin{aligned} \bar{ 0} &= \{ x \in \mathbb{Z} : 3 \mid (x - 5.0) \} = \{ 3x \} \\ \bar{ 5} &= \{ x \in \mathbb{Z} : 3 \mid (x - 5.1) \} = \{ 3x + 5 \} = \{ 3(x + 1) + 2 \} \\ \bar{10} &= \{ x \in \mathbb{Z} : 3 \mid (x - 5.2) \} = \{ 3x + 10 \} = \{ 3(x + 3) + 1 \} \\ \end {aligned} \)
Euler’s Totient Function#
TOTIENT FUNCTION
Euler’s totient function \(\phi(n)\) is the number of \(x \in \mathbb{N}\) with \(1 \le x \le n\) and \(\gcd(x, n) = 1\).
If \(p\) is prime then all the \(x\) with \(1 \le x \le p - 1\) satisfy \(\gcd(x, p) = 1\), but \(\gcd(p, p) = p \ne 1\). Thus \(\boxed{\phi(p) = p - 1}\).
Show code cell source
from math import gcd
def totient (n):
result = n
p = 2
while p * p <= n:
if n % p == 0: # if p divides n
while n % p == 0: # remove factors of p from n
n //= p
result -= result // p
p += 1
if n > 1: # gcd(n, n) != 1, so phi(n) < n for any n
result -= result // n
return result
def totatives (n):
return [x for x in range(1, n) if gcd(x, n) == 1]
for k in range(100):
t = totient(k)
tots = totatives(k)
print(f'\u03c6({k:>2}) = {t:>2}, totatives: {tots}')
φ( 0) = 0, totatives: []
φ( 1) = 1, totatives: []
φ( 2) = 1, totatives: [1]
φ( 3) = 2, totatives: [1, 2]
φ( 4) = 2, totatives: [1, 3]
φ( 5) = 4, totatives: [1, 2, 3, 4]
φ( 6) = 2, totatives: [1, 5]
φ( 7) = 6, totatives: [1, 2, 3, 4, 5, 6]
φ( 8) = 4, totatives: [1, 3, 5, 7]
φ( 9) = 6, totatives: [1, 2, 4, 5, 7, 8]
φ(10) = 4, totatives: [1, 3, 7, 9]
φ(11) = 10, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
φ(12) = 4, totatives: [1, 5, 7, 11]
φ(13) = 12, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
φ(14) = 6, totatives: [1, 3, 5, 9, 11, 13]
φ(15) = 8, totatives: [1, 2, 4, 7, 8, 11, 13, 14]
φ(16) = 8, totatives: [1, 3, 5, 7, 9, 11, 13, 15]
φ(17) = 16, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
φ(18) = 6, totatives: [1, 5, 7, 11, 13, 17]
φ(19) = 18, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
φ(20) = 8, totatives: [1, 3, 7, 9, 11, 13, 17, 19]
φ(21) = 12, totatives: [1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20]
φ(22) = 10, totatives: [1, 3, 5, 7, 9, 13, 15, 17, 19, 21]
φ(23) = 22, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
φ(24) = 8, totatives: [1, 5, 7, 11, 13, 17, 19, 23]
φ(25) = 20, totatives: [1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24]
φ(26) = 12, totatives: [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]
φ(27) = 18, totatives: [1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26]
φ(28) = 12, totatives: [1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27]
φ(29) = 28, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28]
φ(30) = 8, totatives: [1, 7, 11, 13, 17, 19, 23, 29]
φ(31) = 30, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
φ(32) = 16, totatives: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31]
φ(33) = 20, totatives: [1, 2, 4, 5, 7, 8, 10, 13, 14, 16, 17, 19, 20, 23, 25, 26, 28, 29, 31, 32]
φ(34) = 16, totatives: [1, 3, 5, 7, 9, 11, 13, 15, 19, 21, 23, 25, 27, 29, 31, 33]
φ(35) = 24, totatives: [1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34]
φ(36) = 12, totatives: [1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35]
φ(37) = 36, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36]
φ(38) = 18, totatives: [1, 3, 5, 7, 9, 11, 13, 15, 17, 21, 23, 25, 27, 29, 31, 33, 35, 37]
φ(39) = 24, totatives: [1, 2, 4, 5, 7, 8, 10, 11, 14, 16, 17, 19, 20, 22, 23, 25, 28, 29, 31, 32, 34, 35, 37, 38]
φ(40) = 16, totatives: [1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39]
φ(41) = 40, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40]
φ(42) = 12, totatives: [1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41]
φ(43) = 42, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42]
φ(44) = 20, totatives: [1, 3, 5, 7, 9, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 35, 37, 39, 41, 43]
φ(45) = 24, totatives: [1, 2, 4, 7, 8, 11, 13, 14, 16, 17, 19, 22, 23, 26, 28, 29, 31, 32, 34, 37, 38, 41, 43, 44]
φ(46) = 22, totatives: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45]
φ(47) = 46, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46]
φ(48) = 16, totatives: [1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47]
φ(49) = 42, totatives: [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 33, 34, 36, 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 48]
φ(50) = 20, totatives: [1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49]
φ(51) = 32, totatives: [1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 50]
φ(52) = 24, totatives: [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 41, 43, 45, 47, 49, 51]
φ(53) = 52, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52]
φ(54) = 18, totatives: [1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53]
φ(55) = 40, totatives: [1, 2, 3, 4, 6, 7, 8, 9, 12, 13, 14, 16, 17, 18, 19, 21, 23, 24, 26, 27, 28, 29, 31, 32, 34, 36, 37, 38, 39, 41, 42, 43, 46, 47, 48, 49, 51, 52, 53, 54]
φ(56) = 24, totatives: [1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27, 29, 31, 33, 37, 39, 41, 43, 45, 47, 51, 53, 55]
φ(57) = 36, totatives: [1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 40, 41, 43, 44, 46, 47, 49, 50, 52, 53, 55, 56]
φ(58) = 28, totatives: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57]
φ(59) = 58, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58]
φ(60) = 16, totatives: [1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59]
φ(61) = 60, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60]
φ(62) = 30, totatives: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61]
φ(63) = 36, totatives: [1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20, 22, 23, 25, 26, 29, 31, 32, 34, 37, 38, 40, 41, 43, 44, 46, 47, 50, 52, 53, 55, 58, 59, 61, 62]
φ(64) = 32, totatives: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63]
φ(65) = 48, totatives: [1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 16, 17, 18, 19, 21, 22, 23, 24, 27, 28, 29, 31, 32, 33, 34, 36, 37, 38, 41, 42, 43, 44, 46, 47, 48, 49, 51, 53, 54, 56, 57, 58, 59, 61, 62, 63, 64]
φ(66) = 20, totatives: [1, 5, 7, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 59, 61, 65]
φ(67) = 66, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66]
φ(68) = 32, totatives: [1, 3, 5, 7, 9, 11, 13, 15, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 53, 55, 57, 59, 61, 63, 65, 67]
φ(69) = 44, totatives: [1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 47, 49, 50, 52, 53, 55, 56, 58, 59, 61, 62, 64, 65, 67, 68]
φ(70) = 24, totatives: [1, 3, 9, 11, 13, 17, 19, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 51, 53, 57, 59, 61, 67, 69]
φ(71) = 70, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70]
φ(72) = 24, totatives: [1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71]
φ(73) = 72, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72]
φ(74) = 36, totatives: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73]
φ(75) = 40, totatives: [1, 2, 4, 7, 8, 11, 13, 14, 16, 17, 19, 22, 23, 26, 28, 29, 31, 32, 34, 37, 38, 41, 43, 44, 46, 47, 49, 52, 53, 56, 58, 59, 61, 62, 64, 67, 68, 71, 73, 74]
φ(76) = 36, totatives: [1, 3, 5, 7, 9, 11, 13, 15, 17, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 59, 61, 63, 65, 67, 69, 71, 73, 75]
φ(77) = 60, totatives: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 15, 16, 17, 18, 19, 20, 23, 24, 25, 26, 27, 29, 30, 31, 32, 34, 36, 37, 38, 39, 40, 41, 43, 45, 46, 47, 48, 50, 51, 52, 53, 54, 57, 58, 59, 60, 61, 62, 64, 65, 67, 68, 69, 71, 72, 73, 74, 75, 76]
φ(78) = 24, totatives: [1, 5, 7, 11, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 67, 71, 73, 77]
φ(79) = 78, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78]
φ(80) = 32, totatives: [1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49, 51, 53, 57, 59, 61, 63, 67, 69, 71, 73, 77, 79]
φ(81) = 54, totatives: [1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 50, 52, 53, 55, 56, 58, 59, 61, 62, 64, 65, 67, 68, 70, 71, 73, 74, 76, 77, 79, 80]
φ(82) = 40, totatives: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81]
φ(83) = 82, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82]
φ(84) = 24, totatives: [1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 53, 55, 59, 61, 65, 67, 71, 73, 79, 83]
φ(85) = 64, totatives: [1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 18, 19, 21, 22, 23, 24, 26, 27, 28, 29, 31, 32, 33, 36, 37, 38, 39, 41, 42, 43, 44, 46, 47, 48, 49, 52, 53, 54, 56, 57, 58, 59, 61, 62, 63, 64, 66, 67, 69, 71, 72, 73, 74, 76, 77, 78, 79, 81, 82, 83, 84]
φ(86) = 42, totatives: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85]
φ(87) = 56, totatives: [1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 50, 52, 53, 55, 56, 59, 61, 62, 64, 65, 67, 68, 70, 71, 73, 74, 76, 77, 79, 80, 82, 83, 85, 86]
φ(88) = 40, totatives: [1, 3, 5, 7, 9, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 79, 81, 83, 85, 87]
φ(89) = 88, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88]
φ(90) = 24, totatives: [1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89]
φ(91) = 72, totatives: [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 27, 29, 30, 31, 32, 33, 34, 36, 37, 38, 40, 41, 43, 44, 45, 46, 47, 48, 50, 51, 53, 54, 55, 57, 58, 59, 60, 61, 62, 64, 66, 67, 68, 69, 71, 72, 73, 74, 75, 76, 79, 80, 81, 82, 83, 85, 86, 87, 88, 89, 90]
φ(92) = 44, totatives: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91]
φ(93) = 60, totatives: [1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 50, 52, 53, 55, 56, 58, 59, 61, 64, 65, 67, 68, 70, 71, 73, 74, 76, 77, 79, 80, 82, 83, 85, 86, 88, 89, 91, 92]
φ(94) = 46, totatives: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93]
φ(95) = 72, totatives: [1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 21, 22, 23, 24, 26, 27, 28, 29, 31, 32, 33, 34, 36, 37, 39, 41, 42, 43, 44, 46, 47, 48, 49, 51, 52, 53, 54, 56, 58, 59, 61, 62, 63, 64, 66, 67, 68, 69, 71, 72, 73, 74, 77, 78, 79, 81, 82, 83, 84, 86, 87, 88, 89, 91, 92, 93, 94]
φ(96) = 32, totatives: [1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95]
φ(97) = 96, totatives: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96]
φ(98) = 42, totatives: [1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27, 29, 31, 33, 37, 39, 41, 43, 45, 47, 51, 53, 55, 57, 59, 61, 65, 67, 69, 71, 73, 75, 79, 81, 83, 85, 87, 89, 93, 95, 97]
φ(99) = 60, totatives: [1, 2, 4, 5, 7, 8, 10, 13, 14, 16, 17, 19, 20, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 46, 47, 49, 50, 52, 53, 56, 58, 59, 61, 62, 64, 65, 67, 68, 70, 71, 73, 74, 76, 79, 80, 82, 83, 85, 86, 89, 91, 92, 94, 95, 97, 98]
SET OF REDUCED RESIDUES MODULO M
A set of \(\phi(m)\) distinct residue classes \(\bar{r}\) modulo \(m\) with \(\gcd(r, m) = 1\) is called a set of reduced residues modulo \(m\).
One way of thinking about reduced residues is to start from a complete set of fractions with denominator \(m\) in the interval \((0, 1]\)
\( \begin{aligned} \frac{1}{m}, \frac{2}{m}, \dotsc, \frac{m}{m} \end {aligned} \)
and remove just the ones whose numerator has a common factor \(d \gt 1\) with \(m\). What is left are the \(\phi(m)\) reduced fractions with denominator \(m\). Alternatively instead of removing the non-reduced ones we just write them in their lowest form. Then for each divisor \(k\) of \(m\) we obtain all the reduced fractions with denominator \(k\).
\( \begin{aligned} \frac{1}{30} && \frac{2}{30} && \frac{3}{30} && \frac{4}{30} && \frac{5}{30} && \frac{6}{30} && \frac{7}{30} && \frac{8}{30} && \frac{9}{30} && \frac{10}{30} && \frac{11}{30} && \frac{12}{30} && \frac{13}{30} && \frac{14}{30} && \frac{15}{30} && \frac{16}{30} && \frac{17}{30} && \frac{18}{30} && \frac{19}{30} && \frac{20}{30} && \frac{21}{30} && \frac{22}{30} && \frac{23}{30} && \frac{24}{30} && \frac{25}{30} && \frac{26}{30} && \frac{27}{30} && \frac{28}{30} && \frac{29}{30} && \frac{30}{30} \\ \\ \frac{1}{30} && && && && && && \frac{7}{30} && && && && \frac{11}{30} && && \frac{13}{30} && && && && \frac{17}{30} && && \frac{19}{30} && && && && \frac{23}{30} && && && && && && \frac{29}{30} && \\ \\ \frac{1}{30} && \frac{1}{15} && \frac{1}{10} && \frac{2}{15} && \frac{1}{6} && \frac{1}{5} && \frac{7}{30} && \frac{4}{15} && \frac{3}{10} && \frac{1}{3} && \frac{11}{30} && \frac{2}{5} && \frac{13}{30} && \frac{7}{15} && \frac{1}{2} && \frac{8}{15} && \frac{17}{30} && \frac{3}{5} && \frac{19}{30} && \frac{2}{3} && \frac{7}{10} && \frac{11}{15} && \frac{23}{30} && \frac{4}{5} && \frac{5}{6} && \frac{13}{15} && \frac{9}{10} && \frac{14}{15} && \frac{29}{30} && 1 \\ \end {aligned} \)
\( \begin{aligned} k &= 1 && 1 & \phi( 1) = 1 \\ k &= 2 && \frac{1}{ 2} & \phi( 2) = 1 \\ k &= 3 && \frac{1}{ 3}, \frac{2}{ 3} & \phi( 3) = 2 \\ k &= 5 && \frac{1}{ 5}, \frac{2}{ 5}, \frac{ 3}{ 5}, \frac{ 4}{ 5} & \phi( 5) = 4 \\ k &= 6 && \frac{1}{ 6}, \frac{5}{ 6} & \phi( 6) = 2 \\ k &= 10 && \frac{1}{10}, \frac{3}{10}, \frac{ 7}{10}, \frac{ 9}{10} & \phi(10) = 4 \\ k &= 15 && \frac{1}{15}, \frac{2}{15}, \frac{ 4}{15}, \frac{ 7}{15}, \frac{ 8}{15}, \frac{11}{15}, \frac{13}{15}, \frac{14}{15} & \phi(15) = 8 \\ k &= 30 && \frac{1}{30}, \frac{7}{30}, \frac{11}{30}, \frac{13}{30}, \frac{17}{30}, \frac{19}{30}, \frac{23}{30}, \frac{29}{30} & \phi(30) = 8 \\ \end {aligned} \)
\( \begin{aligned} \sum_{k \mid 30} \phi(k) = 30 = \phi(1) + \phi(2) + \phi(3) + \phi(5) + \phi(6) + \phi(10) + \phi(15) + \phi(30) \end {aligned} \)
THEOREM [Vaughan Theorem 3.7]
For each \(m \in \mathbb{N}\) we have
\( \begin{aligned} \sum_{k \mid m} \phi(k) = m = \phi(1) + \phi(2) + \dotsb + \phi(m) \end {aligned} \)
Proof
See the above.
\(\blacksquare\)
THEOREM [Vaughan Theorem 3.9]
Suppose that \(\gcd(k, m) = 1\) and that
\(a_1, a_2, \dotsc, a_{\phi(m)}\)
forms a set of reduced residue classes modulo \(m\). Then
\(ka_1, ka_2, \dotsc, ka_{\phi(m)}\)
also forms a set of reduced residue classes modulo \(m\).
Proof
In view of the earlier theorem the residue classes \(ka_j\) are distinct, and since \(\gcd(a_j, m) = 1\) it is the case that \((ka_j, m) = 1\), so they give \(\phi(m)\) distinct reduced residue classes. So they are all of them in some order.
\(\blacksquare\)
THEOREM [Vaughan Theorem 3.10]
Suppose \(m, n \in \mathbb{N}\) and \(\gcd(m, n) = 1\), and consider the \(xn + ym\) with \(1 \le x \le m\) and \(1 \le y \le n\). Then they form a complete set of residues modulo \(mn\). If in addition \(x\) and \(y\) satisfy \(\gcd(x, m) = 1\) and \(\gcd(y, n) = 1\) then they form a reduced set.
Proof
If \(xn + ym \equiv x'n + y'm \mod mn\) then \(xn \equiv x'n \mod m\), so \(x \equiv x' \mod m\), \(x = x'\). Likewise \(y = y'\). Hence in either case the \(xn + ym\) are distinct modulo \(mn\).
In the unrestricted case we have \(mn\) objects, so they form a coomplete set.
In the restricted case \(\gcd(xn + ym, m) = \gcd(xn, m) = \gcd(x, m) = 1\) and likewise \(\gcd(xn + ym, n) = 1\), so \(\gcd(xn + ym, mn) = 1\) and the \(xn + ym\) all belong to reduced residue classes.
Now let \(\gcd(z, mn) = 1\). Choose \(x', y', x, y\) so that
\( \begin{aligned} x'n + y'm &= 1 \\ x &\equiv x'z \mod m \\ y &\equiv y'z \mod n \\ \end {aligned} \)
Then \(xn + ym \equiv x'zn + y'zm = z \mod mn\) and hence every reduced residue is included.
\(\blacksquare\)
\(6x + 5y \mod 30\)
\( \begin{array}{cc|cccc|} & x & 1 & 2 & 3 & 4 & 5 \\ y & \\ \hline 1 & & 11 & 17 & 23 & 29 & 5 \\ \hline 2 & & 16 & 22 & 28 & 4 & 10 \\ 3 & & 21 & 27 & 3 & 9 & 15 \\ 4 & & 26 & 2 & 8 & 14 & 20 \\ \hline 5 & & 1 & 7 & 13 & 19 & 25 \\ \hline 6 & & 6 & 12 & 18 & 24 & 30 \\ \end {array} \)
The \(30\) numbers \(1\) through \(30\) each appear exactly once. The \(8\) reduced residue classes occur precisely in the intersection of rows \(1\) and \(5\) and columns \(1\) through \(4\).
\(\gcd(x = 1, 2, 3, 4, m = 5) = \gcd(y = 1, 5, n = 6)\)
THEOREM [Vaughan Corollary 3.12]
If \(\gcd(m, n) = 1\) then \(\phi(mn) = \phi(m) \phi(n)\).
\( \begin{aligned} \gcd( 1, n) = 1 && \phi( n) &= \phi( 1) \phi( n) &&= \phi(n) \\ \gcd( 2, n) = 1 && \phi( 2n) &= \phi( 2) \phi( n) &&= \phi(n) \\ \gcd( 3, n) = 1 && \phi( 3n) &= \phi( 3) \phi( n) &&= 2\phi(n) \\ \gcd( 4, n) = 1 && \phi( 4n) &= \phi( 4) \phi( n) &&= 2\phi(n) \\ \gcd( 5, n) = 1 && \phi( 5n) &= \phi( 5) \phi( n) &&= 4\phi(n) \\ \gcd( 6, n) = 1 && \phi( 6n) &= \phi( 6) \phi( n) &&= 2\phi(n) \\ \gcd( 7, n) = 1 && \phi( 7n) &= \phi( 7) \phi( n) &&= 6\phi(n) \\ \gcd( 8, n) = 1 && \phi( 8n) &= \phi( 8) \phi( n) &&= 4\phi(n) \\ \gcd( 9, n) = 1 && \phi( 9n) &= \phi( 9) \phi( n) &&= 6\phi(n) \\ \gcd(10, n) = 1 && \phi(10n) &= \phi(10) \phi( n) &&= 4\phi(n) \\ \end {aligned} \)
COROLLARY [Vaughan Corollary 3.14]
Euler’s function is multiplicative.
THEOREM [Vaughan Theorem 3.15]
If \(n = p^k\) then the number of reduced residue classes modulo \(p^k\) is the number of \(x\) with \(1 \le x \le p^k\) and \(p \nmid x\).
This is \(p^k - N\) where \(N\) is the number of \(x\) with \(1 \le x \le p^k\) and \(p \mid x\), and \(N = p^{k - 1}\). Thus
\(\phi(p^k) = p^k - p^{k - 1} = p^k (1 - 1/p)\)
Let \(n \in N\). Then
\( \begin{aligned} \phi(n) = n \prod_{p \mid n} (1 - 1/p) \end {aligned} \)
where when \(n = 1\) we interpret the product as an empty product \(1\).
Note that \(\phi(n^2) \ne \phi(n)^2\).
EXAMPLE
\( \begin{aligned} n = 2^2 &= 4 &&& 2 = 2 \times 1 &= 2^2 - 2 &&= | \{ 1, 3 \} | \\ n = 2^3 &= 8 &&& 4 = 2^2 \times 1 &= 2^3 - 2^2 &&= | \{ 1, 3, 5, 7 \} | \\ n = 2^4 &= 16 &&& 8 = 2^3 \times 1 &= 2^4 - 2^3 &&= | \{ 1, 3, 5, 7, 9, 11, 13, 15 \} | \\ n = 2^5 &= 32 &&& 16 = 2^4 \times 1 &= 2^5 - 2^4 &&= \dots \\ n = 2^6 &= 64 &&& 32 = 2^5 \times 1 &= 2^6 - 2^5 &&= \dots \\ \\ n = 3^2 &= 9 &&& 6 = 3 \times 2 &= 3^2 - 3 &&= | \{ 1, 2, 4, 5, 7, 8 \} | \\ n = 3^3 &= 27 &&& 18 = 3^2 \times 2 &= 3^3 - 3^2 &&= | \{ 1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26 \} | \\ n = 3^4 &= 81 &&& 54 = 3^3 \times 2 &= 3^4 - 3^3 &&= \dots \\ n = 3^5 &= 243 &&& 162 = 3^4 \times 2 &= 3^5 - 3^4 &&= \dots \\ n = 3^6 &= 729 &&& 486 = 3^5 \times 2 &= 3^6 - 3^5 &&= \dots \\ \\ n = 5^2 &= 25 &&& 20 = 5 \times 4 &= 5^2 - 5 &&= | \{ 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24 \} | \\ n = 5^3 &= 125 &&& 100 = 5^2 \times 4 &= 5^3 - 5^2 &&= \dots \\ n = 5^4 &= 625 &&& 500 = 5^3 \times 4 &= 5^4 - 5^3 &&= \dots \\ n = 5^5 &= 3125 &&& 2500 = 5^4 \times 4 &= 5^5 - 5^4 &&= \dots \\ n = 5^6 &= 15625 &&& 12500 = 5^5 \times 4 &= 5^6 - 5^5 &&= \dots \\ \end {aligned} \)
\( \begin{aligned} \phi( 1) &= 1 \prod_{p \mid 1} (1 - 1/p) && := & 1 \\ \phi( 2) &= 2 \prod_{p \mid 2} (1 - 1/p) = 2 \times (1 - 1/ 2) && = & 1 \\ \phi( 3) &= 3 \prod_{p \mid 3} (1 - 1/p) = 3 \times (1 - 1/ 3) && = & 2 \\ \phi( 4) &= 4 \prod_{p \mid 4} (1 - 1/p) = 4 \times (1 - 1/ 2) && = & 2 \\ \phi( 5) &= 5 \prod_{p \mid 5} (1 - 1/p) = 5 \times (1 - 1/ 5) && = & 4 \\ \phi( 6) &= 6 \prod_{p \mid 6} (1 - 1/p) = 6 \times (1 - 1/ 2)(1 - 1/3) && = & 2 \\ \phi( 7) &= 7 \prod_{p \mid 7} (1 - 1/p) = 7 \times (1 - 1/ 7) && = & 6 \\ \phi( 8) &= 8 \prod_{p \mid 8} (1 - 1/p) = 8 \times (1 - 1/ 2) && = & 4 \\ \phi( 9) &= 9 \prod_{p \mid 9} (1 - 1/p) = 9 \times (1 - 1/ 3) && = & 6 \\ \phi(10) &= 10 \prod_{p \mid 10} (1 - 1/p) = 10 \times (1 - 1/ 2)(1 - 1/5) && = & 4 \\ \phi(11) &= 11 \prod_{p \mid 11} (1 - 1/p) = 11 \times (1 - 1/11) && = & 10 \\ \phi(12) &= 12 \prod_{p \mid 12} (1 - 1/p) = 12 \times (1 - 1/ 2)(1 - 1/3) && = & 4 \\ \phi(13) &= 13 \prod_{p \mid 13} (1 - 1/p) = 13 \times (1 - 1/13) && = & 12 \\ \phi(14) &= 14 \prod_{p \mid 14} (1 - 1/p) = 14 \times (1 - 1/ 2)(1 - 1/7) && = & 6 \\ \phi(15) &= 15 \prod_{p \mid 15} (1 - 1/p) = 15 \times (1 - 1/ 3)(1 - 1/5) && = & 8 \\ \phi(16) &= 16 \prod_{p \mid 16} (1 - 1/p) = 16 \times (1 - 1/ 2) && = & 8 \\ \phi(17) &= 17 \prod_{p \mid 17} (1 - 1/p) = 17 \times (1 - 1/17) && = & 16 \\ \phi(18) &= 18 \prod_{p \mid 18} (1 - 1/p) = 18 \times (1 - 1/ 2)(1 - 1/3) && = & 6 \\ \phi(19) &= 19 \prod_{p \mid 19} (1 - 1/p) = 19 \times (1 - 1/19) && = & 18 \\ \phi(20) &= 20 \prod_{p \mid 20} (1 - 1/p) = 20 \times (1 - 1/ 2)(1 - 1/5) && = & 8 \\ \phi(21) &= 21 \prod_{p \mid 21} (1 - 1/p) = 21 \times (1 - 1/ 3)(1 - 1/7) && = & 12 \\ \phi(22) &= 22 \prod_{p \mid 22} (1 - 1/p) = 22 \times (1 - 1/ 2)(1 - 1/11) && = & 10 \\ \phi(23) &= 23 \prod_{p \mid 23} (1 - 1/p) = 23 \times (1 - 1/23) && = & 22 \\ \phi(24) &= 24 \prod_{p \mid 24} (1 - 1/p) = 24 \times (1 - 1/ 2)(1 - 1/3) && = & 8 \\ \phi(25) &= 25 \prod_{p \mid 25} (1 - 1/p) = 25 \times (1 - 1/ 5) && = & 20 \\ \phi(26) &= 26 \prod_{p \mid 26} (1 - 1/p) = 26 \times (1 - 1/ 2)(1 - 1/13) && = & 12 \\ \phi(27) &= 27 \prod_{p \mid 27} (1 - 1/p) = 27 \times (1 - 1/ 3) && = & 18 \\ \phi(28) &= 28 \prod_{p \mid 28} (1 - 1/p) = 28 \times (1 - 1/ 2)(1 - 1/7) && = & 12 \\ \phi(29) &= 29 \prod_{p \mid 29} (1 - 1/p) = 29 \times (1 - 1/29) && = & 28 \\ \phi(30) &= 30 \prod_{p \mid 30} (1 - 1/p) = 30 \times (1 - 1/ 2)(1 - 1/3)(1 - 1/5) && = & 8 \\ \end {aligned} \)
EULER’S THEOREM [Vaughan Theorem 3.17]
Suppose that \(m \in \mathbb{N}\) and \(a \in \mathbb{Z}\) with \(\gcd(a, m) = 1\). Then
\(a^{\phi(m)} \equiv 1 \mod m\)
Proof
Let \(a_1, a_2, \dotsc, a_{\phi(m)}\) be a reduced set modulo \(m\).
Then \(aa_1, aa_2, \dotsc, aa_{\phi(m)}\) is another. Hence
\( \begin{aligned} a_1 a_2 \dots a_{\phi(m)} &\equiv aa_1 aa_2 \dots aa_{\phi(m)} & \mod m \\ &\equiv a_1 a_2 \dots a_{\phi(m)} a^{\phi(m)} & \mod m \\ 1 &\equiv a^{\phi(m)} & \mod m && \text{since } \gcd(a_1 a_2 \dots a_{\phi(m)}, m) = 1 \\ \end {aligned} \)
\(\blacksquare\)
Example
\( \begin{aligned} m &= 17 & a &= 3 & 3^{16} &\equiv 1 \mod 17 \\ m &= 341561645 & a &= 2 & 2^{m - 1} &\equiv 1 \mod m \\ \end {aligned} \)
FERMAT’S LITTLE THEOREM [Vaughan Corollary 3.18]
Let \(p\) be a prime and \(a \in \mathbb{Z}\). Then
\(a^p \equiv a \mod p\)
If \(p \nmid a\) then
\(a^{p - 1} \equiv 1 \mod p\)
“If \(p\) is prime and \(p\) does not divide \(a\) then \(a^{p - 1} \equiv 1 \mod p\)”
The converse of this statement will lead us to the notion of Fermat pseudoprimes.
Example
\( \begin{aligned} p &= 17, a = 3 && 3^{17} \equiv 3 \mod 17 \\ \end {aligned} \)
Fermat pseudoprimes#
Pseudoprimes are composite integers masquerading as primes.
Could Fermat’s theorem give us a primality test? Unfortunately, it is possible that
\(a^{n - 1} \equiv 1 \mod n\)
when \(n\) is not prime, although this is rare. For example, when \(n = 341,561,645\) then
\(2^{n - 1} \equiv 1 \mod n\)
Such \(n\) are called (Fermat) pseudoprimes.
FERMAT PSEUDOPRIME
A pseudoprime \(m\) to the base \(a\) is a composite integer \(m\) that masquerades as a prime by satisfying the congruence
\(a^{m - 1} \equiv 1 \mod m\)
There are \(245\) pseudoprimes less than \(10^6\) (compared to \(78498\) primes less than \(10^6\)).
Base-2 Fermat Pseudoprimes
\( \begin{aligned} n &= 341 &&= 11 \times 31 & 2^{341 - 1} &\equiv 1 \mod 341 \\ n &= 341561645 &&= 5 \times 67 \times 773 \times 1319 & 2^{n - 1} &\equiv 1 \mod n \\ \end {aligned} \)
\(3^{341 - 1} \equiv 56 \ne 1 \mod 341\) suggests a possible primality test.
Given \(n\), try trial division a few times (say for \(d = 2, 3, 5, 7\)) and then check \(a^{n - 1} \equiv 1 \mod n\) successively for \(a = 2, 3, 5, 7\).
Unfortunately, one still encounters false positives.
\(561 = 3 \times 11 \times 17\) satisfies \(a^{560} \equiv 1 \mod 561\) for all \(a\) with \(\gcd(a, 561) = 1\).
Carmichael Numbers#
CARMICHAEL NUMBER [Vaughan Definition 3.19]
A composite \(n\) which satisfies \(a^{n - 1} \equiv 1 \mod n\) for all \(a\) with \(\gcd(a, n) = 1\) is called a Carmichael number.
“A Carmichael number is a composite integer that is a pseudoprime to all bases \(a\) coprime prime to it.”
There are infinitely many Carmichael numbers. The smallest is \(561\) and there are \(2163\) of them below \(25 \times 10^9\).
Mersenne Primes#
MERSENNE PRIME [Vaughan Definition 3.20]
Define \(M(n) = 2^n - 1\). If it is prime then it is a Mersenne prime.
If \(n = ab\) then \(M(ab) = (2^a - 1)(2^{a(b - 1)} + \dotsb + 2^a + 1)\).
Thus for \(M(n)\) to be prime it is necessary that \(n\) be prime. However, that is not sufficient.
Example
\( \begin{aligned} M( 2) &=& 2^2 - 1 &=& 3 & && \text{} \\ M( 3) &=& 2^3 - 1 &=& 7 & && \text{} \\ M( 5) &=& 2^5 - 1 &=& 31 & && \text{} \\ M( 7) &=& 2^7 - 1 &=& 127 & && \text{} \\ M(11) &=& 2^{11} - 1 &=& 2047 &= \textcolor{red}{23 \times 89} && \text{not a Mersenne prime} \\ \end {aligned} \)
Linear Congruence#
Linear congruences have the form
\(ax \equiv b \mod m\)
To solve linear congruences, inverses modulo \(m\) are employed. Work backward through the steps of the Euclidean algorithm to find inverses modulo \(m\). Once an inverse of \(a\) modulo \(m\) has been found, solve the linear congruence by multiplying both sides by the inverse.
We have already solved \(ax \equiv b \mod m\) in principle since it is equivalent to the linear diophantine equation
\(ax + my = b\)
PROOF
The congruence \(ax \equiv b \mod m\) is equivalent to the equation \(ax + my = b\)
\( \begin{aligned} ax \equiv b \mod m \iff m \mid (ax - b) \iff ax - b = m(-y) \iff ax + my = b \\ \end {aligned} \)
\((a/d)x + (m/d)y = b/d \iff (a/d)x - b/d = (-y)(m/d) \iff (a/d)x \equiv (b/d) \mod (m/d)\)
and there can be no solution if \(\gcd(a, m) \nmid b\)
Let \(d = \gcd(a, m)\). By definition \(d \mid a\) and \(d \mid m\) and so it must be the case that \(d \mid (b = ax + my)\).
If \(d \mid b\) then Euclid’s algorithm solves
\( \begin{aligned} ax + my = b = (a/d)x + (m/d)y = b/d = \frac{a}{\gcd(a, m)} x + \frac{m}{\gcd(a, m)} y = \frac{b}{\gcd(a, m)} \end {aligned} \)
Euclid’s algorithm computes \(d = \gcd(a, m)\) by repeated application of the division algorithm. The extension keeps track of integer combinations of \(a\) and \(m\) that yeild \(d\) for some integers \(s\) and \(t\)
\( \begin{aligned} d &= sa + tm \\ (b/d)d &= (b/d)sa + (b/d)tm \\ b &= a\underbrace{(b/d)s}_{x_0} + m\underbrace{(b/d)t}_{y_0} \\ \end {aligned} \)
\(ax_0 - b = m(-y_0) \iff ax_0 \equiv b \mod m\)
Let \(x_0, y_0\) be such a solution. Obviously every member of the residue class
\(x_0\) modulo \(m/d\)
gives a solution. Let \(x, y\) be another solution. Then
\( \begin{aligned} & ax + my = b, ax_0 + my_0 = b \\ & ax + my - ax_0 - my_0 = 0 \iff ax - ax_0 + my - my_0 = 0 \iff a(x - x_0) + m(y - y_0) = 0 \\ & (a/d)(x - x_0) + (m/d)(y - y_0) = 0 \\ & (a/d)(x - x_0) = (m/d)(y_0 - y) \\ & (m/d) \mid (a/d)(x - x_0) \\ & (a/d)(x - x_0) \equiv 0 \mod (m/d) \\ \end {aligned} \)
\((a/d)(x - x_0) \equiv 0 \mod m/d \iff (m/d) \mid (a/d)(x - x_0)\)
and since
\( \begin{aligned} \gcd(a/d, m/d) = \gcd \left( \frac{a}{\gcd(a, m)}, \frac{m}{\gcd(a, m)} \right) = 1 \end {aligned} \)
\(x = x_0 + k(m/d) \iff (m/d) \mid (x - x_0) \iff x \equiv x_0 \mod (m/d)\)
it follows that \(x\) is in the residue class
\(x_0\) modulo \(m/d\)
\( \begin{aligned} & (a/d)(x - x_0) + (m/d)(y - y_0) = 0 \\ & (a/d)((-k)(m/d)) + (m/d)(y - y_0) = 0 \\ & (-k)(a/d) + y - y_0 = 0 \\ & y = y_0 + k(a/d) \\ & y - y_0 = k(a/d) \\ & y \equiv y_0 \mod (a/d) \end {aligned} \)
\(\blacksquare\)
WILSON’S THEOREM [Vaughan Theorem 3.23]
Let \(p\) be prime. Then \((p - 1)! \equiv -1 \mod p\).
Proof
\( \begin{aligned} p &= 2 && (2 - 1)! \equiv -1 \mod 2 \\ p &= 3 && (3 - 1)! \equiv -1 \mod 3 \\ \end {aligned} \)
Suppose \(p \ge 5\). Observe now that \(x^2 \equiv 1 \mod p\) implies that \(x \equiv \pm 1 \mod p\).
Thus the numbers \(2, 3, \dotsc, p - 2\) can be paired off into \(\frac{p - 3}{2}\) mutually exclusive pairs \(a, b\) s.t. \(ab \equiv 1 \mod p\).
Thus \((p - 1)! \equiv p - 1 \equiv -1 \mod p\)
\(\blacksquare\)
This theorem actually gives a necessary and sufficient condition for \(p\) to be prime, since if \(p\) were to be composite then \(\gcd((p - 1)!, p) \gt 1\). However, it is useless because \((p - 1)!\) grows very rapidly.
Chinese Remainder Theorem#
SYSTEM OF LINEAR CONGRUENCES
\( \begin{cases} a_1 x &\equiv b_1 \mod q_1 \\ a_2 x &\equiv b_2 \mod q_2 \\ \dots \\ a_r x &\equiv b_r \mod q_r \\ \end {cases} \)
There can only be a solution when each individual equation is soluble, so we require \(\gcd(a_j, q_j) \mid b_j\) for every \(j\).
Then we know that each individual equation is soluble by some residue class modulo \(q_j / \gcd(a_j, q_j)\).
Thus for some values of \(c_j\) and \(m_j\) this reduces to
\( \begin{cases} x &\equiv c_1 \mod m_1 \\ \dots \\ x &\equiv c_r \mod m_r \\ \end {cases} \)
Suppose for some \(i\) and \(j \ne i\) we have \(\gcd(m_i, m_j) = d \gt 1\). Then \(x\) has to satisfy \(c_i \equiv x \equiv c_j \mod d\). This imposes conditions on \(c_j\) which can get complicated. Thus it is convenient to assume that \(\gcd(m_i, m_j) = 1\) when \(i \ne j\).
CHINESE REMAINDER THEOREM
The Chinese Remainder Theorem is about solving systems of linear congruences modulo pairwise coprime moduli.
Suppose that \(\gcd(m_i, m_j) = 1\) for every \(i \ne j\).
Then the system
\( \begin{cases} x &\equiv c_1 \mod m_1 \\ \dots \\ x &\equiv c_r \mod m_r \\ \end {cases} \)
has as its complete solution precisely the members of a unique residue class modulo \(m_1 m_2 \dots m_r\).
Proof
EXISTENCE
Let \(M = m_1 m_2 \dots m_r\) and \(M_j = M / m_j\), so that \(\gcd(M_j, m_j) = 1\).
We know that there is an \(N_j\) so that \(M_j N_j \equiv c_j \mod m_j\). (Solve \(yM_j \equiv c_j \mod m_j\) in \(y\).)
Let \(x\) be any member of the residue class \(N_1 M_1 + \dotsb + N_r M_r \mod M\).
Then for every \(j\), since \(m_j \mid M_i\) when \(i \ne j\) we have \(x \equiv N_j M_j \equiv c_j \mod m_j\).
So the residue class \(x \mod M\) gives a solution.
UNIQUENESS
Suppose \(y\) is also a solution of the system.
Then for every \(j\) we have \(y \equiv c_j \equiv x \mod m_j\) and so \(m_j \mid y - x\).
Since the \(m_j\) are pairwise coprime we have \(M \mid y - x\), so \(y\) is in the residue class \(x\) modulo \(M\).
\(\blacksquare\)
Example
\( \begin{aligned} x &\equiv \underset{c_1}{3} \mod \underset{m_1}{\phantom{2}4} \\ x &\equiv \underset{c_2}{5} \mod \underset{m_2}{21} \\ x &\equiv \underset{c_3}{7} \mod \underset{m_3}{25} \\ \end {aligned} \)
\( \begin{aligned} M &= m_1 \times m_2 \times m_3 = & 2100 \\ M_1 &= \phantom{m_1 \times}m_2 \times m_3 = & 525 \\ M_2 &= m_1 \phantom{\times m_2} \times m_3 = & 100 \\ M_3 &= m_1 \times m_2 \phantom{\times m_3} = & 84 \\ \end {aligned} \)
Solve
\( \begin{aligned} 525 N_1 &\equiv 3 \mod \phantom{2}4 \\ 100 N_2 &\equiv 5 \mod 21 \\ 84 N_3 &\equiv 7 \mod 25 \\ \end {aligned} \)
reduces to
\( \begin{aligned} N_1 &\equiv 3 \mod \phantom{2}4 \\ (-5) N_2 &\equiv 5 \mod 21 \\ 9 N_3 &\equiv 7 \equiv -18 \mod 25 \\ \end {aligned} \)
\( \begin{aligned} N_1 &= 3 \\ N_2 &= 20 \\ N_3 &= 23 \equiv -2 \mod 25 \\ \end {aligned} \)
\( \begin{aligned} x &\equiv N_1 M_1 + N_2 M_2 + N_3 M_3 \mod M \\ &= 3 \times 525 + 20 \times 100 + 23 \times 84 \mod 2100 \\ &= 5507 \mod 2100 \\ &\equiv 1307 \mod 2100 \\ \end {aligned} \)
Polynomial Congruence#
The solution of a general polynomial congruence can be quite tricky, even for a polynomial with a single variable.
POLYNOMIAL CONGRUENCE
\(f(x) := a_0 + a_1 x + \dotsb + a_j x^j + \dotsb + a_J x^J \equiv 0 \mod m\)
where the \(a_j\) are integers.
The largest \(k\) such that \(a_k \not\equiv 0 \mod m\) is the degree of \(f\) modulo \(m\). If \(a_j \equiv 0 \mod m\) for every \(j\) then the degree of \(f\) modulo \(m\) is not defined.
When we have a solution \(x\) to a polynomial congruence we may refer to such values as a root of the polynomial modulo \(m\).
We have already seen that
\(x^2 \equiv 1 \mod 8\)
is solved by any odd \(x\) so that it has four solutions modulo \(8\).
\(x \equiv 1, 3, 5, 7 \mod 8\)
LAGRANGE’S THEOREM [Vaughan Theorem 3.26]
Suppose that \(p\) is prime and
\(f(x) = a_0 + a_1 x + \dotsb + a_j x^j + \dotsb + a_J x^J \equiv 0 \mod m\)
is a polynomial with integer coefficients \(a_j\) and it has degree \(k\) modulo \(p\). Then the number of incongruent solutions of
\(f(x) \equiv 0 \mod p\)
is at most \(k\).
Proof by induction on \(k\)
Degree \(0\) is trivial so we can suppose \(k \ge 1\).
If a polynomial \(f\) has degree \(1\) modulo \(p\) so that \(f(x) = a_0 + a_1 x\) with \(p \nmid a_1\) then the congruence becomes \(a_1 x \equiv -a_0 \mod p\) and since \(a_1 \not\equiv 0 \mod p\) (because \(f\) has degree \(1\)) we know that this is soluble by precisely the members of a unique residue class modulo \(p\).
Now suppose that the conclusion holds for all polynomials of a given degree \(k\) and suppose that
\(f = a_0 + \dotsb + a_{k + 1} x^{k + 1}\) has degree \(k + 1\).
If \(f(x) \equiv 0 \mod p\) has no solutions then we are done.
Hence we may assume at least one, say \(x \equiv x_0 \mod p\).
By the division algorithm for polynomials we have
\(f(x) = (x - x_0) q(x) + f(x_0)\)
where \(q(x)\) is a polynomial of degree \(k\).
Moreover the leading coefficient of \(q(x)\) is \(a_{k + 1} \equiv 0 \mod p\).
But \(f(x_0) \equiv 0 \mod p\) so that \(f(x) \equiv (x - x_0) q(x) \mod p\).
If \(f(x_1) \equiv 0 \mod p\) with \(x_1 \equiv x_0 \mod p\) then \(p \nmid x_1 - x_0\) so that \(p \mid q(x_1)\).
By the inductive hypothesis there are at most \(k\) possibilities for \(x_1\) so at most \(k + 1\) in all.
\(\blacksquare\)
Nonlinear polynomials in one variable are complicated. The general modulus can be reduced to a prime power modulus, which can be reduced to the prime modulus. In general, the prime case leads to algebraic number theory.
Acknowledgements#
SDCP 2006 Dasgupta, Sanjoy; Christos Papadimitriou; & Umesh Vazirani. Algorithms. McGraw-Hill.
KRDM 2018 Rosen, Kenneth. Discrete Mathematics and its Applications 8e. McGraw-Hill.
CENT 2023 [ h ] Vaughan, Robert. A Course of Elementary Number Theory. CMPSC/MATH 467 Factorization and Primality Testing. The Pennsylvania State University. [ book ]