Congruence and Residue#
Contents#
Definition: residue class#
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) \}\)
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\).
Residue class arithmetic#
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}\)
Definition: congruence relation#
Let \(m \in \mathbb{N}\). If two integers \(x\) and \(y\) satisfy \(m \mid x - y\) then we write
\(x \equiv y \mod m\)
and we say that \(x\) is congruent to \(y\) modulo \(m\).
Properties of the congruence relation#
Reflexivity#
\(x \equiv x \mod m\)
Symmetry#
\(x \equiv y \mod m \iff y \equiv x \mod m\)
Transitivity#
If \(x \equiv y \mod m\) and \(y \equiv z \mod m\) then \(x \equiv z \mod m\).
Congruences modulo \(m\) partition the integers into equivalence classes.
Additions preserve congruence#
If \(x \equiv y \mod m\) and \(z \equiv t \mod m\) then \(x + z \equiv y + t \mod m\).
Multiplications preserve congruences#
If \(x \equiv y \mod m\) and \(z \equiv t \mod m\) then \(xz \equiv yt \mod m\).
If \(x \equiv y \mod m\) then for any \(n \in \mathbb{N}\) it is the case that \(x^n \equiv y^n \mod m\) (using induction on \(n\)).
If \(f\) is a polynomial with integer coefficients and \(x \equiv y \mod m\) then \(f(x) \equiv f(y) \mod m\).
Theorem#
Suppose that \(m \in \mathbb{N}\), \(k \in \mathbb{Z}\), \(\gcd(k, m) = 1\), and
\(\overline{a_1}, \overline{a_2}, \dotsc, \overline{a_m}\)
forms a complete system of residues modulo \(m\). Then so does
\(\overline{ka_1}, \overline{ka_2}, \dotsc, \overline{ka_m}\)
EXAMPLE
\(\bar{0}, \bar{1}, \bar{2}\) is a complete system of residues modulo \(m\)
\( \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(2, 3) = 1\)
\( \begin{aligned} \bar{0} &= \{ x \in \mathbb{Z} : 3 \mid (x - 0) \} = \{ 3x \} \\ \bar{2} &= \{ x \in \mathbb{Z} : 3 \mid (x - 2) \} = \{ 3x + 2 \} \\ \bar{4} &= \{ x \in \mathbb{Z} : 3 \mid (x - 4) \} = \{ 3x + 4 \} = \{ 3(x + 1) + 1 \} = \{ 3x + 1 \} \\ \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\)
The residue classes \(r\) modulo \(m\) with \(\gcd(r, m) = 1\) play an important role.
Definition: arithmetical function#
A function defined on \(\mathbb{N}\) is called an arithmetical function.
Definition: Euler’s function#
Euler’s function \(\phi(n)\) is the number of \(x \in \mathbb{N}\) with \(1 \le x \le n\) and \(\gcd(x, n) = 1\).
\(\phi(1) = 1\) since \(\gcd(1, 1) = 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 \(\phi(p) = p - 1\)
\( \begin{aligned} \phi( 1) &= 1 \\ \phi( 2) &= 1 \\ \phi( 3) &= 2 \\ \phi( 4) &= 2 && \gcd(1, 4) = \gcd(3, 4) \\ \phi( 5) &= 4 \\ \phi( 6) &= 2 && \gcd(1, 6) = \gcd(5, 6) \\ \phi( 7) &= 6 \\ \phi( 8) &= 4 && \gcd(1, 8) = \gcd(3, 8) = \gcd(5, 8) = \gcd(7, 8) \\ \phi( 9) &= 6 && \gcd(1, 9) = \gcd(2, 9) = \gcd(4, 9) = \gcd(5, 9) = \gcd(7, 9) = \gcd(8, 9) \\ \phi(10) &= 4 && \gcd(1, 10) = \gcd(3, 10) = \gcd(7, 10) = \gcd(9, 10) \\ \phi(11) &= 10 \\ \phi(12) &= 4 && \gcd(1, 12) = \gcd(5, 12) = \gcd(7, 12) = \gcd(11, 12) \\ \phi(13) &= 12 \\ \phi(14) &= 6 && \gcd(1, 14) = \gcd(3, 14) = \gcd(5, 14) = \gcd(9, 14) = \gcd(11, 14) = \gcd(13, 14) \\ \phi(15) &= 8 && \gcd(1, 15) = \gcd(2, 15) = \gcd(4, 15) = \gcd(7, 15) = \gcd(8, 15) = \gcd(11, 15) = \gcd(13, 15) = \gcd(14, 15) \\ \phi(16) &= 8 && \gcd(1, 16) = \gcd(3, 16) = \gcd(5, 16) = \gcd(7, 16) = \gcd(9, 16) = \gcd(11, 16) = \gcd(13, 16) = \gcd(15, 16) \\ \phi(17) &= 16 \\ \phi(18) &= 6 && \gcd(1, 18) = \gcd(5, 18) = \gcd(7, 18) = \gcd(11, 18) = \gcd(13, 18) = \gcd(17, 18) \\ \phi(19) &= 18 \\ \phi(20) &= 8 && \gcd(1, 20) = \gcd(3, 20) = \gcd(7, 20) = \gcd(9, 20) = \gcd(11, 20) = \gcd(13, 20) = \gcd(17, 20) = \gcd(19, 20) \\ \phi(21) &= 12 && \gcd(1, 21) = \gcd(2, 21) = \gcd(4, 21) = \gcd(5, 21) = \gcd(8, 21) = \gcd(10, 21) = \gcd(11, 21) = \gcd(13, 21) = \gcd(16, 21) = \gcd(17, 21) = \gcd(19, 21) = \gcd(20, 21) \\ \phi(22) &= 10 && \gcd(1, 22) = \gcd(3, 22) = \gcd(5, 22) = \gcd(7, 22) = \gcd(9, 22) = \gcd(13, 22) = \gcd(15, 22) = \gcd(17, 22) = \gcd(19, 22) = \gcd(21, 22) \\ \phi(23) &= 22 \\ \phi(24) &= 8 && \gcd(1, 24) = \gcd(5, 24) = \gcd(7, 24) = \gcd(11, 24) = \gcd(13, 24) = \gcd(17, 24) = \gcd(19, 24) = \gcd(23, 24) \\ \phi(25) &= 20 && \gcd(1, 25) = \gcd(2, 25) = \gcd(3, 25) = \gcd(4, 25) = \gcd(6, 25) = \gcd(7, 25) = \gcd(8, 25) = \gcd(9, 25) = \gcd(11, 25) = \gcd(12, 25) = \gcd(13, 25) = \gcd(14, 25) = \gcd(16, 25) = \gcd(17, 25) = \gcd(18, 25) = \gcd(19, 25) = \gcd(21, 25) = \gcd(22, 25) = \gcd(23, 25) = \gcd(24, 25) \\ \phi(26) &= \\ \phi(27) &= \\ \phi(28) &= \\ \phi(29) &= 28 \\ \phi(30) &= 8 && \gcd(1, 30) = \gcd(7, 30) = \gcd(11, 30) = \gcd(13, 30) = \gcd(17, 30) = \gcd(19, 30) = \gcd(23, 30) = \gcd(29, 30) \\ \end {aligned} \)
Definition: reduced residues#
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} \)
Now 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\).
Suppose 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\).
EXAMPLE
\( \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{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} \)
Theorem#
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} \)
EXAMPLE
\( \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#
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.
Theorem#
[Vaughan, Theorem 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.
EXAMPLE
\(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)\)
Corollary#
[Vaughan, Corollary 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} \)
Definition: multiplicative function#
[Vaughan, Definition 13]
If an arithmetical function \(f\) which is not identically \(0\) satisfies
\(f(mn) = f(m) f(n)\)
whenever \(\gcd(m, n) = 1\) then \(f\) is called multiplicative.
Corollary#
[Vaughan, Corollary 14]
Euler’s function is multiplicative.
Theorem#
[Vaughan, Theorem 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} \)
Theorem (Euler)#
[Vaughan, Theorem 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\)
Corollary (Fermat)#
[Vaughan, Corollary 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\)
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 pseudoprimes.
There are \(245\) pseudoprimes less than \(10^6\) (compared to \(78498\) primes less than \(10^6\)).
\(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 57\) satisfies \(a^{560} \equiv 1 \mod 561\) for all \(a\) with \(\gcd(a, 561) = 1\).