Congruence#
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}\)
Congruence#
CONGRUENCE RELATION
If \(a\) and \(b\) are integers and \(m\) is a positive integer then \(a\) is congruent to \(b\) modulo \(m\) if \(m\) divides \(a - b\). (Another way to state this is as follows: Let \(m \in \mathbb{N}\). If two integers \(a\) and \(b\) satisfy \(m \mid a - b\) then…)
\( \begin{aligned} a \equiv b \mod m &\iff m | (a - b) &&\iff a = b + km \\ a \equiv 0 \mod m &\iff m | a &&\iff a = km \\ a \equiv 1 \mod m &\iff m | (a - 1) &&\iff a = 1 + km \\ \end {aligned} \)
We say that \(a \equiv b \mod m\) is a congruence and that \(m\) is its modulus.
\(253 \equiv 13 \,(\text{mod } 60)\) because \(253 - 13\) is a multiple of \(60\). (\(253\) minutes is \(4\) hours and \(13\) minutes.)
\(59 \equiv -1 \,(\text{mod } 60)\) because \(59 - (-1)\) is a multiple of \(60\). (When it’s \(59\) minutes past the hour it’s also one minute short of the next hour.)
THEOREM [Rosen]
\(a \equiv b \mod m\) represents a relation on the set of integers.
\(a \textbf{ mod } m = b\) represents a function.
Let \(a\) and \(b\) be integers and \(m\) be a positive integer. Then \(a \equiv b \mod m\) iff \(a \textbf{ mod } m = b \textbf{ mod } m\). (“a and b are congruent modulo m iff a and b have the same remainder when divided by 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\).
Associativity
\(x + (y + z) \equiv (x + y) + z \quad(\text{mod } N)\)
Commutativity
\(xy \equiv yz \quad(\text{mod } N)\)
Distributivity
\(x(y + z) \equiv xy + xz \quad(\text{mod } N)\)
The four rules imply that while performing a sequence of arithmetic operations it is legal to reduce intermediate results to their remainders modulo \(N\) at any stage:
\(2^{345} \equiv (2^5)^{69} \equiv 32^{69} \equiv 1^{69} \equiv 1 \quad(\text{mod } 31)\)
Factoring a scalar out of a congruence#
CLAIM
\(kx \equiv ka \mod n \iff x \equiv a \mod n/d\) where \(d = \gcd(n, k)\)
The modulus changes when dividing a congruence if you are dividing both sides of the congruence by a number that is not relatively prime to the modulus. In other words, if the number you’re dividing by shares a common factor with the modulus, you must also divide the modulus by that same common factor to maintain the congruence relation.
PROOF
\(kx \equiv ka \mod n \iff n \mid k(x - a) \iff n/d \mid (k/d)(x - a)\) where \(d = \gcd(n, k)\)
\( \begin{aligned} \frac{n}{\gcd(n, k)} \Biggm\vert\left( \frac{k}{\gcd(n, k)}(x - a) \right) \end {aligned} \)
By Euclid’s Lemma we know that
\(n/d \mid (k/d)(x - a) \implies\) either \(n/d \mid k/d\) or \(n/d \mid (x - a)\)
And we know that
\( \gcd(n/d, k/d) = \begin{aligned} \gcd\left( \frac{n}{\gcd(n, k)}, \frac{k}{\gcd(n, k)} \right) = 1 \end {aligned} \)
Thus it must be the case that
\(n/d \mid (x - a) \iff x \equiv a \mod n/d\)
\(\blacksquare\)
https://crypto.stanford.edu/pbc/notes/numbertheory/arith.html
\( \begin{aligned} 65y & \equiv & 5 & \mod 10 \\ 5.13y & \equiv & 5.1 & \mod 10/\gcd(5, 10) \\ 13y & \equiv & 1 & \mod 2 \\ \end {aligned} \)
Modular Arithmetic#
Modular arithmetic operates with the remainders of integers when they are divided by a fixed positive integer called the modulus. For the applications such as primality testing and cryptography it is necessary to deal with numbers which are much larger than 32 bits but whose range is nonetheless limited. Modular arithmetic is a system for dealing with restricted ranges of integers.
Ways to think about modular arithmetic
modular arithmetic limits numbers to a predefined range \(\{ 0, 1, \dotsc, N - 1 \}\) and wraps around whenever you try to leave this range.
modular arithmetic deals with all the integers, but divides them into \(N\) equivalence classes each of the form \(\{ i + kN : k \in \mathbb{Z} \}\) for some \(i\) between \(0\) and \(N - 1\)
Modular Addition#
To add two numbers \(x\) and \(y\) modulo \(N\) we start with regular addition. \(x\) and \(y\) are each in the range \(0\) to \(N - 1\) so their sum is in the range \(0\) to \(2(N - 1)\). When the sum exceeds \(N - 1\) we subtract \(N\) so that it falls back into the range \(0\) to \(N - 1\). The overall computations consists of an addition and a possible subtraction of numbers which never exceed \(2N\).
\(T(n) = O(n)\) where \(n = \lceil \log N \rceil\)
Modular Multiplication#
To multiply two numbers \(x\) and \(y\) modulo \(N\), we start with regular multiplication and then reduce the answer modulo \(N\). The product can be as large as \((N - 1)^2\) but this is still at most \(2n\) bits long since \(\log (N - 1)^2 = 2 \log (N - 1) \le 2n\). To reduce the answer modulo \(N\) we compute the remainder upon dividing it by \(N\) using the quadratic-time division algorithm. Multiplication thus remains a quadratic operation.
Complexity
\(T(n) = \underbrace{\quad\quad O(n^2) \quad\quad}_{\text{multiplication}} + \underbrace{\quad\quad O(n^2) \quad\quad}_{\text{reduction modulo \textit{N} via division}} = O(n^2)\)
Modular Division#
In ordinary arithmetic there is just one tricky case–division by zero. In modular arithmetic there are other tricky cases.
When division is legal, its running time is
\(T(n) = O(n^3)\)
Modular Exponentiation#
Can \(x^y \mod N\) be computed quickly for values of \(x\), \(y\), and \(N\) that are several hundred bits long? The result is some number modulo \(N\) and is therefore itself a few hundred bits long. The raw value \(x^y\) could be much longer. When \(x\) and \(y\) are just \(20\text{-b}\) numbers \(x^y\) is at least \((2^{19})^{2^{19}} = 2^{(19)(524,288)}\) which is about ten million bits long. Imagine what would happen if \(y\) is a \(500\text{-b}\) number. To make sure the numbers we are dealing with never grow too large, we need to perform all intermediate computations modulo \(N\).
Calculate \(x^y \mod N\) by repeatedly multiplying by \(x \mod N\). The resulting sequence of intermediate products \(x \mod N \to x^2 \mod N \to \dotsb \to x^y \mod N\) consists of numbers smaller than \(N\), so the individual multiplications do not take too long. But if \(y\) is \(500\) bits long we need to perform \(y - 1 \approx 2^{500}\) multiplications which is exponential in the size of \(y\).
It will be better to start with \(x\) and repeatedly square modulo \(N\): \(x \mod N \to x^2 \mod N \to x^4 \mod N \to x^8 \mod N \to \dotsb \to x^{2^{\lfloor \log y \rfloor}} \mod N\).
Each squaring takes \(O(\log^2 N)\) and there are \(\log y\) multiplications
To determine \(x^y \mod N\) multiply together the subset of these powers corresponding to \(1\) s in the binary representation of \(y\).
EXAMPLE
algorithm decomposition
\(x^{25} = x^{11001_2} = x^{10000_2} \cdot x^{1000_2} \cdot x^{1_2} = x^{16} \cdot x^8 \cdot x^1\)
For multiplication the terms \(x \cdot 2^i\) come from repeated doubling. For exponentiation the terms \(x^{2^i}\) come from repeated squaring
This algorithm implements the following recursive rule.
\( x^y = \begin{cases} (x^{\lfloor y/2 \rfloor})^2 & \text{if \textit{y} is even} \\ x \cdot (x^{\lfloor y/2 \rfloor})^2 & \text{if \textit{y} is odd} \\ \end {cases} \)
INPUT two n-bit integers x and N, and an integer exponent y
OUTPUT x^y mod N
MODEXP (x, y, N)
1 if y = 0
2 return 1
3
4 z = MODEXP(x, floor(y/2), N)
5
6 if even(y)
7 return z^2 mod N
8 else
9 return xz^2 mod N
Correctness
The recursive rule is transparently correct. Checking that the algorithm is correct is a matter of verifying that it mimics the rule and that it handles the base case \(y = 1\) properly.
Complexity
Let \(n\) be the size in bits of \(x\), \(y\), and \(N\) (whichever is the largest of the three). As with multiplication, the algorithm will halt after at most \(n\) recursive calls and during each call it multiplies \(n\)-bit numbers (doing computation modulo \(N\) saves us here) for a total running time of
\(T(n) = \underbrace{\quad\quad O(n) \quad\quad}_{\text{recursive calls}} \times \underbrace{\quad\quad O(n^2) \quad\quad}_{\text{multiplication}} = O(n^3)\)
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\)
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#
2006 Dasgupta, Sanjoy; Christos Papadimitriou; & Umesh Vazirani. Algorithms. Chapter 1. McGraw-Hill.
2018 Rosen, Kenneth. Discrete Mathematics and its Applications 8e. McGraw-Hill.
2023 Vaughan, Robert. A Course of Elementary Number Theory.