Primitive Roots

Primitive Roots #

The residue class modulo \(m\) is called a ring and denoted by \(\mathbb{Z}_m\) or \(\mathbb{Z}/m\mathbb{Z}\).

We will examine its multiplicative structure; in particular, we will consider the reduced residue classes modulo \(m\).

Order a modulo m #

What happens if we take powers of a fixed residue?

DEFINITION [Vaughan Definition 4.1]

Given \(m \in \mathbb{N}^+\), \(a \in \mathbb{Z}\), and \(\gcd(a, m) = 1\) we define the order \(\text{ord}_m(a)\) of \(a\) modulo \(m\) to be the smallest positive integer \(t\) such that

\(a^t \equiv 1 \mod m\)

We may express this by saying that \(a\) belongs to the exponent \(t\) modulo \(m\), or that \(t\) is the order of \(a\) modulo \(m\).

Note that by Euler’s theorem \(a^{\phi(m)} \equiv 1 \mod m\) so that \(\text{ord}_m(a)\) exists. Its uniqueness follows from its minimality.

EXAMPLE

\( \begin{aligned} a^t & \equiv 1 \mod m && \implies & m & \mid (a^t - 1) && && && \text{ord}_m(a) \\ \hline 2^2 & \equiv 1 \mod 3 && \implies & 3 & \mid (2^2 - 1) && = 3 && = 3 && \text{ord}_3(2) && = 2 \\ 2^4 & \equiv 1 \mod 5 && \implies & 5 & \mid (2^4 - 1) && = 15 && = 3 \times 5 && \text{ord}_5(2) && = 4 \\ 2^6 & \equiv 1 \mod 7 && \implies & 7 & \mid (2^6 - 1) && = 63 && = 3^2 \times 7 && \text{ord}_7(2) && = 6 \\ 2^6 & \equiv 1 \mod 9 && \implies & 9 & \mid (2^6 - 1) && = 63 && = 3^2 \times 7 && \text{ord}_9(2) && = 6 \\ 2^{10} & \equiv 1 \mod 11 && \implies & 11 & \mid (2^{10} - 1) && = 1023 && = 3 \times 11 \times 31 && \text{ord}_{11}(2) && = 10 \\ 2^{12} & \equiv 1 \mod 13 && \implies & 13 & \mid (2^{12} - 1) && = 4095 && = 3^2 \times 5 \times 7 \times 13 && \text{ord}_{13}(2) && = 12 \\ 2^4 & \equiv 1 \mod 15 && \implies & 15 & \mid (2^4 - 1) && = 15 && = 3 \times 5 && \text{ord}_{15}(2) && = 4 \\ \vdots \\ 3^1 & \equiv 1 \mod 2 && \implies & 2 & \mid (3^1 - 1) && = 2 && = 2 && \text{ord}_2(3) && = 1 \\ 3^2 & \equiv 1 \mod 4 && \implies & 4 & \mid (3^2 - 1) && = 8 && = 2^3 && \text{ord}_4(3) && = 2 \\ 3^4 & \equiv 1 \mod 5 && \implies & 5 & \mid (3^4 - 1) && = 80 && = 2^4 \times 5 && \text{ord}_5(3) && = 4 \\ 3^6 & \equiv 1 \mod 7 && \implies & 7 & \mid (3^6 - 1) && = 728 && = 2^3 \times 7 \times 13 && \text{ord}_7(3) && = 6 \\ 3^2 & \equiv 1 \mod 8 && \implies & 8 & \mid (3^2 - 1) && = 8 && = 2^3 && \text{ord}_8(3) && = 2 \\ 3^4 & \equiv 1 \mod 10 && \implies & 10 & \mid (3^4 - 1) && = 80 && = 2^4 \times 5 && \text{ord}_{10}(3) && = 4 \\ 3^5 & \equiv 1 \mod 11 && \implies & 11 & \mid (3^5 - 1) && = 242 && = 2 \times 11^2 && \text{ord}_{11}(3) && = 5 \\ 3^3 & \equiv 1 \mod 13 && \implies & 13 & \mid (3^3 - 1) && = 26 && = 2 \times 13 && \text{ord}_{13}(3) && = 3 \\ 3^6 & \equiv 1 \mod 14 && \implies & 14 & \mid (3^6 - 1) && = 728 && = 2^3 \times 7 \times 13 && \text{ord}_{14}(3) && = 6 \\ \end {aligned} \)

We can do better than that.

THEOREM [Vaughan Theorem 4.2]

Suppose that \(m \in \mathbb{N}^+\), \(\gcd(a, m) = 1\), and \(n \in \mathbb{N}^+\) is such that \(a^n \equiv 1 \mod m\).

Then \(\text{ord}_m(a) \mid n\). In particular \(\text{ord}_m(a) \mid \phi(m)\).

PROOF

For concision let \(t = \text{ord}_m(a)\).

Since \(t\) is minimal we have \(t \le n\).

Thus by the division algorithm there are \(q\) and \(r\) with \(0 \le r \lt t\) such that

\(n = qt + r\)

Hence \(a^r \equiv (a^t)^q a^r = a^{qt + r} = a^n \equiv 1 \mod m\).

\( \begin{aligned} a^t &\equiv 1 & \mod m \\ (a^t)^q &\equiv 1 & \mod m \\ (a^t)^q a^r &\equiv a^r & \mod m \\ a^n &\equiv a^r & \mod m \\ \end {aligned} \)

Thus \(a^r \equiv 1 \mod m\)

But \(0 \le r \lt t\). If \(r \gt 0\) then we would contradict the minimality of \(t\).

Hence \(r = 0\) and so \(n = qt + 0 \implies t \mid n\).

\(\blacksquare\)

Here is an application that will be made use of later.

THEOREM [Vaughan Theorem 4.3]

Suppose that \(d \mid (p - 1)\). Then the congruence

\(x^d \equiv 1 \mod p\)

has exactly \(d\) solutions.

PROOF

\(d \mid (p - 1) \implies x^d \mid x^{p-1} \implies (x^d - 1) \mid (x^{p-1} - 1) \implies x^{p-1} - 1 = (x^d - 1)q(x)\) where \(q(x)\) is a polynomial of degree \(p - 1 - d\).

\(d \mid (p - 1) \implies p - 1 = kd \implies x^{p-1} - 1 = x^{kd} - 1\)

\( \begin{aligned} x^{kd} - 1 &= (x^d - 1)(x^{(k-1)d} + x^{(k-2)d} + x^{(k-3)d} + x^{(k-4)d} + \dotsb + x^d + 1) \\ &= (x^{(k-1)d+d} + x^{(k-2)d+d} + x^{(k-3)d+d} + x^{(k-4)d+d} + \dotsb + x^{2d} + x^d) &- (x^{(k-1)d} + x^{(k-2)d} + \dotsb + x^d + 1) \\ &= (x^{kd} + x^{kd-d} + x^{kd-2d} + x^{kd-3d} \dotsb + x^{2d} + x^d) &- (x^{(k-1)d} + x^{(k-2)d} + \dotsb + x^d + 1) \\ &= (x^{kd} + x^{(k-1)d} + x^{(k-2)d} + x^{(k-3)d} \dotsb + x^{2d} + x^d) &- (x^{(k-1)d} + x^{(k-2)d} + \dotsb + x^d + 1) \\ \end {aligned} \)

Observe that the terms telescope (i.e., all terms but two cancel each other out). To see this with \(p-1\)

\( \begin{aligned} x^{p-1} - 1 &= (x^d - 1)(x^{p-1-d} + x^{p-1-2d} + x^{p-1-3d} + x^{p-1-4d} + \dotsb + x^d + 1) \\ &= (x^{p-1+(d-d)} + x^{p-1+(d-2d)} + x^{p-1+(d-3d)} + x^{p-1+(d-4d)} + \dotsb + x^{2d} + x^d) - (x^{p-1-d} + x^{p-1-2d} + x^{p-1-3d} + x^{p-1-4d} + \dotsb + x^d + 1) \\ \end {aligned} \)

We know from Euler’s theorem that there are exactly \(p-1\) incongruent roots to the lefthand side modulo \(p\).

\(x^{p-1} \equiv 1 \mod p\)

On the other hand, by Lagrange’s theorem, the second factor has at most \(p - 1 - d\) such roots, so the first factor must account for at least \(d\) of them. On the other hand, again by Lagrange’s theorem, the second factor has at most \(d\) roots modulo \(p\). Therefore

\(x^d \equiv 1 \mod p\)

\(\blacksquare\)

EXAMPLE

\( \begin{aligned} x^d & \equiv 1 \mod p & \\ \hline x & \equiv 1 \mod 2 & x &= 1 \\ \hline x & \equiv 1 \mod 3 & x &= 1 \\ x^2 & \equiv 1 \mod 3 & x &= 1, 2 \\ \hline x & \equiv 1 \mod 5 & x &= 1 \\ x^2 & \equiv 1 \mod 5 & x &= 1, 4 \\ x^4 & \equiv 1 \mod 5 & x &= 1, 2, 3, 4 \\ \hline x & \equiv 1 \mod 7 & x &= 1 \\ x^2 & \equiv 1 \mod 7 & x &= 1, 6 \\ x^3 & \equiv 1 \mod 7 & x &= 1, 2, 4 \\ x^6 & \equiv 1 \mod 7 & x &= 1, 2, 3, 4, 5, 6 \\ \hline x & \equiv 1 \mod 11 & x &= 1 \\ x^2 & \equiv 1 \mod 11 & x &= 1, 10 \\ x^5 & \equiv 1 \mod 11 & x &= 1, 3, 4, 5, 9 \\ x^{10} & \equiv 1 \mod 11 & x &= 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \\ \hline \end {aligned} \)

We have now seen that when \(\gcd(a, m) = 1\) it is the case that \(a\) has order modulo \(m\) which divides \(\phi(m)\). One question that can be asked is given any \(d \mid \phi(m)\) are there elements of order \(d\)? In the special case \(d = \phi(m)\) this would mean that

\(a, a^2, \dotsc, a^{\phi(m)}\)

are distinct modulo \(m\) because otherwise we would have

\(a^u \equiv a^v \mod m\) with \(1 \le u \lt v \le \phi(m)\)

and then

\(a^{v-u} \equiv 1 \mod m\) with \(1 \le v-u \lt \phi(m)\)

contradicting the assumption that \(\text{ord}_m(a) = \phi(m)\) is minimal.

\( \begin{aligned} a^t \equiv 1 \mod m && \text{ord}_m(a) = t \\ \hline 1^t \equiv 1 \mod 7 && \text{ord}_7(1) = 1 \\ 2^t \equiv 1 \mod 7 && \text{ord}_7(2) = 3 \\ 3^t \equiv 1 \mod 7 && \text{ord}_7(3) = 6 \\ 4^t \equiv 1 \mod 7 && \text{ord}_7(4) = 3 \\ 5^t \equiv 1 \mod 7 && \text{ord}_7(5) = 6 \\ 6^t \equiv 1 \mod 7 && \text{ord}_7(6) = 2 \\ \end {aligned} \)

There is one element of order \(1\), one element of order \(2\), two of order \(3\), and two of order \(6\).

Is it a fluke that for each \(d \mid 6 = \phi(7)\) the number of elements of order \(d\) is \(\phi(d)\)?

Primitive Root #

PRIMITIVE ROOT [Vaughan Definition 4.5]

Suppose that \(m \in \mathbb{N}^+\) and that \(\gcd(a, m) = 1\).

If \(\text{ord}_m(a) = \phi(m)\) then we say that \(a\) is a primitive root modulo \(m\).

In other words, a primitive root of a prime \(p\) is an integer \(r\) s.t. every integer not divisible by \(p\) is congruent to a power \(r\) modulo \(p\).

We know that we do not always have primitive roots. For example, any number \(a\) with \(\gcd(a, 8) = 1\) is odd and so \(a^2 \equiv 1 \mod 8\) whereas \(\phi(8) = 4\).

There are primitive roots to some moduli. For example, modulo \(7\) the powers of \(3\) are successively \(3, 2, 6, 4, 5, 1\).

\( \begin{aligned} 3^1 \equiv 3 \mod 7 \\ 3^2 \equiv 2 \mod 7 \\ 3^3 \equiv 6 \mod 7 \\ 3^4 \equiv 4 \mod 7 \\ 3^5 \equiv 5 \mod 7 \\ 3^6 \equiv 1 \mod 7 \\ \end {aligned} \)

How to determine whether \(a\) is a primitive root modulo \(p\)?

For each \(2 \le a \lt m\)

\(a^d \not\equiv 1 \mod p\) for all \(d \mid (p - 1)\) other than \(d = p - 1\)

Primitive roots modulo a prime #

Gauss determined precisely which moduli possess primitive roots. The first step is the case of prime modulus.

THEOREM (GAUSS) [Vaughan Theorem 4.6]

Suppose that \(p\) is prime and let \(d \mid (p - 1)\).

Then there are \(\phi(d)\) residue classes \(a\) with \(\text{ord}_p(a) = d\).

In particular, there are \(\phi(p - 1) = \phi(\phi(p))\) primitive roots modulo \(p\).

PROOF

We have seen that the order of every reduced residue class modulo \(p\) divides \(p-1\).

For a given \(d \mid (p - 1)\) let \(\psi(d)\) denote the number of reduced residues of order \(d\) modulo \(p\).

The congruence \(x^d \equiv 1 \mod p\) has exactly \(d\) solutions.

Thus every solution has order dividing \(d\).

Also each residue with order dividing \(d\) is a solution.

Thus for each \(d \mid (p - 1)\) we have

\( \begin{aligned} \sum_{r \mid d} \psi(r) = d \\ \end {aligned} \)

This is reminiscent of an earlier formula

\( \begin{aligned} \sum_{r \mid d} \phi(r) = d \\ \end {aligned} \)

Let \(1 = d_1 \lt d_2 \lt \dots \lt d_k = p - 1\) be the divisors of \(p-1\) in order.

We have a relationship

\( \begin{aligned} \sum_{r \mid d_j} \psi(r) = d_j \text{ for each } j = 1, 2, \dotsc \end {aligned} \)

and of course the sum is over a subset of the divisors of \(p - 1\). It is claimed that this determines \(\psi(d_j)\) uniquely. We can prove this by observing that if \(N\) is the number of positive divisors of \(p - 1\) then we have \(N\) linear equations in the \(N\) unknowns \(\psi(r)\) and we can write this in matrix notation

\(\psi \mathcal{U} = \mathbf{d}\)

Moreover \(\mathcal{U}\) is an upper triangular matrix with nonzero entries on the diagonal and so is invertible.

Hence the \(\psi(d_j)\) are uniquely determined.

But we already know a solution, namely \(\psi = \phi\).

\(\blacksquare\)

If we wish to avoid the linear algebra, starting from

\( \begin{aligned} \sum_{r \mid d_j} \psi(r) = d_j \text{ for each } j = 1, 2, \dotsc \\ \end {aligned} \)

we can prove uniqueness by induction on \(r\).

For the base case we have \(\psi(1) = 1\).

Then suppose \(\psi(d_1), \dotsc, \psi(d_j)\) are determined. Then we have

\( \begin{aligned} \sum_{r \mid d_{j+1}} \psi(r) = d_{j+1} \\ \end {aligned} \)

Hence

\( \begin{aligned} \psi(d_{j+1}) = d_{j+1} - \underset{r \lt d_{j+1}}{\sum_{r \mid d_{j+1}}} \psi(r) \\ \end {aligned} \)

and every term on the righthand side is already determined.

Thus we can conclude that there is only one solution to our system of equations.

But we already know this solution, namely \(\psi(r) = \phi(r)\).

\(\blacksquare\)

EXAMPLE

\(p = 13\)

\( \begin{pmatrix} \underset{1}{\psi(1)} & \underset{1}{\psi(2)} & \underset{2}{\psi(3)} & \underset{2}{\psi(4)} & \underset{2}{\psi(6)} & \underset{4}{\psi(12)} \\ \end {pmatrix} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end {pmatrix} = \)

\( \begin{pmatrix} \underset{1}{\psi(1)} &+& 0 &+& 0 &+& 0 &+& 0 &+& 0 \\ \underset{1}{\psi(1)} &+& \underset{1}{\psi(2)} &+& 0 &+& 0 &+& 0 &+& 0 \\ \underset{1}{\psi(1)} &+& 0 &+& \underset{2}{\psi(3)} &+& 0 &+& 0 &+& 0 \\ \underset{1}{\psi(1)} &+& \underset{1}{\psi(2)} &+& 0 &+& \underset{2}{\psi(4)} &+& 0 &+& 0 \\ \underset{1}{\psi(1)} &+& \underset{1}{\psi(2)} &+& \underset{2}{\psi(3)} &+& 0 &+& \underset{2}{\psi(6)} &+& 0 \\ \underset{1}{\psi(1)} &+& \underset{1}{\psi(2)} &+& \underset{2}{\psi(3)} &+& \underset{2}{\psi(4)} &+& \underset{2}{\psi(6)} &+& \underset{4}{\psi(12)} \\ \end {pmatrix}^\top = \begin{pmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 6 \\ 12 \\ \end {pmatrix}^\top \)

How about higher powers of odd primes?

THEOREM (GAUSS) [Vaughan Theorem 4.8]

We have primitive roots modulo \(m\) when \(m = 2\), \(m = 4\), \(m = p^k\), and \(m = 2p^k\) with \(p\) an odd prime, and in no other cases.

In applications one can usually reduce via the Chinese Remainder Theorem to powers of primes. Thus the lack of primitive roots for higher powers of \(2\) is a nuisance. Nevertheless, Gauss did prove something.

THEOREM (GAUSS) [Vaughan Theorem 4.9]

Suppose that \(k \ge 3\). Then the numbers \((-1)^u 5^v\) with \(u = 0, 1\) and \(0 \le v \lt 2^{k-2}\) form a set of reduced residues modulo \(2^k\).

Examining some moduli #

\(m = 2\)#

The order of \(1\) to any modulus \(m \gt 1\) is equal to \(1\).

\( \begin{aligned} 1^t &\equiv 1 \mod m & \text{ord}_m( 1) &= 1 \\ \end {aligned} \)

The order of any odd integer modulo \(2\) is equal to \(1\).

\( \begin{aligned} & \text{Totatives} &&& \phi(2) = 1 \\ & \text{Primitive Roots} &&& \phi(\phi(2)) = 1 \\ \end {aligned} \)

\( \text{Complete System of Residues} \\ \begin{aligned} a &= \{ mx + a \} && \\ \hline \bar{0} &= \{ 2x \} && \text{} \\ \bar{1} &= \{ 2x + 1 \} && \text{T, PR} \\ \end {aligned} \)

\( \text{Reduced Residues} \\ \begin{aligned} a^t &\equiv 1 \mod m \\ \hline (2x + 1) &\equiv 1 \mod 2 \\ \hline 1^t &\equiv 1 \mod 2 && \text{ord}_2(1) = 1 \\ 3^t &\equiv 1 \mod 2 && \text{ord}_2(3) = 1 \\ 5^t &\equiv 1 \mod 2 && \text{ord}_2(5) = 1 \\ 7^t &\equiv 1 \mod 2 && \text{ord}_2(7) = 1 \\ \vdots \end {aligned} \)

   a | ord(a) |  a^ 1
-----+--------+------
   1 |      1 |     1

\( \begin{aligned} x &\equiv 1 \mod 2 \text{ has 1 solution } & x &= 1 \\ \end {aligned} \)

 1 |  1

\(m = 3\)#

\( \begin{aligned} & \text{Totatives} &&& \phi(3) = 2 \\ & \text{Primitive Roots} &&& \phi(\phi(3)) = 1 \\ \end {aligned} \)

\(1 \equiv 2^2 \mod 3\)

\( \begin{array}{l} \text{Complete System of Residues} \\ \begin{aligned} a &= \{ mx + a \} \\ \hline \bar{0} &= \{ 3x \} \\ \bar{1} &= \{ 3x + 1 \} && \text{T} \\ \bar{2} &= \{ 3x + 2 \} && \text{T, PR} \\ \end {aligned} \end {array} \)

\( \begin{array}{l} \text{Reduced Residues} \\ \begin{aligned} a^t &\equiv 1 \mod m \\ \hline (3x + 1) &\equiv 1 \mod 3 && 1, 4, 7, 10, \dotsc \\ (3x + 2)^2 &\equiv 1 \mod 3 && 2, 5, 8, 11, \dotsc \\ \hline 1^t &\equiv 1 \mod 3 & \text{ord}_3( 1) &= 1 \\ 2^t &\equiv 1 \mod 3 & \text{ord}_3( 2) &= 2 \\ 4^t &\equiv 1 \mod 3 & \text{ord}_3( 4) &= 1 \\ 5^t &\equiv 1 \mod 3 & \text{ord}_3( 5) &= 2 \\ 7^t &\equiv 1 \mod 3 & \text{ord}_3( 7) &= 1 \\ 8^t &\equiv 1 \mod 3 & \text{ord}_3( 8) &= 2 \\ 10^t &\equiv 1 \mod 3 & \text{ord}_3(10) &= 1 \\ 11^t &\equiv 1 \mod 3 & \text{ord}_3(11) &= 2 \\ \vdots \end {aligned} \end {array} \)

PR(3)

   a | ord(a) |  a^ 1  a^ 2
-----+--------+------------
   1 |      1 |     1     1
   2 |      2 |     2     1

\( \begin{aligned} x &\equiv 1 \mod 3 \text{ has 1 solution } & x &= 1 \\ x^2 &\equiv 1 \mod 3 \text{ has 2 solutions} & x &= 1, 2 \\ \end {aligned} \)

# take an element from the first row and raise it to the power d, the value is the result modulo m
# thus, solutions are 1s
m = 3
for d in range(1,m):
  print(f"{d:>2} | {'  '.join([f'{x**d%m:>2}' for x in range(1,m)])}")

 1 |  1   2
 2 |  1   1

\( \begin{aligned} (3k + 2)^2 &= 9k^2 + 12k + 4 = 9k^2 + 12k + 3 + 1 \\ &= \underbrace{3(3k^2 + 4k + 1) + 1}_{3k + 1} \\ &\equiv 1 \mod 3 \\ \end {aligned} \)

\(m = 4\)#

\( \begin{aligned} & \text{Totatives} &&& \phi(4) = 2 \\ & \text{Primitive Roots} &&& = 1 \\ \end {aligned} \)

\( \begin{array}{l} \text{Complete System of Residues} \\ \begin{aligned} a &= \{ mx + a \} \\ \hline \bar{0} &= \{ 4x \} \\ \bar{1} &= \{ 4x + 1 \} && \text{T} \\ \bar{2} &= \{ 4x + 2 \} \\ \bar{3} &= \{ 4x + 3 \} && \text{T, PR} \impliedby \text{ord}_4(3) = \phi(4) \\ \end {aligned} \end {array} \)

\( \begin{array}{l} \text{Reduced Residues} \\ \begin{aligned} a^t &\equiv 1 \mod m \\ \hline (4k+1) &\equiv 1 \mod 4 && 1, 5, 9, 13, \dotsc \\ (4k+3)^2 &\equiv 1 \mod 4 && 3, 7, 11, 15, \dotsc \\ \hline 1^t &\equiv 1 \mod 4 & \text{ord}_4( 1) &= 1 \\ 3^t &\equiv 1 \mod 4 & \text{ord}_4( 3) &= 2 \\ 5^t &\equiv 1 \mod 4 & \text{ord}_4( 5) &= 1 \\ 7^t &\equiv 1 \mod 4 & \text{ord}_4( 7) &= 2 \\ 9^t &\equiv 1 \mod 4 & \text{ord}_4( 9) &= 1 \\ 11^t &\equiv 1 \mod 4 & \text{ord}_4(11) &= 2 \\ 13^t &\equiv 1 \mod 4 & \text{ord}_4(13) &= 1 \\ 15^t &\equiv 1 \mod 4 & \text{ord}_4(15) &= 2 \\ \vdots \end {aligned} \end {array} \)

\( \begin{aligned} (4k + 3)^2 &= 16k^2 + 24k + 9 = 16k^2 + 24k + 8 + 1 \\ &= \underbrace{4(4k^2 + 6k + 2) + 1}_{4k + 1} \\ &\equiv 1 \mod 4 \\ \end {aligned} \)

\(m = 5\)#

\( \begin{aligned} & \text{Totatives} &&& \phi(5) = 4 \\ & \text{Primitive Roots} &&& \phi(\phi(5)) = 2 \\ \end {aligned} \)

\(1 \equiv 2^4 \equiv 3^4 \equiv 4^2 \mod 5\)

\( \begin{array}{l} \text{Complete System of Residues} \\ \begin{aligned} a &= \{ mx + a \} \\ \hline \bar{0} &= \{ 5x \} \\ \bar{1} &= \{ 5x + 1 \} && \text{T} \\ \bar{2} &= \{ 5x + 2 \} && \text{T, PR} \\ \bar{3} &= \{ 5x + 3 \} && \text{T, PR} \\ \bar{4} &= \{ 5x + 4 \} && \text{T} \\ \end {aligned} \end {array} \)

\( \begin{array}{l} \text{Reduced Residues} \\ \begin{aligned} a^t &\equiv 1 \mod m \\ \hline (5k + 1) &\equiv 1 \mod 5 && 1, 6, 11, 16, \dotsc \\ (5k + 2)^4 &\equiv 1 \mod 5 && 2, 7, 12, 17, \dotsc \\ (5k + 3)^4 &\equiv 1 \mod 5 && 3, 8, 13, 18, \dotsc \\ (5k + 4)^2 &\equiv 1 \mod 5 && 4, 9, 14, 19, \dotsc \\ \hline 1^t &\equiv 1 \mod 5 & \text{ord}_5( 1) &= 1 \\ 2^t &\equiv 1 \mod 5 & \text{ord}_5( 2) &= 4 \\ 3^t &\equiv 1 \mod 5 & \text{ord}_5( 3) &= 4 \\ 4^t &\equiv 1 \mod 5 & \text{ord}_5( 4) &= 2 \\ 6^t &\equiv 1 \mod 5 & \text{ord}_5( 6) &= 1 \\ 7^t &\equiv 1 \mod 5 & \text{ord}_5( 7) &= 4 \\ 8^t &\equiv 1 \mod 5 & \text{ord}_5( 8) &= 4 \\ 9^t &\equiv 1 \mod 5 & \text{ord}_5( 9) &= 2 \\ \vdots \end {aligned} \end {array} \)

PR(5)

   a | ord(a) |  a^ 1  a^ 2  a^ 3  a^ 4
-----+--------+------------------------
   1 |      1 |     1     1     1     1
   2 |      4 |     2     4     3     1
   3 |      4 |     3     4     2     1
   4 |      2 |     4     1     4     1

\( \begin{aligned} x &\equiv 1 \mod 5 \text{ has 1 solution } & x &= 1 \\ x^2 &\equiv 1 \mod 5 \text{ has 2 solutions} & x &= 1, 4 \\ x^4 &\equiv 1 \mod 5 \text{ has 4 solutions} & x &= 1, 2, 3, 4 \\ \end {aligned} \)

|  1   2   3   4
|  1   4   4   1
|  1   3   2   4
|  1   1   1   1

\( \begin{aligned} (5k + 4)^2 &= 25k^2 + 40k + 16 = 25k^2 + 40k + 15 + 1 \\ &= \underbrace{5(5k^2 + 8k + 3) + 1}_{5k + 1} \\ (5k + 3)^4 &= (25k^2 + 30k + 9)^2 = (25k^2 + 30k + 5 + 4)^2 \\ &= \underbrace{(5(5k^2 + 6k + 1) + 4)^2}_{(5k + 4)^2} \\ (5k + 2)^4 &= (25k^2 + 20k + 4)^2 \\ &= \underbrace{(5(5k^2 + 4k) + 4)^2}_{(5k + 4)^2} \\ &\equiv 1 \mod 5 \\ \end {aligned} \)

\(m = 6\)#

\( \begin{aligned} & \text{Modulus} &&& 6 &= 2 \times 3 \\ & \text{Totatives} &&& \phi(6) &= 2 & = \phi(2 \times 3) = \phi(2)\phi(3) = 1 \times 2 \\ & \text{Primitive Roots} &&& &= 1 & \\ \end {aligned} \)

\( \begin{array}{l} \text{Complete System of Residues} \\ \begin{aligned} a &= \{ mx + a \} \\ \hline \bar{0} &= \{ 6x \} \\ \bar{1} &= \{ 6x + 1 \} && \text{T} \\ \bar{2} &= \{ 6x + 2 \} \\ \bar{3} &= \{ 6x + 3 \} \\ \bar{4} &= \{ 6x + 4 \} \\ \bar{5} &= \{ 6x + 5 \} && \text{T, PR} \impliedby \text{ord}_6(5) = \phi(6) \\ \end {aligned} \end {array} \)

\( \begin{array}{l} \text{Reduced Residues} \\ \begin{aligned} a^t &\equiv 1 \mod m \\ \hline (6x + 1) &\equiv 1 \mod 6 && 1, 7, 13, 19, \dotsc \\ (6x + 5)^2 &\equiv 1 \mod 6 && 5, 11, 17, 23, \dotsc \\ \hline 1^t &\equiv 1 \mod 6 & \text{ord}_6( 1) &= 1 \\ 5^t &\equiv 1 \mod 6 & \text{ord}_6( 5) &= 2 \\ 7^t &\equiv 1 \mod 6 & \text{ord}_6( 7) &= 1 \\ 11^t &\equiv 1 \mod 6 & \text{ord}_6(11) &= 2 \\ 13^t &\equiv 1 \mod 6 & \text{ord}_6(13) &= 1 \\ 17^t &\equiv 1 \mod 6 & \text{ord}_6(17) &= 2 \\ 19^t &\equiv 1 \mod 6 & \text{ord}_6(19) &= 1 \\ 23^t &\equiv 1 \mod 6 & \text{ord}_6(23) &= 2 \\ \vdots \end {aligned} \end {array} \)

\( \begin{aligned} (6k + 5)^2 &= 36k^2 + 60k + 25 = 36k^2 + 60k + 24 + 1 \\ &= \underbrace{6(6k^2 + 10k + 4) + 1}_{6k + 1} \\ &\equiv 1 \mod 6 \end {aligned} \)

\(m = 7\)#

\( \begin{aligned} & \text{Modulus} &&& 7 \\ & \text{Totatives} &&& \phi(7) = 6 \\ & \text{Primitive Roots} &&& \phi(\phi(7)) = 2 \\ \end {aligned} \)

\(1 \equiv 2^3 \equiv 3^6 \equiv 4^3 \equiv 5^6 \equiv 6^2 \mod 7\)

\( \begin{array}{l} \text{Complete System of Residues} \\ \begin{aligned} a &= \{ mx + a \} & &&& \text{Reduced} && \text{Order} &&& a^t &\equiv 1 \mod m \\ \hline \bar{0} &= \{ 7x \} & &&& && &&& \\ \bar{1} &= \{ 7x + 1 \} =& 1, 8, 15, 22, \dotsc &&& \text{T} && 1 &&& (7x + 1) &\equiv 1 \mod 7 \\ \bar{2} &= \{ 7x + 2 \} =& 2, 9, 16, 23, \dotsc &&& \text{T} && 3 &&& (7x + 2)^3 &\equiv 1 \mod 7 \\ \bar{3} &= \{ 7x + 3 \} =& 3, 10, 17, 24, \dotsc &&& \text{T, PR} && 6 &&& (7x + 3)^6 &\equiv 1 \mod 7 \\ \bar{4} &= \{ 7x + 4 \} =& 4, 11, 18, 25, \dotsc &&& \text{T} && 3 &&& (7x + 4)^3 &\equiv 1 \mod 7 \\ \bar{5} &= \{ 7x + 5 \} =& 5, 12, 19, 26, \dotsc &&& \text{T, PR} && 6 &&& (7x + 5)^6 &\equiv 1 \mod 7 \\ \bar{6} &= \{ 7x + 6 \} =& 6, 13, 20, 27, \dotsc &&& \text{T} && 2 &&& (7x + 6)^2 &\equiv 1 \mod 7 \\ \hline \end {aligned} \end {array} \)

PR(7)

   a | ord(a) |  a^ 1  a^ 2  a^ 3  a^ 4  a^ 5  a^ 6
-----+--------+------------------------------------
|      1 |     1     1     1     1     1     1
|      3 |     2     4     1     2     4     1
|      6 |     3     2     6     4     5     1
|      3 |     4     2     1     4     2     1
|      6 |     5     4     6     2     3     1
|      2 |     6     1     6     1     6     1

\( \begin{aligned} x &\equiv 1 \mod 7 \text{ has 1 solution } & x &= 1 \\ x^2 &\equiv 1 \mod 7 \text{ has 2 solutions} & x &= 1, 6 \\ x^3 &\equiv 1 \mod 7 \text{ has 3 solutions} & x &= 1, 2, 4 \\ x^6 &\equiv 1 \mod 7 \text{ has 6 solutions} & x &= 1, 2, 3, 4, 5, 6 \\ \end {aligned} \)

|  1   2   3   4   5   6
|  1   4   2   2   4   1
|  1   1   6   1   6   6
|  1   2   4   4   2   1
|  1   4   5   2   3   6
|  1   1   1   1   1   1

\( \begin{aligned} (7k + 2)^3 &= (49k^2 + 28k + 4)(7k + 2) \\ &= (7\underbrace{(7k^2 + 4k)}_k + 4)(7k + 2) \\ &= 49k^2 + 42k + 8 = 49k^2 + 42k + 7 + 1 \\ &= 7(\underbrace{7k^2 + 6k + 1}_k) + 1 \\ (7k + 3)^6 &= (49k^2 + 42k + 9)^3 = (49k^2 + 42k + 7 + 2)^3 \\ &= (7\underbrace{(7k^2 + 6k + 1)}_k + 2)^3 \\ (7k + 4)^3 &= (49k^2 + 56k + 16)(7k + 4) = (49k^2 + 56k + 14 + 2)(7k + 4) \\ &= (7(\underbrace{7k^2 + 8k + 2}_k) + 2)(7k + 4) \\ (7k + 5)^6 &= (49k^2 + 70k + 25)^3 = (49k^2 + 70k + 21 + 4)^3 \\ &= (7(\underbrace{7k^2 + 10k + 3}_k) + 4)^3 \\ (7k + 6)^2 &= 49k^2 + 84k + 36 = 49k^2 + 84k + 35 + 1 \\ &= 7\underbrace{(7k^2 + 12k + 5)}_k + 1 \\ \end {aligned} \)

\(m = 8\)#

\( \begin{aligned} & \text{Modulus} &&& 8 &= 2^3 \\ & \text{Totatives} &&& \phi(8) &= 4 \\ & \text{Primitive Roots} &&& &= 0 \\ \end {aligned} \)

\(1 \equiv 3^2 \equiv 5^2 \equiv 7^2 \mod 8\)

\( \begin{array}{l} \text{Complete System of Residues} \\ \begin{aligned} a &= \{ mx + a \} && \text{Reduced} && \text{Order } t &&& a^t &\equiv 1 \mod m \\ \hline \bar{0} &= \{ 8x \} && && &&& \\ \bar{1} &= \{ 8x + 1 \} && \text{T} && 1 &&& (8x + 1) &\equiv 1 \mod 8 \\ \bar{2} &= \{ 8x + 2 \} && && &&& \\ \bar{3} &= \{ 8x + 3 \} && \text{T} && 2 &&& (8x + 3)^2 &\equiv 1 \mod 8 \\ \bar{4} &= \{ 8x + 4 \} && && &&& \\ \bar{5} &= \{ 8x + 5 \} && \text{T} && 2 &&& (8x + 5)^2 &\equiv 1 \mod 8 \\ \bar{6} &= \{ 8x + 6 \} && && &&& \\ \bar{7} &= \{ 8x + 7 \} && \text{T} && 2 &&& (8x + 7)^2 &\equiv 1 \mod 8 \\ \hline \end {aligned} \end {array} \)

\(m = 11\)#

\( \begin{aligned} & \text{Modulus} & & & 11 & \\ & \text{Totatives} & \phi(11) & = & 10 & \\ & \text{Primitive Roots} & \phi(\phi(11)) & = & 4 & = \phi(2 \times 5) = \phi(2)\phi(5) = 1 \times 4 \\ \end {aligned} \)

\(1 \equiv 2^{10} \equiv 3^5 \equiv 4^5 \equiv 5^5 \equiv 6^{10} \equiv 7^{10} \equiv 8^{10} \equiv 9^5 \equiv 10^2 \mod 11\)

\( \begin{array}{l} \text{Complete System of Residues} \\ \begin{aligned} a &= \{ mx + a \} && \text{Reduced} & \text{Order} && a^t &\equiv 1 \mod m \\ \hline \bar{ 0} &= \{11x \} && & && \\ \bar{ 1} &= \{11x + 1 \} && \text{T} & 1 && (11x + \phantom{1}1)\phantom{^{15}} &\equiv 1 \mod 11 \\ \bar{ 2} &= \{11x + 2 \} && \text{T, PR} & 10 && (11x + \phantom{1}2)^{10} &\equiv 1 \mod 11 \\ \bar{ 3} &= \{11x + 3 \} && \text{T} & 5 && (11x + \phantom{1}3)^{\phantom{1}5} &\equiv 1 \mod 11 \\ \bar{ 4} &= \{11x + 4 \} && \text{T} & 5 && (11x + \phantom{1}4)^{\phantom{1}5} &\equiv 1 \mod 11 \\ \bar{ 5} &= \{11x + 5 \} && \text{T} & 5 && (11x + \phantom{1}5)^{\phantom{1}5} &\equiv 1 \mod 11 \\ \bar{ 6} &= \{11x + 6 \} && \text{T, PR} & 10 && (11x + \phantom{1}6)^{10} &\equiv 1 \mod 11 \\ \bar{ 7} &= \{11x + 7 \} && \text{T, PR} & 10 && (11x + \phantom{1}7)^{10} &\equiv 1 \mod 11 \\ \bar{ 8} &= \{11x + 8 \} && \text{T, PR} & 10 && (11x + \phantom{1}8)^{10} &\equiv 1 \mod 11 \\ \bar{ 9} &= \{11x + 9 \} && \text{T} & 5 && (11x + \phantom{1}9)^{\phantom{1}5} &\equiv 1 \mod 11 \\ \bar{10} &= \{11x + 10 \} && \text{T} & 2 && (11x + 10)^{\phantom{1}2} &\equiv 1 \mod 11 \\ \hline \end {aligned} \end {array} \)

\( \begin{aligned} 2 \not\equiv && 2^2 && \not\equiv && \underset{\equiv 10}{2^5} & \not\equiv 1 \mod 11 \\ 3 \not\equiv && 3^2 && \not\equiv && \boxed{3^5} & \equiv 1 \mod 11 \\ 4 \not\equiv && 4^2 && \not\equiv && \boxed{4^5} & \equiv 1 \mod 11 \\ 5 \not\equiv && 5^2 && \not\equiv && \boxed{5^5} & \equiv 1 \mod 11 \\ 6 \not\equiv && 6^2 && \not\equiv && \underset{\equiv 10}{6^5} & \not\equiv 1 \mod 11 \\ 7 \not\equiv && 7^2 && \not\equiv && \underset{\equiv 10}{7^5} & \not\equiv 1 \mod 11 \\ 8 \not\equiv && 8^2 && \not\equiv && \underset{\equiv 10}{8^5} & \not\equiv 1 \mod 11 \\ 9 \not\equiv && 9^2 && \not\equiv && \boxed{9^5} & \equiv 1 \mod 11 \\ 10 \not\equiv && \boxed{10^2} && && & \equiv 1 \mod 11 \\ \end {aligned} \)

PR(11)

   a | ord(a) |  a^ 1  a^ 2  a^ 3  a^ 4  a^ 5  a^ 6  a^ 7  a^ 8  a^ 9  a^10
-----+--------+------------------------------------------------------------
|      1 |     1     1     1     1     1     1     1     1     1     1
|     10 |     2     4     8     5    10     9     7     3     6     1
|      5 |     3     9     5     4     1     3     9     5     4     1
|      5 |     4     5     9     3     1     4     5     9     3     1
|      5 |     5     3     4     9     1     5     3     4     9     1
|     10 |     6     3     7     9    10     5     8     4     2     1
|     10 |     7     5     2     3    10     4     6     9     8     1
|     10 |     8     9     6     4    10     3     2     5     7     1
|      5 |     9     4     3     5     1     9     4     3     5     1
|      2 |    10     1    10     1    10     1    10     1    10     1

Solutions to congruences of the form \(x^d \equiv 1 \mod p\)

\( \begin{aligned} x & \equiv 1 \mod 11 && x = 1 \\ x^2 & \equiv 1 \mod 11 && x = 1, 10 \\ x^5 & \equiv 1 \mod 11 && x = 1, 3, 4, 5, 9 \\ x^{10} & \equiv 1 \mod 11 && x = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \\ \end {aligned} \)

|  1   2   3   4   5   6   7   8   9  10
|  1   4   9   5   3   3   5   9   4   1
|  1   8   5   9   4   7   2   6   3  10
|  1   5   4   3   9   9   3   4   5   1
|  1  10   1   1   1  10  10  10   1  10
|  1   9   3   4   5   5   4   3   9   1
|  1   7   9   5   3   8   6   2   4  10
|  1   3   5   9   4   4   9   5   3   1
|  1   6   4   3   9   2   8   7   5  10
|  1   1   1   1   1   1   1   1   1   1

\(m = 13\)#

\(1 \equiv 2^{12} \equiv 3^3 \equiv 4^6 \equiv 5^4 \equiv 6^{12} \equiv 7^{12} \equiv 8^4 \equiv 9^3 \equiv 10^6 \equiv 11^{12} \equiv 12^2 \mod 13\)

PR(13)

   a | ord(a) |  a^ 1  a^ 2  a^ 3  a^ 4  a^ 5  a^ 6  a^ 7  a^ 8  a^ 9  a^10  a^11  a^12
-----+--------+------------------------------------------------------------------------
|      1 |     1     1     1     1     1     1     1     1     1     1     1     1
|     12 |     2     4     8     3     6    12    11     9     5    10     7     1
|      3 |     3     9     1     3     9     1     3     9     1     3     9     1
|      6 |     4     3    12     9    10     1     4     3    12     9    10     1
|      4 |     5    12     8     1     5    12     8     1     5    12     8     1
|     12 |     6    10     8     9     2    12     7     3     5     4    11     1
|     12 |     7    10     5     9    11    12     6     3     8     4     2     1
|      4 |     8    12     5     1     8    12     5     1     8    12     5     1
|      3 |     9     3     1     9     3     1     9     3     1     9     3     1
|      6 |    10     9    12     3     4     1    10     9    12     3     4     1
|     12 |    11     4     5     3     7    12     2     9     8    10     6     1
|      2 |    12     1    12     1    12     1    12     1    12     1    12     1

Discrete Logarithms #

As an application of primitive roots we can say something when \(p\) is odd about the solution of congruences of the form

\(x^k \equiv a \mod p\)

The case \(a = 0\) is easy. The only solution is \(x \equiv 0 \mod p\).

\( \begin{aligned} x^k & \equiv & \underset{a}{0} & \mod p && \implies p \mid x^k \\ x & \equiv & \underset{a}{0} & \mod p && \implies p \mid x \\ \end {aligned} \)

(Remember that \(p \mid x^k \implies p \mid x\))

Suppose \(a \not\equiv 0 \mod p \quad\quad \implies p \nmid a\).

Claim

Suppose \(x^k \equiv a \mod p\) and \(a \not\equiv 0 \mod p \iff p \nmid \pm a\). Then \(p \nmid x\).

Proof by contradiction

\(p \mid x \iff x \equiv 0 \mod p\) implies that \((0)^k = 0 \equiv a \mod p\). Contradiction. Thus \(p \nmid x \iff p \nmid x^k\).

Then pick a primitive root \(g\) modulo \(p\), and a \(c\) so that

\(g^c \equiv a \mod p\)

Also, since any solution \(x\) will have \(p \nmid x\) we can define \(y\) so that

\(g^y \equiv x \mod p\)

(This works because no power \(y\) of a primitive root \(g\) will be congruent to \(0\) the modulus, while some \(y\) will produce a congruence to any \(x \not\equiv 0\).)

\( \begin{aligned} g^{p-1} &\equiv 1 & \mod p \\ g^c &\equiv x^k \equiv a & \mod p \\ g^y &\equiv x & \mod p &&& \text{definition} \\ (g^y)^k &\equiv x^k & \mod p &&& \text{raise to the k-th power} \\ \end {aligned} \)

Thus our congruence becomes

\(g^{ky} \equiv g^c \mod p\).

Hence it follows that

\(ky \equiv c \mod p - 1\)

We have turned a polynomial congruence into a linear one. This is a bit like using logarithms on real numbers.

The exponents \(c\) and \(y\) are called the discrete logarithms modulo \(p\) to the base \(g\). Computing them numerically is hard and there is a protocol called Diffie-Hellman which uses them to exchange secure keys and passwords.

Our new congruence is soluble iff

\(\gcd(k, p - 1) \mid c\)

and when this holds the \(y\) which satisfy it lie in a residue class modulo \(\frac{p - 1}{\gcd(k, p - 1)}\). In other words, \(\gcd(k, p - 1)\) residue classes modulo \(p - 1\).

Thus when \(a \not\equiv 0 \mod p\) the original congruence is either insoluble or has \(\gcd(k, p - 1)\) solutions.

The following theorem was just proved above.

THEOREM [Vaughan Theorem 4.10]

Suppose \(p\) is an odd prime. When \(p \nmid a\) the congruence

\(x^k \equiv a \mod p\)

has \(0\) or \(\gcd(k, p - 1)\) solutions, and the number of reduced residues \(a\) modulo \(p\) for which it is soluble is

\( \begin{aligned} \frac{p - 1}{\gcd(k, p - 1)} \end {aligned} \)

The previous theorem suggests the following.

DISCRETE LOGARITHM [Vaughan Definition 4.11]

Given a primitive root \(g\) and a reduced residue class \(a\) modulo \(m\) we define the discrete logarithm

\(\text{dlog}_g(a)\)

or index \(\text{ind}_g(a)\) to be that unique residue class \(\ell\) modulo \(\phi(m)\) such that

\(g^\ell \equiv a \mod m\)

The notation \(\text{ind}_g(a)\) is more commonly used, but \(\text{dlog}_g(a)\) seems more natural.

EXAMPLE

Find a primitive root modulo \(11\) and construct a table of discrete logarithms.

Table of powers of \(g\) modulo \(11\).

\( \begin{array}{lrrrrrrrrrr} y & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline x \equiv 2^y & 2 & 4 & 8 & 5 & 10 & 9 & 7 & 3 & 6 & 1 \\ x \equiv 6^y & 6 & 3 & 7 & 9 & 10 & 5 & 8 & 4 & 2 & 1 \\ x \equiv 7^y & 7 & 5 & 2 & 3 & 10 & 4 & 6 & 9 & 8 & 1 \\ x \equiv 8^y & 8 & 9 & 6 & 4 & 10 & 3 & 2 & 5 & 7 & 1 \\ \end {array} \)

Inverse tables

\( \begin{array}{lrrrrrrrrrr} x & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline y \equiv \text{dlog}_2(x) & 10 & 1 & 8 & 2 & 4 & 9 & 7 & 3 & 6 & 5 \\ \hline \hline \\ x & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline y \equiv \text{dlog}_6(x) & 10 & 9 & 2 & 8 & 6 & 1 & 3 & 7 & 4 & 5 \\ \hline \hline \\ x & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline y \equiv \text{dlog}_7(x) & 10 & 3 & 4 & 6 & 2 & 7 & 1 & 9 & 8 & 5 \\ \hline \hline \\ x & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline y \equiv \text{dlog}_8(x) & 10 & 7 & 6 & 4 & 8 & 3 & 9 & 1 & 2 & 5 \\ \end {array} \)

Note that while \(x\) is a residue modulo \(p\), \(y\) is a resiude modulo \(p - 1\).

\(y\) is the order, or exponent, to which \(g\) has to be raised to give \(x\) modulo \(p\). In other words

\(x \equiv g^{\text{dlog}_g(x)} \mod p\)

We can use this to solve congruences.

EXAMPLE

Solve the congruence

\(x^3 \equiv 6 \mod 11\)

where \(k = 3\) and \(a \equiv 6 \mod 11\).

Choose a primitive root \(g = 2\) modulo \(11\) as a base for discrete logarithms.

\( \begin{aligned} x^3 & \equiv & 6 & \mod 11 \\ 2^c & \equiv & 6 & \mod 11 && 1 \\ 2^y & \equiv & x & \mod 11 && 3 \\ 2^{3y} & \equiv & 2^c & \mod 11 \\ 3y & \equiv & c & \mod 10 && 2 \\ \end {aligned} \)

Which power \(c\) of \(2\) is congruent to \(6\). In the inverse table, \(x = 6\) and the corresponding entry \(y = 9\).

\(2^9 \equiv 6 \mod 11\)

Now we must solve \(3y \equiv 9 \mod 10\) which has the unique solution \(y \equiv 3 \mod 10\).

\(\underset{g}{2}\) to the power \(\underset{y}{3}\) produces which \(x\) modulo \(11\)? In the table of discrete logarithms, \(y = 3\) and the corresponding entry \(x = 8\).

\(2^3 \equiv x \equiv 8 \mod 11\)

8**3%11

EXAMPLE

Solve the congruence

\(x^5 \equiv 9 \mod 11\)

where \(k = 5\) and \(a \equiv 9 \mod 11\).

\( \begin{aligned} 2^6 \equiv 9 \mod 11 \\ 5y \equiv 6 \mod 10 \\ \end {aligned} \)

\(\gcd(\underset{k}{5}, \underset{p-1}{10}) = 5 \nmid \underset{c}{6}\) and so this congruence is insoluble.

EXAMPLE

Solve the congruence

\(x^{65} \equiv 10 \mod 11\)

where \(k = 65\) and \(a \equiv 10 \mod 11\).

\( \begin{aligned} 2^5 & \equiv & 10 & \mod 11 \\ 65y & \equiv & 5 & \mod 10 \\ 13y & \equiv & 1 & \mod 2 \\ y & \equiv & 1 & \mod 2 \\ \end {aligned} \)

\(\gcd(\underset{k}{65}, \underset{p-1}{10}) = 5 \mid \underset{c}{5}\) and so this congruence is soluble.

This congruence has one solution modulo \(2\)

\(y \equiv 1 \mod 2\)

and \(5\) solutions modulo \(10\).

\( \begin{aligned} & y \equiv 1, 3, 5, 7, 9 \mod 10 \\ & x \equiv 2, 8, 10, 7, 6 \mod 11 \\ \end {aligned} \)

[2**y % 11 for y in range(1, 10, 2)]

[2, 8, 10, 7, 6]

RSA #

In 1978 Rivest, Shamir, Adleman rediscovered an idea which had already been described internally at GCHQ by Cocks in 1973 and then shared with NSA, which is described as a way of sharing information by public key encryption.

RSA

Let \(n, d, e \in \mathbb{N}\) such that

\(de \equiv 1 \mod \phi(n)\)

Given a message \(M\) encoded as a number with \(M \lt n\) compute

\(E \equiv M^e \mod n\)

and transmit \(E\). The recipient then computes

\(E^d \mod n\)

Then

\(E^d \equiv (M^e)^d = M^{de} \equiv M \mod n\)

since \(\phi(n) \mid (de - 1)\)

and the recipient recovers the message.

The sender has to know only \(n\) and \(e\). The recipient has to know only \(n\) and \(d\). The level of security depends only on the ease with which one can find \(d\) knowing \(n\) and \(e\). The numbers \(n\) and \(e\) can be in the public domain. The crucial question is, given \(n\) and \(d\), the solubility of

\(de \equiv 1 \mod \phi(n)\)

and this in turn requires the value of \(\phi(n)\).

Suppose \(n\) is the product of two primes

\(n = pq\)

If \(n\) can be factored then we have

\(\phi(n) = (p - 1)(q - 1)\)

But this factorization is a known hard problem, especially when the primes are roughly of the same size. Of course if the value of \(\phi(n)\) can be discovered not only is the message easily broken, but \(n\) is easily factored since one has

\(p + q = pq + 1 - \phi(n) = n + 1 - \phi(n)\) and \(pq = n\)

and one can substitute for \(q\) and then solve the quadratic equation in \(p\).

In other words, knowing \(\phi(n)\) is equivalent to factoring \(n\).

Acknowledgements #

2023 Vaughan, Robert. A Course of Elementary Number Theory.

Primitive Roots

Contents