More about checking for primitive roots

Posted on October 25, 2013 by Dan Ma

Finding primitive roots modulo a number is of great interest in number theory, both in a theoretical standpoint and in a computational standpoint. In this post we compare and contrast three different ways of checking for primitive roots, continuing a discussion in an earlier post An elementary algorithm for finding primitive roots.

___________________________________________________________________________________________________________________

Background

Let $m$ be a positive integer. Let $a$ be a positive integer that is relative prime to $m$ . Let $\phi$ be Euler’s phi function, which counts the number of least residues that are relatively prime to the modulus. For example, $\phi(6)=2$ as $1$ and $5$ are the only numbers relatively prime to $6$ (out of the numbers $0,1,2,3,4,5$ ). Furthermore, $\phi(p)=p-1$ for any prime number $p$ . Previous posts on the phi function: Euler’s phi function, part 1 and Euler’s phi function, part 2.

Euler’s theorem tells us that $a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$ . By the order of $a$ modulo $m$ we mean the least positive exponent $k$ such that $a^{k} \equiv 1 \ (\text{mod} \ m)$ (Euler’s theorem indicates that this notion of order is well defined). The number $a$ is said to be a primitive root modulo $m$ if the order of $a$ modulo $m$ is $\phi(m)$ .

___________________________________________________________________________________________________________________

Three Checks

Let $m$ be a positive integer. Let $a$ be a positive integer that is relative prime to $m$ . How can we determine whether the number $a$ is a primitive root modulo $m$ ? We discuss three ways of answering this question.

Check # 1

$a^j \ (\text{mod} \ m)$

$j<\phi(m)$

If each such congruence $\not \equiv 1$ , then the number $a$ is a primitive root modulo $m$ .

____________________________________________________________________________________________

Check # 1 is merely a restatement of the definition of primitive root. It is a dumb test as it requires too much calculation. For large moduli, it would be an inefficient method of checking for primitive roots. The following is a much better test.

Check # 2

$a^j \ (\text{mod} \ m)$

$j$

$\phi(m)$

$j<\phi(m)$

If each such congruence $\not \equiv 1$ , then the number $a$ is a primitive root modulo $m$ .

____________________________________________________________________________________________

Check # 2 narrows down the checking by quite a bit – simply checking $a^j$ among the divisors of $\phi(m)$ . This works because the only possible numbers for the order modulo $m$ of the number $a$ are the divisors of $\phi(m)$ . So we can skip all $j$ that are not divisors of $\phi(m)$ . The following lemma shows why this is so. Actually, the lemma proves something more general. It shows that if $a^n \equiv 1 \ (\text{mod} \ m)$ , then the order of $a$ must be a divisor of $n$ . Euler’s theorem says that $a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$ . So the order of $a$ must be a divisor of $\phi(m)$ .

Lemma 1

$k$

$a$

$m$

$a^n \equiv 1 \ (\text{mod} \ m)$

$k \ \lvert \ n$

Proof of Lemma 1
We have $k \le n$ since $k$ is least with the property $a^k \equiv 1 \ (\text{mod} \ m)$ . By the division algorithm, we have $n=q \cdot k+r$ where $q$ is some integer and $0 \le r <k$ . We have the following:

$1 \equiv a^{n} \equiv a^{q \cdot k+r} \equiv (a^k)^q \cdot a^r \equiv a^r \ (\text{mod} \ m)$

With $a^r \equiv 1 \ (\text{mod} \ m)$ and $r < k$ , it follows that $r=0$ and $n=q \cdot k$ . Thus $k$ is a divisor of $n$ . $\blacksquare$

Though Check # 2 is definitely an improvement over Check # 1, the following further narrows the list of exponents to check.

Check # 3

$q$

$\phi(m)$

$\displaystyle j=\frac{\phi(m)}{q}$

$q$

Check $a^j \ (\text{mod} \ m)$ for all $j$ calculated above.

If each such congruence $\not \equiv 1$ , then the number $a$ is a primitive root modulo $m$ .

____________________________________________________________________________________________

Check # 3 further eliminates the exponents to try when we check $a^j \ (\text{mod} \ m)$ . Instead of checking over all the divisors of $\phi(m)$ , we only need to try the divisors of the form $\displaystyle \frac{\phi(m)}{q}$ where $q$ is a prime divisor of $\phi(m)$ . The following lemma shows why this works.

Lemma 2

$a$

$m$

$\displaystyle a^{\frac{\phi(m)}{q}} \not \equiv 1 \ (\text{mod} \ m)$

$q$

$\phi(m)$

Proof of Lemma 2
The direction $\Longrightarrow$ is clear.

To show $\Longleftarrow$ , suppose $a$ is not a primitive root modulo $m$ . Then
$\displaystyle a^{t} \equiv 1 \ (\text{mod} \ m)$ for some $t$ that is a divisor of $\phi(m)$ . We have $\phi(m)=t \cdot y$ for some integer $y$ . Let $q$ be a prime factor of $y$ . Then $\phi(m)=t \cdot q \cdot b$ for some integer $b$ . Consider the following derivation.

$\displaystyle 1 \equiv (a^t)^b =(a^{\frac{\phi(m)}{qb}})^b \equiv a^{\frac{\phi(m)}{q}} \ (\text{mod} \ m)$

Thus if $\displaystyle a^{\frac{\phi(m)}{q}} \not \equiv 1 \ (\text{mod} \ m)$ for all prime divisors $q$ of $\phi(m)$ , then $a$ must be a primitive root modulo $m$ . $\blacksquare$

___________________________________________________________________________________________________________________

Examples

We now work some examples using Check # 3. The modular arithmetic is done using an online calculator. It can also be done using the fast powering algorithm (discussed in the post Congruence Arithmetic and Fast Powering Algorithm).

Example 1
Consider $m=37$ . Find all primitive roots modulo $m=37$ .

First $\phi(37)=36$ . The divisors of $36$ are:

$1,2,3,4,6,9,12,18,36$

To use Check # 2, in order to find out if $a$ is a primitive root, we would need to calculate $a^j$ nine times, one for each of the above divisors of $\phi(37)=36$ .

To use Check # 3, only two of these nine divisors are needed. There are two prime divisors of $36$ , namely $2$ and $3$ . We use $\displaystyle \frac{36}{2}=18$ and $\displaystyle \frac{36}{3}=12$ . So we check $a^{12}$ and $a^{18}$ modulo $37$ . The calculation is presented in the following tables.

$\displaystyle \begin{bmatrix} a&\text{ }&a^{12}&\text{ }&a^{18} \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1&\text{ }&1 \\ 2&\text{ }&26&\text{ }&36 \\ 3&\text{ }&10&\text{ }&1 \\ 4&\text{ }&10&\text{ }&1 \\ 5&\text{ }&10&\text{ }&36 \\ 6&\text{ }&1&\text{ }&36 \\ 7&\text{ }&10&\text{ }&1 \\ 8&\text{ }&1&\text{ }&36 \\ 9&\text{ }&26&\text{ }&1 \\ 10&\text{ }&1&\text{ }&1 \end{bmatrix} \ \ \ \ \ \displaystyle \begin{bmatrix} a&\text{ }&a^{12}&\text{ }&a^{18} \\\text{ }&\text{ }&\text{ } \\ 11&\text{ }&1&\text{ }&1 \\ 12&\text{ }&26&\text{ }&1 \\ 13&\text{ }&10&\text{ }&36 \\ 14&\text{ }&1&\text{ }&36 \\ 15&\text{ }&26&\text{ }&36 \\ 16&\text{ }&26&\text{ }&1 \\ 17&\text{ }&26&\text{ }&36 \\ 18&\text{ }&10&\text{ }&36 \\ 19&\text{ }&10&\text{ }&36 \\ 20&\text{ }&26&\text{ }&36 \end{bmatrix}$

$\displaystyle \begin{bmatrix} a&\text{ }&a^{12}&\text{ }&a^{18} \\\text{ }&\text{ }&\text{ } \\ 21&\text{ }&26&\text{ }&1 \\ 22&\text{ }&26&\text{ }&36 \\ 23&\text{ }&1&\text{ }&36 \\ 24&\text{ }&10&\text{ }&36 \\ 25&\text{ }&26&\text{ }&1 \\ 26&\text{ }&1&\text{ }&1 \\ 27&\text{ }&1&\text{ }&1 \\ 28&\text{ }&26&\text{ }&1 \\ 29&\text{ }&1&\text{ }&36 \\ 30&\text{ }&10&\text{ }&1 \end{bmatrix} \ \ \ \ \ \displaystyle \begin{bmatrix} a&\text{ }&a^{12}&\text{ }&a^{18} \\\text{ }&\text{ }&\text{ } \\ 31&\text{ }&1&\text{ }&36 \\ 32&\text{ }&10&\text{ }&36 \\ 33&\text{ }&10&\text{ }&1 \\ 34&\text{ }&10&\text{ }&1 \\ 35&\text{ }&26&\text{ }&36 \\ 36&\text{ }&1&\text{ }&1 \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \end{bmatrix}$

The primitive roots are the rows with both congruences $\not \equiv 1$ . They are:

$2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35$

One comment about the above tables. The non-one values in the above table seem to follow a pattern. In the columns for the calculation for $a^{18}$ , the values are either $1$ or $36$ . The non-one value is $36$ . It turns out that it has order $2$ modulo $37$ . The non-one values in the columns for $a^{12}$ are $10$ and $26$ . It turns out that they have order $3$ modulo $37$ . See the exercise stated below.

Example 2
Consider $m=17$ . Find all primitive roots modulo $m=17$ .

Since $\phi(17)=16=2^4$ , the only prime divisor of $latex $\phi(17)$ is $2$ . We use $\displaystyle \frac{16}{2}=8$ . For any $a$ , we only need to calculate $a^8$ .

$\displaystyle \begin{bmatrix} a&\text{ }&a^{8}&\text{ }&a&\text{ }&a^{8} \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1&\text{ }&11&\text{ }&16 \\ 2&\text{ }&1&\text{ }&12&\text{ }&16 \\ 3&\text{ }&16&\text{ }&13&\text{ }&1 \\ 4&\text{ }&1&\text{ }&14&\text{ }&16 \\ 5&\text{ }&16&\text{ }&15&\text{ }&1 \\ 6&\text{ }&16&\text{ }&16&\text{ }&1 \\ 7&\text{ }&16&\text{ }&\text{ } \\ 8&\text{ }&1&\text{ }&\text{ } \\ 9&\text{ }&1&\text{ }&\text{ } \\ 10&\text{ }&16&\text{ }&\text{ } \end{bmatrix}$

The primitive roots modulo $17$ are:

$3, 5, 6, 7, 10, 11, 12, 14$

Note that the non-one value $16$ in the above table has order $2$ modulo $17$ . See the exercise below.

___________________________________________________________________________________________________________________

Special Case

Based on Example 2, the following is a special case for Check # 3.

Check # 3 (A Special Case)

Let $p$ be a prime such that $p-1=2^n$ for some positive integer $n$ .

Note that $2$ is the only prime divisor of $\phi(p)=p-1$ .

Check $a^j \ (\text{mod} \ p)$ where $\displaystyle j=\frac{p-1}{2}$ .

If $a^j \not \equiv 1$ , then the number $a$ is a primitive root modulo $p$ .

____________________________________________________________________________________________

___________________________________________________________________________________________________________________

Exercise

This is the exercise mentioned at the end of Example 1.

Let $p$ be a prime number. Let $q$ be a prime divisor of $p-1$ . Let $a$ be an integer with $1 \le a \le p-1$ . Show that the number $\displaystyle a^{\frac{p-1}{q}}$ is either $\equiv 1$ or has order $q$ modulo $p$ .

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

Quadratic Residues

Posted on October 20, 2013 by Dan Ma

In a previous post called Solving Quadratic Congruences, we discuss the solvability of the quadratic congruence

$x^2 \equiv a \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

where $p$ is an odd prime and $a$ is relatively prime to $p$ . In this post, we continue to discuss the solvability of equation (1) from the view point of quadratic residues. In this subsequent post, we discuss specific algorithms that produce solutions to such equations.

____________________________________________________________________________

Definition

Let $p$ be an odd prime. Let $a$ be an integer that is not divisible by $p$ (equivalently relatively prime to $p$ ). Whenever equation (1) has solutions, we say that the number $a$ is a quadratic residue modulo $p$ . Otherwise, we say that the number $a$ is a quadratic nonresidue modulo $p$ . When the context is clear, the word quadratic is sometimes omitted.

The term quadratic residues is more convenient to use. Instead of saying the equation $x^2 \equiv a \ (\text{mod} \ p)$ has a solution, we say the number $a$ is a quadratic residue for the modulus in question. The significance of the notion of quadratic residue extends beyond the convenience of having a shorter name. It and and the Legendre symbol lead to a large body of beautiful and deep results in number theory, the quadratic reciprocity theorem being one of them.

One property of the quadratic congruence equation (1) is that when equation (1) has solutions, it has exactly two solutions among the set $\left\{1,2,3,\cdots,p-1 \right\}$ (see Lemma 1 in the post Solving Quadratic Congruences). Thus among the integers in the set $\left\{1,2,3,\cdots,p-1 \right\}$ , $\displaystyle \frac{p-1}{2}$ of them are quadratic residues and the other half are quadratic nonresidues modulo $p$ .

For example, consider the modulus $p=11$ . Among the numbers in the set $\left\{1,2,3,\cdots,10 \right\}$ , the numbers $1,3,4,5,9$ are quadratic residues and the numbers $2,6,7,8,10$ are quadratic nonresidues. See the following two tables.

$\displaystyle \begin{bmatrix} x&\text{ }&x^2 \equiv \ (\text{mod} \ 11) \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1 \\ 2&\text{ }&4 \\ 3&\text{ }&9 \\ 4&\text{ }&5 \\ 5&\text{ }&3 \\ 6&\text{ }&3 \\ 7&\text{ }&5 \\ 8&\text{ }&9 \\ 9&\text{ }&4 \\ 10&\text{ }&1 \end{bmatrix}$

The above table shows the least residues of $x^2$ for $x \in \left\{1,2,3,\cdots,10 \right\}$ . It shows that there $x^2$ can only be $1,3,4,5,9$ . Thus these are the quadratic residues. The table below shows the status of residue/nonresidue among the integers in $\left\{1,2,3,\cdots,10 \right\}$ .

$\displaystyle \begin{bmatrix} x&\text{ }&\text{residue or nonresidue mod } 11 \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&\text{residue} \\ 2&\text{ }&\text{nonresidue} \\ 3&\text{ }&\text{residue} \\ 4&\text{ }&\text{residue} \\ 5&\text{ }&\text{residue} \\ 6&\text{ }&\text{nonresidue} \\ 7&\text{ }&\text{nonresidue} \\ 8&\text{ }&\text{nonresidue} \\ 9&\text{ }&\text{residue} \\ 10&\text{ }&\text{nonresidue} \end{bmatrix}$

____________________________________________________________________________

Legendre Symbol

The notion of quadratic residues is often expressed using the Legendre symbol, which is defined as follows:

$\displaystyle \biggl(\frac{a}{p}\biggr)=\left\{\begin{matrix}1&\ \text{if } a \text{ is a quadratic residue modulo }p \\{-1}&\ \text{if } a \text{ is a quadratic nonresidue modulo }p \end{matrix}\right.$

The bottom number $p$ in the above notation is an odd prime. The top number $a$ is an integer that is not divisible by $p$ (equivalently relatively prime to $p$ ). Despite the appearance, the Legendre symbol is not the fraction of $a$ over $p$ . It follows from the definition that the symbol has the value of one if the equation $x^2 \equiv a \ (\text{mod} \ p)$ has solutions. It has the value of negative one if the equation $x^2 \equiv a \ (\text{mod} \ p)$ has no solutions.

For example, $\displaystyle \biggl(\frac{a}{11}\biggr)=1$ for $a=1,3,4,5,9$ and and $\displaystyle \biggl(\frac{a}{11}\biggr)=-1$ for $a=2,6,7,8,10$ . To evaluate $\displaystyle \biggl(\frac{11}{3}\biggr)$ , consider the equation $x^2 \equiv 11 \ (\text{mod} \ 3)$ , which is equivalent to the equation $x^2 \equiv 2 \ (\text{mod} \ 3)$ . This last equation has no solutions. Thus $\displaystyle \biggl(\frac{11}{3}\biggr)=-1$ .

The quadratic reciprocity law discussed below allows us to calculate $\displaystyle \biggl(\frac{11}{3}\biggr)$ by flipping $\displaystyle \biggl(\frac{3}{11}\biggr)$ . In certain cases, flipping the symbol keeps the same sign. In other cases, flipping introduces a negative sign (as in this example).

____________________________________________________________________________

Basic Properties

Euler’s Criterion is a formula that determines whether an integer is a quadratic residue modulo an odd prime. We have the following theorem. A proof of Euler’s Criterion is found in this post.

Theorem 1 (Euler’s Criterion)

$p$

$a$

$p$

$\displaystyle \biggl(\frac{a}{p}\biggr) \equiv \displaystyle a^{\frac{p-1}{2}} \ (\text{mod} \ p)$

The following lemma shows a connection between the notion of quadratic residue and the notion of primitive roots.

Lemma 2

$p$

$g$

$p$

$a$

$p$

The number $a$ is a quadratic residue modulo $p$ if and only if $a \equiv g^{2k} \ (\text{mod} \ p)$ for some integer $k$ .
Or equivalently, the number $a$ is a quadratic nonresidue modulo $p$ if and only if $a \equiv g^{2k+1} \ (\text{mod} \ p)$ for some integer $k$ .

Proof of Lemma 2
A primitive root $g$ exists since the modulus $p$ is prime (see Theorem 1 in the post Primitive roots of prime moduli). Furthermore, any integer that is not divisible by $p$ is congruent to a unique element of the set $\left\{g^1,g^2,g^3,\cdots,g^{p-1} \right\}$ . Thus for the number $a$ in question, either $a \equiv g^{2k}$ or $a \equiv g^{2k+1}$ . We can conclude that the first bullet point in the lemma is equivalent to the second bullet point.

We prove the first bullet point. First we show the direction $\Longleftarrow$ . Suppose $a \equiv g^{2k} \ (\text{mod} \ p)$ . Clearly the equation $x^2 \equiv a \ (\text{mod} \ p)$ has a solution since $(g^k)^2 \equiv a \equiv g^{2k} \ (\text{mod} \ p)$ .

Now we show the direction $\Longrightarrow$ . We prove the contrapositive. Suppose that $a \equiv g^{2k+1} \ (\text{mod} \ p)$ . We wish to show that $a$ is a quadratic nonresidue modulo $p$ . Suppose not. Then $t^2 \equiv a \ (\text{mod} \ p)$ for some $t$ . It follows that $p \not \lvert \ t$ . Note that if $p \ \lvert \ t$ , $p \ \lvert \ a$ , which is not true. By Fermat’s little theorem, we have $t^{p-1} \equiv 1 \ (\text{mod} \ p)$ . We have the following derivation.

$\displaystyle (g^{2k+1})^{\frac{p-1}{2}} \equiv (t^{2})^{\frac{p-1}{2}} \equiv t^{p-1} \equiv 1 \ (\text{mod} \ p)$

On the other hand, we can express $\displaystyle (g^{2k+1})^{\frac{p-1}{2}}$ as follows:

$\displaystyle (g^{2k+1})^{\frac{p-1}{2}} \equiv g^{k(p-1)} \cdot g^{\frac{p-1}{2}} \equiv (g^{p-1})^k \cdot g^{\frac{p-1}{2}} \equiv 1^k \cdot g^{\frac{p-1}{2}} \equiv g^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$

Note that the last congruence $g^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$ contradicts the fact that $g$ is a primitive root modulo $p$ since $p-1$ is the least exponent that such that $g^{p-1} \equiv 1 \ (\text{mod} \ p)$ . So $a$ cannot be a quadratic residue modulo $p$ . We have proved that if $a \equiv g^{2k+1} \ (\text{mod} \ p)$ , then $a$ is a quadratic nonresidue modulo $p$ . Equivalently, if $a$ is a quadratic residue modulo $p$ , then $a \equiv g^{2k} \ (\text{mod} \ p)$ . Thus the lemma is established. $\blacksquare$

We can also obtain an alternative proof by using Theorem 1 (Euler’s Criterion). We show $\Longleftarrow$ of both bullet points.

First, $\Longleftarrow$ of the first bullet point. Suppose $a \equiv g^{2k} \ (\text{mod} \ p)$ . Then $\displaystyle (g^{2k})^{\frac{p-1}{2}} \equiv (g^{p-1})^k \equiv 1^k \equiv 1 \ (\text{mod} \ p)$ . Thus $\displaystyle \biggl(\frac{a}{p}\biggr)=1$ and $a$ is a quadratic residue modulo $p$ by Euler’s Criterion.

Now $\Longleftarrow$ of the second bullet point. Suppose $a \equiv g^{2k+1} \ (\text{mod} \ p)$ . Then $\displaystyle (g^{2k+1})^{\frac{p-1}{2}} \equiv (g^{p-1})^k \cdot g^{\frac{p-1}{2}} \equiv g^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$ . The last congruence $g^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$ because $g$ is a primitive root. Thus $\displaystyle \biggl(\frac{a}{p}\biggr)=-1$ and $a$ is a quadratic nonresidue modulo $p$ by Euler’s Criterion. $\blacksquare$

Remark
Each number in the set $\left\{1,2,3,\cdots,p-1 \right\}$ is congruent to a power of the primitive root $g$ in question. Lemma 2 indicates that the even powers are the quadratic residues while the odd powers are the quadratic nonresidues. The following lemma is a corollary of Lemma 2.

Lemma 3

$p$

If $a$ and $b$ are quadratic residues modulo $p$ , then $ab$ is a quadratic residue modulo $p$ .
If $a$ is a quadratic residue and $b$ is a quadratic nonresidue modulo $p$ , then $ab$ is a quadratic nonresidue modulo $p$ .
If $a$ and $b$ are quadratic nonresidues modulo $p$ , then $ab$ is a quadratic residue modulo $p$ .

Proof of Lemma 3
Let $g$ be a primitive root modulo $p$ . Then we express each residue or nonresidue as a power of $g$ and then multiply the two powers of $g$ by adding the exponents as in the following.

$\displaystyle g^{2j} \cdot g^{2k}=g^{2(j+k)}$

$\displaystyle g^{2j} \cdot g^{2k+1}=g^{2(j+k)+1}$

$\displaystyle g^{2j+1} \cdot g^{2k+1}=g^{2(j+k+1)}$

The first product above has an even exponent. Thus the product of two quadratic residues is a quadratic residue (the first bullet point). The second product above has an odd exponent. Thus the product of a quadratic residue and a quadratic nonresidue is a nonresidue (second bullet point). The third product above has an even exponent. Thus the product of two nonresidues is a residue. $\blacksquare$

One part of the following theorem is a corollary of Lemma 3.

Theorem 4

$p$

If $p \not \lvert \ a$ and $a \equiv b \ (\text{mod} \ p)$ , then $\displaystyle \biggl(\frac{a}{p}\biggr)=\biggl(\frac{b}{p}\biggr)$ .
If $p \not \lvert \ a$ , then $\displaystyle \biggl(\frac{a^2}{p}\biggr)=1$ .
if $p \not \lvert \ a$ and $p \not \lvert \ b$ , then $\displaystyle \biggl(\frac{a}{p}\biggr) \cdot \biggl(\frac{b}{p}\biggr)=\biggl(\frac{ab}{p}\biggr)$ .

Proof of Theorem 4
The first and second bullets points are straightforward. We prove the third bullet point, which follows from Lemma 3. Given $a$ and $b$ , they would fall into one of the three cases of Lemma 3. Translating each case of Lemma 3 will give the correct statement in Legendre symbol. $\blacksquare$

____________________________________________________________________________

Quadratic Reciprocity

Quadratic reciprocity is a property that indicates how $\displaystyle \biggl(\frac{p}{q}\biggr)$ and $\displaystyle \biggl(\frac{q}{p}\biggr)$ are related when both $p$ and $q$ are odd prime. Even thought the statement of the theorem is easy to state and understand, it is an unexpected and profound result. Our goal here is quite simple – state the theorem and demonstrate how it can be used to simplify calculations. We have the following theorems.

Theorem 5 (Quadratic Reciprocity)

$p$

$q$

$\displaystyle \biggl(\frac{q}{p}\biggr)=\left\{\begin{matrix} \displaystyle \biggl(\frac{p}{q}\biggr) &\ \text{if } p \equiv 1 \ (\text{mod} \ 4) \text{ or } q \equiv 1 \ (\text{mod} \ 4) \\{\displaystyle -\biggl(\frac{p}{q}\biggr)}&\ \text{if } p \equiv q \equiv 3 \ (\text{mod} \ 4) \end{matrix}\right.$

Theorem 6

$p$

$q$

$\displaystyle \biggl(\frac{2}{p}\biggr)=\left\{\begin{matrix} 1 &\ \text{if } p \equiv 1 \ (\text{mod} \ 8) \text{ or } p \equiv 7 \ (\text{mod} \ 8) \\{-1}&\ \text{if } p \equiv 3 \ (\text{mod} \ 8) \text{ or } p \equiv 5 \ (\text{mod} \ 8) \end{matrix}\right.$

Theorem 7

$p$

$q$

$\displaystyle \biggl(\frac{-1}{p}\biggr)=\left\{\begin{matrix} 1 &\ \text{if } p \equiv 1 \ (\text{mod} \ 4) \\{-1}&\ \text{if } p \equiv 3 \ (\text{mod} \ 4) \end{matrix}\right.$

Theorems 4, 5, 6 and 7 are tools for evaluating Legendre symbols. We demonstrate with examples.

____________________________________________________________________________

Examples

Example 1
Is $1776$ a quadratic residue modulo the prime $1777$ ?

We evaluate the symbol $\displaystyle \biggl(\frac{1776}{1777}\biggr)=\biggl(\frac{-1}{1777}\biggr)$ . Note that $1777 \equiv 1 \ (\text{mod} \ 4)$ . By Theorem 7, $\displaystyle \biggl(\frac{-1}{1777}\biggr)=1$ . It follows that $1776$ is a quadratic residue modulo the prime $1777$ . Furthermore, $x^2 \equiv 1776 \ (\text{mod} \ 1777)$ has solutions.

Example 2
Solve $x^2 \equiv 899 \ (\text{mod} \ 50261)$ .

Note that $50261$ is a prime while $899$ is not since $899=29 \cdot 31$ . After applying Theorem 4, we have:

$\displaystyle \biggl(\frac{899}{50261}\biggr)=\displaystyle \biggl(\frac{29}{50261}\biggr) \displaystyle \biggl(\frac{31}{50261}\biggr)$ .

Now we can start using quadratic reciprocity.

$\displaystyle \begin{aligned} \displaystyle \biggl(\frac{899}{50261}\biggr)&=\displaystyle \biggl(\frac{29}{50261}\biggr) \biggl(\frac{31}{50261}\biggr) \\&=\displaystyle \biggl(\frac{50261}{29}\biggr) \biggl(\frac{50261}{31}\biggr) \\&=\displaystyle \biggl(\frac{4}{29}\biggr) \biggl(\frac{10}{31}\biggr) \\&=\displaystyle \biggl(\frac{2}{29}\biggr)^2 \biggl(\frac{2}{31}\biggr) \biggl(\frac{5}{31}\biggr) \\&=(-1)^2 \cdot 1 \cdot 1 \\&=1 \end{aligned}$

The above derivation is the result of applying Theorems 4, 5 and 7. Of particular importance is the repeated applications of Theorem 5 (Quadratic Reciprocity) so that the numbers in the Legendre symbols are much smaller than the ones we start with.

As useful as it is, the theorem for quadratic reciprocity does not show us how to solve the equation $x^2 \equiv 899 \ (\text{mod} \ 50261)$ . See Example 2 in the post Solving Quadratic Congruences to see how it can be solved.

____________________________________________________________________________

$\copyright \ 2013 - 2015 \text{ by Dan Ma}$
Revised December 9, 2015

Solving Quadratic Congruences

Posted on October 15, 2013 by Dan Ma

This post is an introductory discussion on the congruence equations of the form $x^2 \equiv a \ (\text{mod} \ p)$ where the modulus $p$ is an odd prime and the number $a$ is relatively prime to $p$ . A discussion on the related notion of quadratic residues is found here. Specific algorithms for solving quadratic congruence eqautions with odd prime moduli are discussed in this subsequent post.

____________________________________________________________________________

Simple Example

We start off with a simple example. Calculate $x^2$ modulo $m=11$ for $x=0,1,2,\cdots,10$ .

$0^2 \equiv 0 \ (\text{mod} \ 11)$

$1^2 \equiv 1 \ (\text{mod} \ 11)$

$2^2 \equiv 4 \ (\text{mod} \ 11)$

$3^2 \equiv 9 \ (\text{mod} \ 11)$

$4^2 \equiv 5 \ (\text{mod} \ 11)$

$5^2 \equiv 3 \ (\text{mod} \ 11)$

$6^2 \equiv 3 \ (\text{mod} \ 11)$

$7^2 \equiv 5 \ (\text{mod} \ 11)$

$8^2 \equiv 9 \ (\text{mod} \ 11)$

$9^2 \equiv 4 \ (\text{mod} \ 11)$

$10^2 \equiv 1 \ (\text{mod} \ 11)$

The above calculation shows that the values of $x^2$ modulo $m=11$ can only be $1,3,4,5,9$ . So equations such as $x^2 \equiv a \ (\text{mod} \ 11)$ for $a=1,3,4,5,9$ have solutions. For example, the solutions for the equation $x^2 \equiv 5 \ (\text{mod} \ 11)$ are $x=4$ and $x=7$ .

On the other hand, the equations $x^2 \equiv b \ (\text{mod} \ 11)$ for $b=2,6,7,8,10$ have no solutions.

Also note that whenever $a \ne 0$ and the equation $x^2 \equiv a \ (\text{mod} \ 11)$ has a solution, the solutions come in pairs.

____________________________________________________________________________

Quadratic Congruences

Let $m$ be an odd prime number. Let $a$ be an integer that is not divisible by $p$ (equivalently relatively prime to $p$ ). The object of interest here is the quadratic congruence equation $x^2 \equiv a \ (\text{mod} \ p)$ . It turns out that each such equation has exactly two solutions whenever the number $a$ and the modulus $p$ are relatively prime (as demonstrated in the above simple example). The following lemma and corollary confirm what we see in the above example.

Lemma 1

$p$

$a$

$p$

$x^2 \equiv a \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

has no solutions or exactly two solutions.

Proof of Lemma 1
If equation (1) has no solutions, then we are done. Suppose it has at least one solution, say $x=r$ . We have $r^2 \equiv a \ (\text{mod} \ p)$ . It follows that $x=-r \equiv p-r \ (\text{mod} \ p)$ is a solution of equation (1) too.

We claim $x=r$ and $x=p-r$ are distinct modulo $p$ . To see this, suppose $p-r \equiv r \ (\text{mod} \ p)$ . Then $p \ \lvert \ (p-2r)$ . Because $p$ is an odd prime, $p \not \lvert \ 2$ . So $p \ \lvert \ r$ . This implies that $p \ \lvert \ r^2$ . Because $p \ \lvert \ (r^2-a)$ , $p \ \lvert \ a$ , contradicting the assumption that $p \not \lvert \ a$ . Thus $p-r \not \equiv r \ (\text{mod} \ p)$ , demonstrating that equation (1) has at least two solutions.

It remains to be shown that any solution of equation (1) must be congruent to one of $x=r$ and $x=p-r$ . Suppose $t^2 \equiv a \ (\text{mod} \ p)$ . Then $t^2 \equiv r^2 \ (\text{mod} \ p)$ . It follows that $p \ \lvert \ (t-r)(t+r)$ . Thus $p$ must divide one of the two factors (Euclid’s lemma). The case $p \ \lvert \ (t-r)$ implies $t \equiv r \ (\text{mod} \ p)$ . The case $p \ \lvert \ (t+r)$ implies $t \equiv -r \ (\text{mod} \ p)$ . $\blacksquare$

Corollary 2

$p$

$x^2 \equiv a \ (\text{mod} \ p)$

$\displaystyle \frac{p-1}{2}$

$a \in \left\{1,2,\cdots,p-1 \right\}$

$\displaystyle \frac{p-1}{2}$

$a \in \left\{1,2,\cdots,p-1 \right\}$

Remark
For the even prime $p=2$ , the equation $x^2 \equiv a \ (\text{mod} \ 2)$ is not an interesting one. For $x^2 \equiv 0 \ (\text{mod} \ 2)$ , $x=0$ is the only solution. For $x^2 \equiv 1 \ (\text{mod} \ 2)$ , $x=1$ is the only solution.

For composite moduli, the quadratic equation $x^2 \equiv a \ (\text{mod} \ m)$ can have more than two solutions. For example, $x^2 \equiv 1 \ (\text{mod} \ 8)$ has four solutions $x=1,3,5,7$ .

For these reasons, we only work with odd prime moduli for quadratic congruences.

____________________________________________________________________________

General Case

What about the general case of the quadratic congruence equation of the following form?

$\alpha y^2+\beta y+\gamma \equiv 0 \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

Of course, we only consider the equations where $\alpha \not \equiv 0 \ (\text{mod} \ p)$ and $p$ is an odd prime. It turns out that equation (2) can be replaced by an equivalent congruence equation of the same form as equation (1) above. So the general case of equation (2) presents no new problem. We just convert equation (2) to its equivalence and solve it accordingly. We now discuss how this is done.

The coefficient $\alpha$ , the coefficient of the $y^2$ term, has a multiplicative inverse modulo $p$ . So multiplying equation (2) by $\alpha^{-1}$ gives the following equation.

$y^2+\alpha^{-1} \beta y+\alpha^{-1} \gamma \equiv 0 \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$

So we can now focus on solving equation (3), which has the same solutions as equation (2). Consider the coefficient of the $y$ term. If the coefficient $\alpha^{-1} \beta$ is even, we can complete the square and obtain an equivalent equation of the same form as equation (1). If the coefficient $\alpha^{-1} \beta$ is odd, then we can add $p$ to it and obtain an even coefficient. We can then proceed to complete the square as in the even case. We demonstrate with two examples.

Consider the equation $3 y^2+4y+1 \equiv 0 \ (\text{mod} \ 11)$ . Since $4 \cdot 3 \equiv 1 \ (\text{mod} \ 11)$ . The multiplicative inverse of $4$ is $3$ . So we multiply $4$ across and obtain $y^2+16y+4 \equiv 0 \ (\text{mod} \ 11)$ . The coefficient of the $y$ term is even. We complete the square as follows.

$y^2+16y+4 \equiv 0 \ (\text{mod} \ 11)$

$y^2+16y+64 \equiv 64-4 \ (\text{mod} \ 11)$

$(y+8)^2 \equiv 60 \ (\text{mod} \ 11)$

$(y+8)^2 \equiv 5 \ (\text{mod} \ 11)$

The last equation in the above derivation is of the form $x^2 \equiv 5 \ (\text{mod} \ 11)$ where the solutions are $x=4$ and $x=7$ . Thus we have $y+8 \equiv 4 \ (\text{mod} \ 11)$ and $y+8 \equiv 7 \ (\text{mod} \ 11)$ . These two congruences give $y \equiv 7 \ (\text{mod} \ 11)$ and $y \equiv 10 \ (\text{mod} \ 11)$ .

For the odd case, consider the equation $5 y^2+y+8 \equiv 0 \ (\text{mod} \ 11)$ . The multiplicative inverse of $5$ is $9$ as $5 \cdot 9 \equiv 1 \ (\text{mod} \ 11)$ . After multiplying by the inverse, we obtain $y^2+9y+72 \equiv 0 \ (\text{mod} \ 11)$ . We further reduce $72$ modulo $11$ to get $y^2+9y+6 \equiv 0 \ (\text{mod} \ 11)$ . Note that the coefficient of the $y$ term is odd. So we add modulus to that coefficient to obtain the equation $y^2+20y+6 \equiv 0 \ (\text{mod} \ 11)$ . We then proceed to complete the square as follows.

$y^2+20y+100 \equiv 100-6 \ (\text{mod} \ 11)$

$(y+10)^2 \equiv 94 \ (\text{mod} \ 11)$

$(y+10)^2 \equiv 6 \ (\text{mod} \ 11)$

The last equation in the above derivation is of the form $x^2 \equiv 6 \ (\text{mod} \ 11)$ , which has no solutions (based on the simple example above). Thus the original equation $5 y^2+y+8 \equiv 0 \ (\text{mod} \ 11)$ has no solutions.

____________________________________________________________________________

Examples

To solve the quadratic congruence $x^2 \equiv a \ (\text{mod} \ p)$ , one way is to compute the entire table of values for $x^2$ modulo $p$ . For very small prime such as the simple example above, this approach is workable. For large primes, this requires a lot of computational resources.

To further illustrate the quadratic congruences, we work three examples with help from Euler’s Criterion and from using Excel to do some of the calculations.

According to Euler’s Criterion, the equation $x^2 \equiv a \ (\text{mod} \ p)$ has solutions if and only if $\displaystyle a^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$ . Equivalently, the equation $x^2 \equiv a \ (\text{mod} \ p)$ has no solutions if and only if $\displaystyle a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$ . So the solvability of the quadratic congruence equation can be translated as a modular exponentiation calculation.

The computation for $\displaystyle a^{\frac{p-1}{2}} \ (\text{mod} \ p)$ can be done directly using an online modular arithmetic calculator or using the fast-powering algorithm (discussed in the post Congruence Arithmetic and Fast Powering Algorithm). For a discussion and a proof of Euler’s Criterion, see the post Euler’s Criterion.

When Euler’s Criterion indicates there are solutions, how do we find the solutions? We demonstrate using the following examples.

Example 1
Solve $x^2 \equiv 5 \ (\text{mod} \ 61)$ .

According to Euler’s Criterion, the equation $x^2 \equiv 5 \ (\text{mod} \ 61)$ has solutions since $5^{30} \equiv 1 \ (\text{mod} \ 61)$ . To find the solutions, we keep adding the modulus to $a=5$ until we get a perfect square.

$\displaystyle x^2 \equiv 5 \equiv 5+61 \equiv 5+2(61) \equiv \cdots \equiv 5+20(61)=1225=35^2 \ (\text{mod} \ 61)$

So we have $x^2 \equiv 35^2 \ (\text{mod} \ 61)$ , which gives $x=35$ and $x=-35$ . The solutions are $x \equiv -35 \equiv 26 \ (\text{mod} \ 61)$ and $x \equiv 35 \ (\text{mod} \ 61)$ .

Example 2
Solve $x^2 \equiv 899 \ (\text{mod} \ 50261)$ .

Since $899^{25130} \equiv 1 \ (\text{mod} \ 50261)$ , the equation has solutions. We then add the modulus repeatedly to $899$ until we get a perfect square (with the aid of an Excel spreadsheet).

$\displaystyle x^2 \equiv 899 \equiv 899+50261 \equiv 899+2(50261) \equiv \cdots \equiv 899+4297(50261)=215972416=14696^2 \ (\text{mod} \ 50261)$

So we have $x^2 \equiv 14696^2 \ (\text{mod} \ 50261)$ , which gives $x=14696$ and $x=-14696$ . The solutions are $x \equiv 14696 \ (\text{mod} \ 50261)$ and $x \equiv -14696 \equiv 35565 \ (\text{mod} \ 50261)$ .

Example 3
Solve $x^2 \equiv 13961 \ (\text{mod} \ 50261)$ .

Since $13961^{25130} \equiv -1 \ (\text{mod} \ 50261)$ , the equation has no solutions according to Euler’s Criterion.

____________________________________________________________________________

$\copyright \ 2013 - 2015 \text{ by Dan Ma}$
Revised December 9, 2015

Euler’s Criterion

Posted on October 12, 2013 by Dan Ma

In this post we discuss a beautiful connection between Fermat’s little theorem and the solvability of a quadratic congruence equation. The discussion leads to a theorem that is commonly called Euler’s Criterion.

___________________________________________________________________________________________________________________

The Setting

Let $p$ be an odd prime number. Let $a$ be a positive integer that is relative prime to $p$ . According to Fermat’s little theorem, we have $\displaystyle a^{p-1} \equiv 1 \ (\text{mod} \ p)$ , which can be written as $\displaystyle (a^{\frac{p-1}{2}})^2 \equiv 1 \ (\text{mod} \ p)$ . So the number $\displaystyle a^{\frac{p-1}{2}}$ represent solutions to the equation $y^2 \equiv 1 \ (\text{mod} \ p)$ . It can be shown that the equation $y^2 \equiv 1 \ (\text{mod} \ p)$ has exactly two solutions. The number $\displaystyle a^{\frac{p-1}{2}}$ has two possibilities. They are:

$\displaystyle a^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p) \ \ \ \ \text{or} \ \ \ \ a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$

The result we wish to highlight is that each of the above two cases corresponds to either the solvability or non-solvability of the following quadratic congruence equation.

$x^2 \equiv a \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

___________________________________________________________________________________________________________________

Euler’s Criterion

The result indicated at the end of the preceding section is known as Euler’s Criterion. We have the following theorem.

Theorem 1 (Euler’s Criterion)

Let $p$ be an odd prime number. Let $a$ be a positive integer that is relative prime to $p$ .

The equation $x^2 \equiv a \ (\text{mod} \ p)$ has solutions if and only if $\displaystyle a^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$ .

$\text{ }$

The equation $x^2 \equiv a \ (\text{mod} \ p)$ has no solutions if and only if $\displaystyle a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$ .

Examples
Take $x^2 \equiv 899 \ (\text{mod} \ 50261)$ as an example. To determine whether this equation is solvable, we can check each integer in the interval $1 \le x <50261$ . Euler's Criterion reduces the solvability question to a modular exponential problem. It can be shown that $\displaystyle 899^{\frac{50261-1}{2}}=899^{25130} \equiv 1 \ (\text{mod} \ p)$ . Thus $x^2 \equiv 899 \ (\text{mod} \ 50261)$ has solutions.

On the other hand, the equation $x^2 \equiv 13961 \ (\text{mod} \ 50261)$ has no solutions since $\displaystyle 13961^{25130} \equiv -1 \ (\text{mod} \ p)$ .

Proof of Theorem 1
We prove the first bullet point. The two bullet points in Theorem 1 are equivalent. We need only prove one of them.

$\Longrightarrow$
Suppose that $x^2 \equiv a \ (\text{mod} \ p)$ has solutions. Let $x=t$ be one solution. Then we have $t^2 \equiv a \ (\text{mod} \ p)$ . The following derivation establishes the direction of $\Longrightarrow$ .

$\displaystyle a^{\frac{p-1}{2}} \equiv (t^2)^{\frac{p-1}{2}} \equiv t^{p-1} \equiv 1 \ (\text{mod} \ p)$

Applying Fermat’s little theorem, which gives $t^{p-1} \equiv 1 \ (\text{mod} \ p)$ (giving the last congruence in the above derivation). To apply Fermat’s theorem, we need to show that $p \not \lvert \ t$ . Suppose that $p \ \lvert \ t$ . Then $p \ \lvert \ t^2$ and $t^2 \equiv 0 \ (\text{mod} \ p)$ . It follows that $a \equiv 0 \ (\text{mod} \ p)$ , contradicting the fact that $a$ is relatively prime to the modulus $p$ .

$\Longleftarrow$
Suppose that $x^2 \equiv a \ (\text{mod} \ p)$ has no solutions. we make the following claim.

$h \in \left\{1,2,\cdots,p-1 \right\}$

$k \in \left\{1,2,\cdots,p-1 \right\}$

$h \ne k$

$hk=a$

To prove the above claim, let $k=h^{-1}a$ . It is clear that $hk=a$ . It remains to be shown that $h \ne k$ . Suppose that $h=h^{-1}a$ . Then $h^2=a$ , implying that $x^2 \equiv a \ (\text{mod} \ p)$ has a solution. Thus $h \ne k$ .

It follows from the claim that the set $\left\{1,2,\cdots,p-1 \right\}$ consists of $\displaystyle \frac{p-1}{2}$ many pairs of numbers, each with product $a$ . So we have the following:

$\displaystyle 1 \cdot 2 \cdots p-1 \equiv a^{\frac{p-1}{2}} \ (\text{mod} \ p)$

According to Wilson’s theorem, $\displaystyle 1 \cdot 2 \cdots p-1 \equiv -1 \ (\text{mod} \ p)$ . Consequently, $\displaystyle a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$ .

We have shown that if the equation $x^2 \equiv a \ (\text{mod} \ p)$ has no solutions, then $\displaystyle a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$ . Equivalently if $\displaystyle a^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$ , then the equation $x^2 \equiv a \ (\text{mod} \ p)$ has solutions. $\blacksquare$

___________________________________________________________________________________________________________________

Quadratic Residue

The statement that the equation $x^2 \equiv a \ (\text{mod} \ p)$ has solutions is commonly described by the term quadratic residue. We say that the number $a$ is a quadratic reside modulo $p$ if the equation $x^2 \equiv a \ (\text{mod} \ p)$ has solutions. If the number $a$ is not a quadratic reside modulo $p$ , we say that it is a quadratic nonresidue modulo $p$ . Whenever there is no need to make a distinction between quadratic and higher power, we will just omit the word quadratic and refer to residues and nonresidues.

Euler’s Criterion can be restated using the term quadratic residues.

Theorem 1 (Euler’s Criterion)

Let $p$ be an odd prime number. Let $a$ be a positive integer that is relative prime to $p$ .

The number $a$ is a quadratic residue modulo $p$ if and only if $\displaystyle a^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$ .

$\text{ }$

The number $a$ is a quadratic nonresidue modulo $p$ if and only if $\displaystyle a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$ .

___________________________________________________________________________________________________________________

Legendre Symbol

For those who like to be economical in the statements of mathematical results, the Legendre symbol can be used. The Legendre symbol $\displaystyle \biggl(\frac{a}{p}\biggr)$ is defined as follows:

Euler’s Criterion can be restated as follows:

Theorem 1 (Euler’s Criterion)

Let $p$ be an odd prime number. Let $a$ be a positive integer that is relative prime to $p$ . Then the following property holds.

$\displaystyle \biggl(\frac{a}{p}\biggr) \equiv \displaystyle a^{\frac{p-1}{2}} \ (\text{mod} \ p)$

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

Two Proofs of Wilson’s Theorem

Posted on September 22, 2013 by Dan Ma

In this post, we give two proofs of Wilson’s theorem. The second proof uses the notion of primitive roots. The following is the statement of the theorem.

Theorem 1 (Wilson’s Theorem)

$p$

$(p-1)! \equiv -1 \ (\text{mod} \ p)$

An alternative way of stating Wilson’s theorem is that $p$ is a prime number if and only if $(p-1)! +1$ is divisible by $p$ .

___________________________________________________________________________________________________________________

One Proof

We use $\text{GCD}(a,b)$ to denote the greatest common divisor of the positive integers $a$ and $b$ . We use the following lemma.

Lemma 2

$m$

$x^2 \equiv 1 \ (\text{mod} \ m)$

$x=1,m-1$

Proof of Lemma 2

It is straightforward to see that $1^2 \equiv 1 \ (\text{mod} \ m)$ and $(m-1)^2 \equiv 1 \ (\text{mod} \ m)$ . It remains to show that $x=1,m-1$ are the only two solutions. To that end, we show that any solution of $x^2 \equiv 1 \ (\text{mod} \ m)$ must be one of these.

Let $t$ be a solution of the above congruence equation. This means that $t^2 \equiv 1 \ (\text{mod} \ m)$ and $0 \le t \le m-1$ . So $m \ \lvert \ (t^2-1)=(t+1)(t-1)$ . By Euclid’s lemma, either $m \ \lvert (t+1)$ or $m \ \lvert (t-1)$ . The first case gives $t \equiv -1 \ (\text{mod} \ m)$ and the second case gives $t \equiv 1 \ (\text{mod} \ m)$ . Since $0 \le t \le m-1$ , the first congruence means that $t=p-1$ and the second congruence means that $t=1$ . $\blacksquare$

Lemma 3

$a$

$0 \le a \le m-1$

The number $a$ and the modulus $m$ are relatively prime, i.e., $\text{GCD}(a,m)=1$ .
There exists a unique integer $b$ with $0 \le b \le m-1$ such that $ab \equiv 1 \ (\text{mod} \ m)$ . In other words, the number $a$ has a multiplicative inverse modulo $m$ .

Lemma 3 is proved in a previous post (see Theorem 1 in the post Euler’s phi function, part 1).

Proof of Theorem 1 (first proof)

$\Longleftarrow$
Suppose $p$ is a positive integer that is not prime. Then $p$ has a factor among the integers $2,3,\cdots,p-1$ . Thus $d=\text{GCD}((p-1)!,p)>1$ (i.e. $(p-1)!$ and $p$ are not relatively prime).

We claim that $(p-1)! \not \equiv -1 \ (\text{mod} \ p)$ . Suppose that $(p-1)! \equiv -1 \ (\text{mod} \ p)$ . Then we have $(p-1)! \cdot x+ p \cdot y=-1$ for some integers $x$ and $y$ . Since $d$ divides the left-hand side of the equation, $d \ \lvert \ -1$ . But $d=\text{GCD}((p-1)!,p)>1$ . So $(p-1)! \not \equiv -1 \ (\text{mod} \ p)$ .

We have proved that if $p$ is not prime, then $(p-1)! \not \equiv -1 \ (\text{mod} \ p)$ . Equivalently if $(p-1)! \equiv -1 \ (\text{mod} \ p)$ , then $p$ is prime.

$\Longrightarrow$
Suppose $p$ is prime. For each $a \in \left\{1,2,3,\cdots,p-1 \right\}$ , $a$ and $p$ are relatively prime. By Lemma 3, for each such $a$ , there exists a unique $b$ in $\left\{1,2,3,\cdots,p-1 \right\}$ such that $ab \equiv 1 \ (\text{mod} \ p)$ .

By Lemma 2, the congruence equation $x^2 \equiv 1 \ (\text{mod} \ p)$ has exactly two solutions, namely $x=1,p-1$ . Thus $a=1,p-1$ are the only numbers in $\left\{1,2,3,\cdots,p-1 \right\}$ for which $a$ and its inverse $b$ are the same. For each $a \in \left\{2,3,\cdots,p-2 \right\}$ , $a \ne b$ .

The number $p-3$ is an even integer. There are $p-3$ many numbers in the set $\left\{2,3,\cdots,p-2 \right\}$ . Based on the discussion in the preceding paragraph, the set $\left\{2,3,\cdots,p-2 \right\}$ consists of $\displaystyle \frac{p-3}{2}$ many pairs of numbers such that the product of each pair is $\equiv 1 \ (\text{mod} \ p)$ . Thus we have

$2 \cdot 3 \cdots (p-2) \equiv 1 \ (\text{mod} \ p)$

We can also write $(p-2)! \equiv 1 \ (\text{mod} \ p)$ . Multiply $p-1$ on both sides of the equation, we have $(p-1)! \equiv p-1 \ (\text{mod} \ p)$ . Since $p-1 \equiv -1 \ (\text{mod} \ p)$ , we have $(p-1)! \equiv -1 \ (\text{mod} \ p)$ . $\blacksquare$

___________________________________________________________________________________________________________________

Another Proof

To carry out the following proof, we use the theorem that every prime modulus has a primitive root. A primitive root for a given prime modulus $m$ is a positive integer $g$ with $1 \le g \le m-1$ such that the least positive exponent satisfying the equation $g^x \equiv 1 \ (\text{mod} \ m)$ is $m-1$ .

Another property of primitive roots that is used in the following proof is that for a given primitive root $g$ for a given prime modulus $m$ , the powers of $g$ would generate the elements of the set $\left\{1,2,3,\cdots,p-1 \right\}$ (these are the least residues that are relatively prime to the prime modulus $m$ ).

Basic properties of primitive roots are discussed in the post called Defining Primitive Root.

Proof of Theorem 1 (second proof)

We prove the direction that if $p$ is prime, then $(p-1)! \equiv -1 \ (\text{mod} \ p)$ .

$\Longrightarrow$
If $p=2$ , it is clear that $(p-1)! \equiv -1 \ (\text{mod} \ p)$ . Suppose $p$ is an odd prime. Then there exists a primitive root modulo $p$ . Let $g$ be one such. Because $p$ is prime, every integer $x$ in the interval $1 \le x \le p-1$ is relative prime to $p$ . One property of a primitive root for the prime modulus $p$ is that the powers of $g$ would generate the integers in the interval $1 \le x \le p-1$ . Specifically we have the following set equality

$\left\{r_1,r_2,r_3,\cdots,r_{p-1} \right\}=\left\{1,2,3,\cdots,p-1 \right\}$

where each $r_j$ is a least residue modulo $p$ , i.e., $0 \le r_j \le p-1$ and $r_j \equiv g^j \ (\text{mod} \ p)$ . As a result of the above set equality, we have the following congruence equality.

$g^1 g^2 g^3 \cdots g^{p-1} \equiv r_1 \cdot r_2 \cdot r_3 \cdots r_{p-1} \equiv (p-1)! \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

The exponents in the left-hand side of the above congruence equality can be summed as follows:

$\displaystyle 1+2+3+\cdots+p-1=\frac{(p-1)p}{2}$

The congruence equality (1) can be further simplified as follows:

$\displaystyle g^{\frac{(p-1)p}{2}} \equiv (p-1)! \ (\text{mod} \ p)$

It follows from Fermat’s theorem that $g^{p-1} \equiv 1 \ (\text{mod} \ p)$ . Thus the number $\displaystyle g^{\frac{p-1}{2}}$ satisfies the congruence equation $x^2 \equiv 1 \ (\text{mod} \ p)$ . By Lemma 2, $x^2 \equiv 1 \ (\text{mod} \ p)$ has exactly 2 solutions, namely $x=1$ or $x=p-1$ . So we have the following are two possibilities for $\displaystyle g^{\frac{p-1}{2}}$ .

$\displaystyle g^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$

$\displaystyle g^{\frac{p-1}{2}} \equiv p-1 \equiv -1 \ (\text{mod} \ p)$

But the first one is not possible since $g$ is a primitive root modulo $p$ . So the second congruence is true. It follows that

$\displaystyle (p-1)! \equiv g^{\frac{(p-1)p}{2}}=(-1)^p \equiv -1 \equiv \ (\text{mod} \ p)$

The above derivation concludes the proof of the theorem. $\blacksquare$

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

Primitive roots of prime moduli

Posted on September 18, 2013 by Dan Ma

In this post we show that if $m$ is prime, then there exists a primitive root modulo $m$ . It follows that there exist $\phi(m-1)$ primitive roots modulo $m$ where $\phi$ is Euler’s phi function.

For a basic discussion of the notion of primitive roots, see Defining Primitive Root. A basic discussion of the phi function is found in the post Euler’s phi function, part 1 and in the post Euler’s phi function, part 2.

In modular arithmetic, not all moduli have primitive roots. For example, for the modulus $m=8$ , the least residues that are relatively prime are $a=1,3,5,7$ . Thus $\phi(8)=4$ . For each one of these values of $a$ , $a^2 \equiv 1 \ (\text{mod} \ 8)$ . Thus every one of them has order $2 < \phi(8)$ . Thus there are no primitive roots modulo $m=8$ . We prove the following results.

Theorem 1

$p$

$\text{ }$

Theorem 2

$p$

$\phi(m-1)$

$m$

$\text{ }$

Theorem 1 is the main theorem in this post. Theorem 2 follows from Theorem 1 and from a result proved in a previous post. The previous result is that if there exists a primitive root modulo $m$ (not necessarily prime), then there exist exactly $\phi(\phi(m))$ many primitive roots modulo $m$ (see Theorem 6 and Corollary 7 in Defining Primitive Root). Since Theorem 1 provides the existence of a primitive root, Theorem 2 follows from Theorem 1 and from the previous result and from the fact that $\phi(p)=p-1$ for any prime number.

___________________________________________________________________________________________________________________

Proving the Main Theorem

Our proof of the existence of a primitive root of any prime modulus uses only elementary techniques. Most of the results we need are developed here in this post. The first result is proved in a previous post (see Theorem 4 in Defining Primitive Root).

Lemma 3

$a$

$0 \le a \le m-1$

$a$

$m$

$k$

$a$

$m$

$n$

The congruence condition $a^n \equiv 1 \ (\text{mod} \ m)$ holds.
The number $k$ is a divisor of $n$ .

The second result is that of polynomial congruence. Let $f(x)$ be a polynomial with integer coefficients. In the next lemma, we are interested in solving the polynomial congruence equation $f(x) \equiv 0 \ (\text{mod} \ m)$ .

Lemma 4

$m$

$f(x)$

$n$

$f(x) \equiv 0 \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

$\text{ }$

has at most $n$ solutions.

Proof of Lemma 4

Suppose $f(x)=a_n x^n +a_{n-1} x^{n-1} + \cdots+a_2 x^2+a_1 x + a_0$ where $a_n \not \equiv 0 \ (\text{mod} \ m)$ . We prove the lemma by induction on the degree $n$ .

Suppose $n=1$ . We have $f(x)=a_1 x +a_0 \equiv 0 \ (\text{mod} \ m)$ . Since $m$ is prime and $a_1 \not \equiv 0 \ (\text{mod} \ m)$ , the coefficient $a_1$ must be relatively prime to $m$ . Then the congruence equation $a_1 x +a_0 \equiv 0 \ (\text{mod} \ m)$ has exactly one solution. The number of solutions of a linear congruence is the same as the greatest common divisor of the coefficient of $x$ and the modulus $m$ (see Theorem 2 in the post Solving Linear Congruences).

Suppose the lemma is true for polynomials of degree $n-1$ . Consider two cases – either equation (1) has no solution or equation (1) has a solution. If the first case is true, then the conclusion of the lemma is true.

Suppose the second case is true. Suppose $b$ is a solution to equation (1). It follows that $f(b) \equiv 0 \ (\text{mod} \ m)$ and that $b$ is a least residue modulo $m$ .

Our next goal is to factor the polynomial $f(x)$ into a product of a first degree polynomial and a polynomial of degree $n-1$ . To this end, note that $x-b$ is a factor of $x^w-b^w$ for $w=1,2,3,\cdots,n$ . We have the following derivation

$\displaystyle \begin{aligned} f(x)&\equiv f(x)-f(b) \\&\equiv a_n (x^n-b^n) +a_{n-1} (x^{n-1}-b^{n-1}) + \cdots+a_2 (x^2-b^2)+a_1 (x-b) \\&\equiv (x-b) \cdot h(x) \ (\text{mod} \ m) \end{aligned}$

where $h(x)$ is a polynomial of degree $n-1$ .

Whenever $f(x) \equiv 0 \ (\text{mod} \ m)$ , we have $m \ \lvert \ (x-b) \cdot h(x)$ . Using the fact that $m$ is prime and Euclid’s lemma, either $m \ \lvert \ (x-b)$ or $m \ \lvert \ h(x)$ . In terms of congruence, either $x-b \equiv 0 \ (\text{mod} \ m)$ or $h(x) \equiv 0 \ (\text{mod} \ m)$ . The first congruence has exactly one solution. By induction hypothesis, the second congruence has at most $n-1$ solutions. Together, equation (1) has at most $n$ solutions. $\blacksquare$

Lemma 5

$m$

$d \ \lvert \ (p-1)$

$x^d \equiv 1 \ (\text{mod} \ m)$

$d$

Proof of Lemma 5

Suppose $d \ \lvert \ (p-1)$ . Fermat’s little theorem tells us that $x^{m-1}-1 \equiv 0 \ (\text{mod} \ m)$ has exactly $m-1$ solutions, namely $1,2,3,\cdots,m-1$ . We can factor the polynomial $x^{m-1}-1$ as follows:

$g(x)=x^{m-1}-1=(x^d-1) \cdot (x^{m-1-d}+x^{m-1-2d}+x^{m-1-3d}+\cdots+x^{d}+1)$

Let $t(x)=(x^{m-1-d}+x^{m-1-2d}+x^{m-1-3d}+\cdots+x^{d}+1)$ . Whenever $g(x) \equiv 0 \ (\text{mod} \ m)$ , $m \ \lvert \ g(x)=x^{m-1}-1=(x^d-1) \cdot t(x)$ . By Euclid’s lemma, $m \ \lvert \ (x^d-1)$ or $m \ \lvert \ t(x)$ . In terms of congruence, $x^d \equiv 1 \ (\text{mod} \ m)$ or $t(x) \equiv 0 \ (\text{mod} \ m)$ .

By Lemma 4, the congruence $t(x) \equiv 0 \ (\text{mod} \ m)$ has at most $m-1-d$ solutions. Since $x^{m-1}-1 \equiv 0 \ (\text{mod} \ m)$ has exactly $m-1$ solutions, the congruence equation $x^d \equiv 1 \ (\text{mod} \ m)$ has at least $d$ many solutions.

By Lemma 4, the congruence equation $x^d \equiv 1 \ (\text{mod} \ m)$ has at most $d$ solutions. Thus $x^d \equiv 1 \ (\text{mod} \ m)$ has exactly $d$ many solutions. $\blacksquare$

We need one more lemma before proving Theorem 1.

Lemma 6

$a$

$b$

$0 \le a,b \le m-1$

$\alpha$

$a$

$m$

$\beta$

$b$

$m$

Suppose that $\alpha$ and $\beta$ are relatively prime. Then $\alpha \cdot \beta$ is the order of $a \cdot b$ modulo $m$ .

Proof of Lemma 6

Let $\gamma$ be the order of $a \cdot b$ modulo $m$ . We show that $\gamma=\alpha \beta$ . The following derivation shows that $\alpha \ \lvert \ \gamma$ .

$1 \equiv 1^\beta \equiv ((ab)^\gamma)^\beta =(ab)^{\gamma \beta}=(a)^{\gamma \beta} (b)^{\gamma \beta}=(a)^{\gamma \beta} (b^{\gamma})^{\beta} \equiv a^{\gamma \beta} \ (\text{mod} \ m)$

Since $a^{\gamma \beta} \equiv 1 \ (\text{mod} \ m)$ , we have $\alpha \ \lvert \ \gamma \beta$ (by Lemma 3). Since $\alpha$ and $\beta$ are relatively prime, $\alpha \ \lvert \ \gamma$ . By a symmetrical argument, it can also be shown that $\beta \ \lvert \ \gamma$ .

Since $\alpha \ \lvert \ \gamma$ , we have $\gamma=\alpha \cdot t$ for some integer $t$ . Since $\beta \ \lvert \alpha \cdot t$ , it follows that $\beta \ \lvert t$ (Euclid’s lemma). So $t=\beta \cdot z$ for some integer $z$ . Now $\gamma=\alpha \cdot \beta \cdot z$ . This means that $\alpha \beta \ \lvert \ \gamma$ .

On the other hand, we have $\gamma \ \lvert \alpha \beta$ . This follows from the following derivation and from Lemma 3.

$(ab)^{\alpha \beta}=(a^\alpha)^\beta \cdot (b^\beta)^\alpha \equiv 1 \ (\text{mod} \ m)$

It follows that $\gamma= \alpha \beta$ . $\blacksquare$

Remark
Lemma 6 indicates that the orders of two numbers are multiplicative as long as the two orders are relatively prime. As a corollary of Lemma 6, it follows that the order of a product of finitely many numbers (for the same modulus) is the product of the individual orders provided that the orders are pairwise relatively prime. This fact will be used in the proof of Theorem 1 below.

Proof of Theorem 1

We start off with a prime factorization of the number $p-1$ .

$\displaystyle p-1=w_1^{e_1} \cdot w_2^{e_2} \cdot w_3^{e_3} \cdots w_n^{e_n}$

In the above factorization, the numbers $w_i$ are distinct prime numbers and the exponents $e_i \ge 1$ .

For each $i$ , it is clear that $w_i^{e_i} \ \lvert \ (p-1)$ . By Lemma 5, the congruence equation

$\displaystyle x^{w_i^{e_i}} \equiv 1 \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

has exactly $w_i^{e_i}$ many solutions. Note that the $w_i^{e_i}$ many solutions are integers in the interval $0 \le x \le p-1$ . Furthermore, the order modulo $p$ of each of these solutions to (2) is a divisor of $w_i^{e_i}$ (by Lemma 3).

In fact, from Lemma 3, we can say that for any integer $x$ in the interval $0 \le x \le p-1$ , the number $x$ is a solution of equation (2) if and only if the order modulo $p$ of $x$ is a divisor of $w_i^{e_i}$ . We have the following claim.

Claim
For each $i$ , we claim that there exists at least one integer $a_i$ in the interval $0 \le x \le p-1$ such that the order of $a_i$ modulo $p$ is $w_i^{e_i}$ .

To see the above claim, the congruence equation

$\displaystyle x^{w_i^{e_i-1}} \equiv 1 \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$

has exactly $w_i^{e_i-1}$ many solutions in the interval $0 \le x \le p-1$ (using Lemma 5). Furthermore, the order of each of the solutions of (3) is a divisor of $w_i^{e_i-1}$ .

In fact, from Lemma 3, we can also say that for any integer $x$ in the interval $0 \le x \le p-1$ , the number $x$ is a solution of equation (3) if and only if the order modulo $p$ of $x$ is a divisor of $w_i^{e_i-1}$ .

Note that the solutions of (3) are also solutions of (2). This is clear since we know that divisors of $w_i^{e_i-1}$ are also divisors of $w_i^{e_i}$ .

Thus there are $w_i^{e_i}-w_i^{e_i-1}$ many of the solutions to (2) that are not solutions to equation (3). Pick one such solution and call it $a_i$ . Let $k$ be the order of $a_i$ modulo $p$ . There are three possibilities for $k$ :

$k \le w_i^{e_i-1} \ \ \ \ \ w_i^{e_i-1}<k<w_i^{e_i} \ \ \ \ \ k=w_i^{e_i}$

Since $a_i$ is a solution to (2), the number $k$ is a divisor of $w_i^{e_i}$ . Note that there are no divisors of $w_i^{e_i}$ within the interval $w_i^{e_i-1}<y<w_i^{e_i}$ since $w_i$ is a prime number. So $w_i^{e_i-1}<k<w_i^{e_i}$ is not possible.

Since $a_i$ is not a solution to (3), the number $k$ is not a divisor of $w_i^{e_i-1}$ . This means that $k \le w_i^{e_i-1}$ is not possible. Since $w_i$ is prime, $k$ must be a power of $w_i$ . Since $k$ must be a power of $w_i$ , if $k \le w_i^{e_i-1}$ , $k$ is then a divisor of $w_i^{e_i-1}$ .

So the only possibility is that $k=w_i^{e_i}$ . This establishes the above claim.

Let $g=a_1 \cdot a_2 \cdots a_n$ . The primitive root modulo $p$ we are looking for is either $g$ if $g<p$ or the least residue of $g$ if $g \ge p$ .

According to the above claim, the order modulo $p$ of $a_i$ is $w_i^{e_i}$ . Clearly $w_i^{e_i}$ and $w_j^{e_j}$ are relatively prime for $i \ne j$ . As a corollary of Lemma 6, the order of the product $g=a_1 \cdot a_2 \cdots a_n$ is the products of $w_i^{e_i}$ , namely $p-1$ . Thus $g=a_1 \cdot a_2 \cdots a_n$ or its least residue modulo $p$ is a primitive root. $\blacksquare$

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

An elementary algorithm for finding primitive roots

Posted on September 12, 2013 by Dan Ma

In the previous post Finding Primitive Roots, we demonstrate one approach for finding all primitive roots of a prime modulus. In this post, we summarize the ideas behind that example.

Throughout this discussion $m$ is a positive integer that is used as the modulus for modular arithmetic, and $a$ is assumed to be a positive integer that is relatively prime to $m$ such that $0 \le a \le m-1$ .

According to Fermat’s little theorem, if the modulus $m$ is prime, then $a^{m-1} \equiv 1 \ (\text{mod} \ m)$ . If the modulus is relaxed to include non-prime integers as well, then we have Euler’s theorem which states that $a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$ where $\phi(m)$ is Euler’s phi function. For any modulus $m$ , $\phi(m)$ is simply the numbers of possible values of $a$ that are relatively prime to $m$ . For example, $\phi(m)=10$ if $m=11$ and $\phi(m)=4$ if $m=10$ .

So it is always the case that $a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$ . Another way to say this is that the number $\phi(m)$ is always a solution to the following congruence equation.

$\displaystyle a^x \equiv 1 \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

With this above discussion in mind, we define the notion of order. The order of $a$ modulo $m$ is the least positive integer solution to the congruence equation (1).

Furthermore, the number $a$ is said to be a primitive root modulo $m$ if the least positive integer solution to (1) is $\phi(m)$ .

Note that even though the notions of order and primitive root are defined here for integers $a$ that are relatively prime to $m$ with $0 \le a \le m-1$ , the definitions are also valid for positive $a$ outside the range $0 \le a \le m-1$ . Relaxing the definitions can make some proofs go easier (e.g. Theorem 2 below).

___________________________________________________________________________________________________________________

An Approach in Finding Primitive Roots

We now summarize the ideas discussed in the previous post Finding Primitive Roots.

Recall that $a$ is a positive integer less than $m$ that is relatively prime to $m$ . How do we check if $a$ is a primitive root? On the face of it, we need to check that no positive integer less than $\phi(m)$ is a solution to equation (1). It turns out that we only need to check positive integers less than $\phi(m)$ that are divisors of $\phi(m)$ . We have the following theorem.

Theorem 1

The number $a$ is a primitive root modulo $m$ .
Every positive divisor $k$ of $\phi(m)$ with $k < \phi(m)$ is not a solution of the congruence equation (1).

$\text{ }$
If we know that there exists a primitive root for a modulus, the followng theorem tells us how to find the other primitive roots.

Theorem 2

$a$

$m$

$\phi(\phi(m))$

$m$

$a^j$

$j$

$\left\{j: 1 \le j \le \phi(m) \text{ and } j \text{ is relatively prime to } \phi(m) \right\} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

Thus the above two theorems taken together form an algorithm for finding primitve roots of a modulus (if one is known to exist to begin with). We can use Theorem 1 to find a primitive root. Once we have found one, we can raise it to exponents that are relatively prime to the number $\phi(m)$ to find the remaining primitive roots. Since there are $\phi(\phi(m))$ many positive integers that are less than $\phi(m)$ and relatively prime to $\phi(m)$ , there are $\phi(\phi(m))$ many primitive roots modulo $m$ (if one exists).

Before proving the theorems, let’s look at a quick example.

For $m=11$ , $\phi(11)=10$ . The candidates for primitive roots modulo $m=11$ are in the set $\left\{2,3,4,\cdots,10 \right\}$ . The divisors of $\phi(11)=10$ are $1,2,5$ . According to Theorem 1, we only need to raise these numbers to exponents that are divisors of $\phi(11)=10$ .

Note that $2^1 \equiv 2 \ (\text{mod} \ 11)$ , $2^2 \equiv 4 \ (\text{mod} \ 11)$ and $2^5 \equiv 10 \ (\text{mod} \ 11)$ . Thus $a=2$ is a primitive root modulo $m=11$ .

The positive integers that are less than $\phi(11)=10$ and that are relatively prime to $\phi(11)=10$ are $1, 3, 7, 9$ . So there are four primitive roots modulo $m=11$ . They are:

$\displaystyle \begin{aligned} \text{ }&2^1 \equiv 2 \ (\text{mod} \ 11) \\&2^3 \equiv 8 \ (\text{mod} \ 11) \\&2^7 \equiv 7 \ (\text{mod} \ 11) \\&2^9 \equiv 6 \ (\text{mod} \ 11) \end{aligned}$

___________________________________________________________________________________________________________________

Proof of Theorems

Proof of Theorem 1

The direction $1 \Longrightarrow 2$ is clear. If $a$ is a primitive root modulo $m$ , then by definition, no positive integer less than $\phi(m)$ can be a solution to the congruence equation (1).

$2 \Longrightarrow 1$
Let $h$ be the order of $a$ modulo $m$ . The key to the proof is that $h$ must be a divisor of $\phi(m)$ (see Theorem 4 and Corollary 5 in the post Defining Primitive Root). For the sake of completeness, we provide the proof here.

Since $h$ is the least positive solution of the congruence equation (1), $h \le \phi(m)$ . Using the division algorithm, we have $\phi(m)=q \cdot h+r$ for some integers $q$ and $r$ where $0 \le r <h$ . We have the following calculation.

$1 \equiv a^{\phi(m)}=(a^h)^q \cdot a^r \equiv (1)^q \cdot a^r \equiv a^r \ (\text{mod} \ m)$

So we have $a^r \equiv 1 \ (\text{mod} \ m)$ and $0 \le r <h$ . Since $h$ is the least positive solution of (1), the only possibility is that $r=0$ . Hence $\phi(m)=q \cdot h$ and $h$ is a divisor of $\phi(m)$ .

Now back to the proof for $2 \Longrightarrow 1$ . We claim that $h=\phi(m)$ , implying that $a$ is a primitive root modulo $m$ . If $h<\phi(m)$ , then $h$ is a positive divisor of $\phi(m)$ with $h<\phi(m)$ such that $h$ is a solution of the congruence equation (1) (i.e. the condition 2 does not hold). Thus if condition 2 holds, condition 1 must hold. $\blacksquare$

Proof of Theorem 2
Theorem 2 is the combined result of Theorem 6 and Corollary 7 in the post Defining Primitive Root. To make this post as self contained as possible, we repeat the proof, showing just the essential parts.

We do need one theorem from the previous post Defining Primitive Root. Let $w$ be a positive integer that is relatively prime to the modulus $m$ . Let $k$ be the order of $w$ modulo $m$ . Theorem 4 in this post states that for any , $w^n \equiv 1 \ (\text{mod} \ m)$ if and only if $k \ \lvert \ n$ .

There are exactly $\phi(\phi(m))$ many elements in the above set indicated by (2). So there are these many powers of $a$ . The first thing to show is that the powers $a^j$ are all distinct congruent modulo $m$ . Hence their least residues are also distinct.

To see this, suppose $a^j \equiv a^i \ (\text{mod} \ m)$ where $i, j \le \phi(m)$ with $i \le j$ . We want to show $i=j$ . Suppose that $i<j$ . Since $a^i$ is relatively prime to $m$ , we can cancel out $a^i$ on both sides and obtain $a^{j-i} \equiv 1 \ (\text{mod} \ m)$ . Since $j-i<\phi(m)$ and $a$ is a primitive root modulo $m$ , $a^{j-i} \not \equiv 1 \ (\text{mod} \ m)$ . So $i=j$ . Thus if $i \ne j$ , then $a^j \not \equiv a^i \ (\text{mod} \ m)$ .

The next thing to show is that $a^j$ is a primitive root modulo $m$ for any $j$ in the above set (2). Suppose $j$ is one such element of the set (2). Then $j$ and $\phi(m)$ are relatively prime.

Let $h$ be the order of $a^j$ modulo $m$ . We have $a^{j \cdot h}=(a^h)^j \equiv 1 \ (\text{mod} \ m)$ . Since $a$ is a primitive root modulo $m$ , it follows that $\phi(m) \ \lvert \ j \cdot h$ (according Theorem 4 in Defining Primitive Root). Since $\phi(m)$ and $j$ are relatively prime, $\phi(m) \ \lvert \ h$ .

On the other hand, $(a^j)^{\phi(m)}=(a^{\phi(m)})^j \equiv 1 \ (\text{mod} \ m)$ . Since $h$ is the order of $a^j$ , it follows that $h \ \lvert \ \phi(m)$ (also using Theorem 4 in Defining Primitive Root).

With $\phi(m) \ \lvert \ h$ and $h \ \lvert \ \phi(m)$ , we have $h=\phi(m)$ . Thus $a^j$ is a primitive root modulo $m$ and so is its least residue. $\blacksquare$

___________________________________________________________________________________________________________________

Finding Primitive Roots

Posted on September 9, 2013 by Dan Ma

In the previous post called Defining Primitive Root, we define and discuss the notion of primitive roots and prove some elementary theorems. In this post we use these theorems to find primitive roots modulo a prime number. The algorithm demonstrated here is further described in An elementary algorithm for finding primitive roots.

It is a theorem that if the modulus $m$ is a prime number, there exist primitive roots modulo $m$ . But the theorem does not provide an algorithm of how to find one. We demonstrate a process of how to find all the primitive roots of a prime modulus. We use the prime modulus $m=277$ , a number that is small enough to make the calculation not too lengthy and is big enough to make the demonstration meaningful.

The modular arithmetic calculation discussed below can be programmed in a computer or done using a hand-held calculator using the fast powering algorithm (which is discussed in this post).

__________________________________________________________________________________________________________________

Background

For any positive integer $m$ , let $\mathbb{Z}_m$ be the set $\left\{0,1,2,\cdots,m-1 \right\}$ . Let $(\mathbb{Z}_m)^*$ be the set of all numbers $a$ in $\mathbb{Z}_m$ that is relatively prime to $m$ . Euler’s phi function $\phi(m)$ is the count of the elements in the set $(\mathbb{Z}_m)^*$ . Euler’s theorem states that for any $a \in (\mathbb{Z}_m)^*$ , $a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$ .

Euler’s theorem establishes a solution for the congruence equation $a^{x} \equiv 1 \ (\text{mod} \ m)$ where $x$ is a positive integer. Whenever $\phi(m)$ is the smallest positive solution to $a^{x} \equiv 1 \ (\text{mod} \ m)$ , the number $a$ is said to be a primitive root modulo $m$ .

In general, the smallest positive solution to the equation $a^{x} \equiv 1 \ (\text{mod} \ m)$ is called the order of $a$ modulo $m$ . Thus, in terms of the notion of order, any number $a \in (\mathbb{Z}_m)^*$ is a primitive root modulo $m$ whenever the order of $a$ and $\phi(m)$ coincide.

__________________________________________________________________________________________________________________

Finding One Primitive Root

For the modulus $m=277$ , $\mathbb{Z}_m=\left\{0,1,2,\cdots,276 \right\}$ and $(\mathbb{Z}_m)^*=\left\{1,2,3,\cdots,276 \right\}$ . So $\phi(277)=276$ . According to Euler’s theorem, $a^{\phi(m)}=a^{276} \equiv 1 \ (\text{mod} \ 277)$ for all $a \in (\mathbb{Z}_m)^*=\left\{1,2,3,\cdots,276 \right\}$ .

Obviously $a=1$ can never be a primitive root. Thus candidates for primitive roots are the $275$ numbers in the set $\left\{2,3,\cdots,276 \right\}$ . As we will see below, we only need to find one primitive root $a$ from this list. Our plan is to find the smallest primitive root $a$ from this list.

Since $a^{\phi(m)}=a^{276} \equiv 1 \ (\text{mod} \ 277)$ , showing that $a$ is a primitive root modulo $m=277$ requires verifying that $a^j \not \equiv 1 \ (\text{mod} \ 277)$ for each $j \in \left\{2,3,\cdots,275 \right\}$ . We can get by with less computation.

If $x=k$ is the smallest positive integer solution to $a^{x} \equiv 1 \ (\text{mod} \ m)$ , then $k \ \lvert \ \phi(m)$ (see Theorem 4 and Corollary 5 in the post Defining Primitive Root).

So the order of a number $a$ can only be the numbers $j$ in the set $\left\{2,3,\cdots,275 \right\}$ that are divisors of $\phi(277)=276$ . If $a^j \not \equiv 1 \ (\text{mod} \ 277)$ for all such $j$ , then the number $a$ is a primitive root modulo $m=277$ . If $a^j \equiv 1 \ (\text{mod} \ 277)$ for one such $j$ , then the number $a$ is not a primitive root modulo $m=277$ . This is the approach we take to find one primitive root modulo $m=277$ .

Note that $276=2^2 \cdot 3 \cdot 23$ , which has eleven divisors that are less than $276$ . They are:

$\displaystyle \begin{aligned} \text{divisors of } 276&=1 \\&=2 \\&=3 \\&=4 \\&=6 \\&=12 \\&=23 \\&=46 \\&=69 \\&=92 \\&=138 \end{aligned}$

We start with $a=2$ and check $a^j$ where $j$ is from the above list of divisors. The first $a$ where $a^j \not \equiv 1 \ (\text{mod} \ 277)$ for all eleven $j$ is a primitive root.

We have the following calculation:

$2^{92} \equiv 1 \ (\text{mod} \ 277)$

$3^{69} \equiv 1 \ (\text{mod} \ 277)$

$4^{46} \equiv 1 \ (\text{mod} \ 277)$

So $a=2,3,4$ are not primitive root modulo $m=277$ . For $a=5$ , $a^j \not \equiv 1 \ (\text{mod} \ 277)$ for all eleven $j$ . Thus $a=5$ is the smallest primitive root modulo $m=277$ .

__________________________________________________________________________________________________________________

Finding the Other Primitive Roots

If there is one primitive root for a modulus $m$ , there are exactly $\phi(\phi(m))$ many primitive roots (see Corollary 7 in the post Defining Primitive Root). For the modulus $m=277$ , there are $\phi(\phi(277))=\phi(276)=88$ primitive roots.

Theorem 6 in that same post says that if $a$ is a primitive root modulo $m$ , then $a^j$ (or the least residue of it) is also a primitive root for all integers $j$ that are relatively prime to $\phi(m)$ .

So in this example, for the exponents we only need to find the numbers in the set $\left\{1,2,3,\cdots,276 \right\}$ that are relatively prime to $\phi(277)=276$ .

To find the $88$ numbers that are relatively prime to $\phi(277)=276$ , we can list out the numbers $1,2,3,\cdots,276$ . Since the prime factors of $276$ are $2,3,23$ , we cross out the multiples of $2$ , the multiples of $3$ , and finally the multiples of $23$ . The following matrix shows the $88$ numbers that remain.

$\displaystyle \begin{bmatrix} 1&5&7&11&13&17&19&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&101&103&107&109&113&119&121&125 \\ 127&131&133&137&139&143&145&149&151&155 \\ 157&163&167&169&173&175&179&181&185&187 \\ 191&193&197&199&203&205&209&211&215&217 \\ 221&223&227&229&233&235&239&241&245&247 \\ 251&257&259&263&265&269&271&275&\text{ }&\text{ } \end{bmatrix}$

From the last section, we know that $a=5$ is a primitive root modulo $m=277$ . For each number $j$ in the above matrix, we calculate the least residue of $5^j$ modulo $m=277$ . The following shows the results.

$\displaystyle \begin{bmatrix} 5&78&11&227&135&167&20&44&77&263 \\ 114&80&140&176&31&221&179&43&6&150 \\ 124&53&162&172&24&46&219&212&94&134 \\ 96&184&45&17&99&259&107&180&68&119 \\ 205&151&174&166&272&199&266&50&142&110 \\ 257&233&200&14&163&197&137&101&246&56 \\ 98&234&271&127&153&224&115&105&253&231 \\ 58&65&183&143&181&93&232&260&178&18 \\ 170&97&209&158&72&126&103&111&\text{ }&\text{ } \end{bmatrix}$

For example, the following calculation gives the ten results in the first row of the above matrix.

$5^{1} \equiv 5 \ (\text{mod} \ 277)$

$5^{5} \equiv 78 \ (\text{mod} \ 277)$

$5^{7} \equiv 11 \ (\text{mod} \ 277)$

$5^{11} \equiv 227 \ (\text{mod} \ 277)$

$5^{13} \equiv 135 \ (\text{mod} \ 277)$

$5^{17} \equiv 167 \ (\text{mod} \ 277)$

$5^{19} \equiv 20 \ (\text{mod} \ 277)$

$5^{25} \equiv 44 \ (\text{mod} \ 277)$

$5^{29} \equiv 77 \ (\text{mod} \ 277)$

$5^{31} \equiv 263 \ (\text{mod} \ 277)$

The following matrix shows the $88$ primitive roots sorted in increasing order.

$\displaystyle \begin{bmatrix} 5&6&11&14&17&18&20&24&31&43 \\ 44&45&46&50&53&56&58&65&68&72 \\ 77&78&80&93&94&96&97&98&99&101 \\ 103&105&107&110&111&114&115&119&124&126 \\ 127&134&135&137&140&142&143&150&151&153 \\ 158&162&163&166&167&170&172&174&176&178 \\ 179&180&181&183&184&197&199&200&205&209 \\ 212&219&221&224&227&231&232&233&234&246 \\ 253&257&259&260&263&266&271&272&\text{ }&\text{ } \end{bmatrix}$

__________________________________________________________________________________________________________________

Exercise

We leave with an exercise (for any interested reader).

Find all the primitive roots modulo $m=127$ . Answers are show below.

$\text{ }$

$\displaystyle \begin{bmatrix} 3&6&7&12&14&23&29&39&43&45 \\ 46&48&53&55&56&57&58&65&67&78 \\ 83&85&86&91&92&93&96&97&101&106 \\ 109&110&112&114&116&118&\text{ }&\text{ }&\text{ }&\text{ } \end{bmatrix}$

The algorithm demonstrated here is further described in An elementary algorithm for finding primitive roots.

___________________________________________________________________________________________________________________

Defining Primitive Root

Posted on September 3, 2013 by Dan Ma

In this post, we define the notion of primitive root and prove some elementary results. Instead of jumping right into the definition, we take a leisurely approach by first looking at some of the related basic notions.

___________________________________________________________________________________________________________________

Setting Up the Scene

Two positive integers $a$ and $b$ are relatively prime if they do not share any prime factors, i.e., their greatest common divisor is one (the only positive integer that can divide both numbers is one). For example, $a=9$ and $b=14$ are relatively prime, as are $a=9$ and $b=35$ . If $a$ and $b$ are relatively prime, we also say that $a$ is relatively prime to $b$ or $b$ is relatively prime to $a$ . Our notation for greatest common divisor is $\text{GCD}(a,b)$ .

In working with modular arithmetic where the modulus is the positive integer $m$ , every integer is congruent modulo $m$ to exactly one number in the set $\left\{0,1,2,\cdots,m-1 \right\}$ . The numbers in this set are called the least residues modulo $m$ . In doing modulus $m$ calculation, for some purposes we only need to reduce the result to one number in this set. For convenience, we use the notation $\mathbb{Z}_m=\left\{0,1,2,\cdots,m-1 \right\}$ .

An even more interesting set is the set of all integers $a$ in $\mathbb{Z}_m$ such that $a$ and the modulus $m$ are relatively prime. To facilitate the discussion, we describe this set as follows:

$\displaystyle \begin{aligned} (\mathbb{Z}_m)^*&=\left\{a \in \mathbb{Z}_m: a \text{ is relatively prime to } m \right\} \\&=\left\{a \in \mathbb{Z}_m:\text{GCD}(a,m) =1 \right\} \end{aligned}$

When the modulus $m$ is a prime number, $(\mathbb{Z}_m)^*=\left\{1,2,\cdots,m-1 \right\}$ , the non-zero elements of $\mathbb{Z}_m$ . The following theorem gives some indication why $(\mathbb{Z}_m)^*$ is an interesting set, which provides alternative characterizations of $(\mathbb{Z}_m)^*$ .

Theorem 1

$a$

$\mathbb{Z}_m$

$\text{GCD}(a,m)=1$ .
There is a $b \in \mathbb{Z}_m$ such that $a \cdot b \equiv 1 \ (\text{mod} \ m)$ .
Some positive power of $a$ modulo $m$ is $1$ , i.e., $a^n \equiv 1 \ (\text{mod} \ m)$ for some positive integer $n$ .

$\text{ }$

The proof of Theorem 1 can be found in the post Euler’s phi function, part 1.

The Euler’s phi function, denoted by $\phi(m)$ , is the number of integers $a$ where $0 \le a \le m-1$ such that $a$ and the modulus $m$ are relatively prime. In light of the above discussion, $\phi(m)$ is the number of elements in the set $(\mathbb{Z}_m)^*$ . It is also the case that $\phi(m)$ is the number of elements in $\mathbb{Z}_m$ that satisfies any one of the three conditions in Theorem 1.

___________________________________________________________________________________________________________________

Defining Primitive Root

When we are interested in the power of a number being one congruence modulo $m$ , according to Theorem 1, the base has to be a number that is relatively prime to the modulus. We have already come across two such situations – Fermat’s little theorem and its generalization, Euler’s theorem.

Theorem 2 (Fermat’s little theorem)

$m$

$a^{m-1} \equiv 1 \ (\text{mod} \ m)$

$a$

$m$

$\text{ }$

Theorem 3 (Euler’s theorem)

$a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$

$a$

$m$

$\text{ }$

Theorem 2 follows from Theorem 3, which is proved in the post Euler’s phi function, part 1.

Definitions
We now define the notion of primitive root. Let $a$ be an integer in $\mathbb{Z}_m$ that is relatively prime to the modulus $m$ . Based on the above theorems, $a^k \equiv 1 \ (\text{mod} \ m)$ for some positive integer $k$ . By the order of $a$ modulo $m$ , we mean the least positive integer $k$ such that $a^k \equiv 1 \ (\text{mod} \ m)$ . The number $a$ is a primitive root modulo $m$ if the order of $a$ modulo $m$ is the number $\phi(m)$ .

By Theorem 3, the order of $a$ modulo $m$ is always $\le \phi(m)$ . We will see below that the order always divides $\phi(m)$ (see Theorem 4).

One comment. The notions of order and primitive roots are defined above for integers in $\mathbb{Z}_m$ . In actuality, the two notations can be defined for all positive integers. It is just that we are interested in finding primitive roots among the residues, i.e., the elements of the set $\mathbb{Z}_m$ . In some cases, it will be helpful to think of orders of numbers outside of $\mathbb{Z}_m$ and think of numbers outside of $\mathbb{Z}_m$ as primitive roots (e.g. in the proof of Theorem 6 below).

Suppose that the modulus $m$ is a prime number. Fermat’s little theorem tells us that $a^{m-1} \equiv 1 \ (\text{mod} \ m)$ for any $a$ that is relatively prime to $m$ . Is $m-1$ the only exponent for which the power of $a$ is one? Take $m=11$ . The following table gives the powers of $a$ modulus $m=11$ where $1 \le a \le 10$ .

$\displaystyle \begin{bmatrix} a^1&a^2&a^3&a^4&a^5&a^6&a^7&a^8&a^9&a^{10} \\\text{ }&\text{ }&\text{ } \\ 1&1&1&1&1&1&1&1&1&1 \\ 2&4&8&5&10&9&7&3&6&1 \\ 3&9&5&4&1&3&9&5&4&1 \\ 4&5&9&3&1&4&5&9&3&1 \\ 5&3&4&9&1&5&3&4&9&1 \\ 6&3&7&9&10&5&8&4&2&1 \\ 7&5&2&3&10&4&6&9&8&1 \\ 8&9&6&4&10&3&2&5&7&1 \\ 9&4&3&5&1&9&4&3&5&1 \\ 10&1&10&1&10&1&10&1&10&1 \end{bmatrix}$

The above table shows that for $a=2,6,7,8$ , the number $10$ is the least exponent for which the power of $a$ is one. In other words, the order for these $a$ is $\phi(11)=10$ . The numbers $a=2,6,7,8$ are primitive roots modulo $m=11$ . The other values of $a$ are not primitive roots. The order for $a=1$ is $1$ . The order for $a=10$ is $2$ . The order for $a=3,4,5,9$ is $5$ .

Note that in the above table, for the numbers $a$ that are primitive roots, the set $\left\{a^1,a^2,a^3,\cdots,a^{\phi(11)} \right\}$ equals the set $\left\{1,2,3,\cdots,10 \right\}$ . So a primitive root generates by powering all the least residues that are relatively prime to the modulus.

Let’s look at a modulus that is not prime. Take $m=10$ . The following table gives the powers of $a$ modulus $m=10$ where $1 \le a \le 9$ .

$\displaystyle \begin{bmatrix} a^1&a^2&a^3&a^4&a^5&a^6&a^7&a^8&a^9 \\\text{ }&\text{ }&\text{ } \\ 1&1&1&1&1&1&1&1&1 \\ 2&4&8&6&2&4&8&6&2 \\ 3&9&7&1&3&9&7&1&3 \\ 4&6&4&6&4&6&4&6&4 \\ 5&5&5&5&5&5&5&5&5 \\ 6&6&6&6&6&6&6&6&6 \\ 7&9&3&1&7&9&3&1&7 \\ 8&4&2&6&8&4&2&6&8 \\ 9&1&9&1&9&1&9&1&9 \end{bmatrix}$

Note that $\phi(10)=4$ since $(\mathbb{Z}_{10})^*=\left\{1,3,7,9 \right\}$ is the set of all the least residues that are relatively prime to $m=10$ . In terms of powers of $a$ , we should only focus on $\left\{1,3,7,9 \right\}$ . The following is the reduced table.

$\displaystyle \begin{bmatrix} a^1&a^2&a^3&a^4&a^5&a^6&a^7&a^8&a^9 \\\text{ }&\text{ }&\text{ } \\ 1&1&1&1&1&1&1&1&1 \\ 3&9&7&1&3&9&7&1&3 \\ 7&9&3&1&7&9&3&1&7 \\ 9&1&9&1&9&1&9&1&9 \end{bmatrix}$

Note that $a^4 \equiv 1 \ (\text{mod} \ 10)$ for all four $a$ . But only $a=3,7$ are primitive roots modulo $m=10$ .

Also note that in the above table, for the numbers $a$ that are primitive roots, the set $\left\{a^1,a^2,a^3,a^4 \right\}$ equals the set $\left\{1,3,7,9 \right\}$ . So a primitive root generates by powering all the least residues that are relatively prime to the modulus.

Not all moduli have primitive roots. Take $m=8$ . The least residues that are relatively prime to $m=8$ are the set $\left\{1,3,5,7 \right\}$ . Note that $a^2 \equiv 1 \ (\text{mod} \ 8)$ for every $a$ in this set. Thus no number $a$ in this set can have order = $\phi(8)=4$ .

___________________________________________________________________________________________________________________

Elementary Results

One observation can be made about the above small tables for $m=11$ and $m=10$ is that all exponents for which the power of $a$ is one are the multiples of the order. We have the following theorem.

Theorem 4

$a$

$0 \le a \le m-1$

$a$

$m$

$k$

$a$

$m$

$a^n \equiv 1 \ (\text{mod} \ m)$

$n$

$k$

Proof of Theorem 4

$\Longleftarrow$
This direction is clear. If $n=q \cdot k$ for some integer $q$ , then $a^n=(a^k)^q \equiv 1 \ (\text{mod} \ m)$ .

$\Longrightarrow$
Suppose that $a^n \equiv 1 \ (\text{mod} \ m)$ . By the division algorithm, we have $n=q \cdot k+r$ for some integers $q$ and $r$ where $0 \le r <k$ . We have the following:

$a^n=(a^k)^q \cdot a^r \equiv a^r \ (\text{mod} \ m)$

Since $r<k$ and $a^r \equiv 1 \ (\text{mod} \ m)$ , it must be the case that $r=0$ , implying that $n=q \cdot k$ . $\blacksquare$

We have the following corollary.

Corollary 5

$a$

$0 \le a \le m-1$

$a$

$m$

$k$

$a$

$m$

$\phi(m)$

$k$

Another observation from the above small tables is that a primitive root, through powering, is a generator of the least residues that are relatively prime to the modulus.

Theorem 5

$a$

$0 \le a \le m-1$

$a$

$m$

The number $a$ is a primitive root modulo $m$ .
The set $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ , where each $a^j$ is considered as the least residues modulo $m$ , is precisely the set $(\mathbb{Z}_m)^*$ .

$\text{ }$

Recall that $(\mathbb{Z}_m)^*$ is the set of all $a \in \mathbb{Z}_m=\left\{0,1,2,3,\cdots,m-1 \right\}$ such that $a$ is relatively prime to $m$ .

Proof of Theorem 5

$1 \Longrightarrow 2$
Suppose that the number $a$ is a primitive root modulo $m$ . The first step in showing condition 2 is to show that the $\phi(m)$ numbers in the set $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ are distinct congruent modulo $m$ . Then it follows that their least residues modulo $m$ are distinct too.

Suppose $a^j \equiv a^i \ (\text{mod} \ m)$ where $i,j \le \phi(m)$ . We want to show that $i=j$ . Suppose $i<j$ . Then cancel out $a^i$ on both sides of the equation since $a^i$ is relatively prime to $m$ . We have $a^{j-i} \equiv 1 \ (\text{mod} \ m)$ . But $j-i<\phi(m)$ . Since $a$ is a primitive root modulo $m$ , we cannot have $a^{j-i} \equiv 1 \ (\text{mod} \ m)$ . So it must be the case that $j=i$ . So if $a^j \equiv a^i \ (\text{mod} \ m)$ , then $i=j$ . Equivalently, if $i \ne j$ , $a^j \not \equiv a^i \ (\text{mod} \ m)$ . Thus the least residues modulo $m$ of the values in $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ are distinct too.

Since $a^i$ is relatively prime to $m$ , its least residue is also relatively prime to $m$ . Now the least residues modulo $m$ of the values in $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ consist of $\phi(m)$ numbers inside $(\mathbb{Z}_m)^*$ , which is also a set of $\phi(m)$ many numbers. So the two sets must equal.

$2 \Longrightarrow 1$
We show the contrapositive of $2 \Longrightarrow 1$ . Suppose that the order of $a$ modulo $m$ is $j$ where $1 \le j<\phi(m)$ . So $a^j \equiv 1 \ (\text{mod} \ m)$ and $a^{j+1} \equiv a \ (\text{mod} \ m)$ . So $a$ and $a^{j+1}$ are two elements in the set $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ that are congruent to each other. This means that the least residues of $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ have less than $\phi(m)$ many values. In other words, the number $a$ , through powering, cannot generate all the least residues that are relatively prime to the modulus $m$ . $\blacksquare$

The following theorem and corollary give the number of primitive root modulo $m$ as long as it is known that there is a primitive root modulo $m$ .

Theorem 6

$a$

$m$

$k$

$a^k$

$m$

$k$

$\phi(m)$

Proof of Theorem 6

$\Longrightarrow$
Suppose that $k$ is not relatively prime to $\phi(m)$ . So $d=\text{GCD}(k,\phi(m))>1$ . Then we have:

$\displaystyle (a^k)^{\frac{\phi(m)}{d}}=(a^{\phi(m)})^{\frac{k}{d}} \equiv 1 \ (\text{mod} \ m)$

With $\displaystyle b=\frac{\phi(m)}{d}<\phi(m)$ and $(a^k)^b \equiv 1 \ (\text{mod} \ m)$ , it follows that $a^k$ is not a primitive root modulo $m$ . Hence the least residue of $a^k$ modulo $m$ is also not a primitive root. Thus if the least residue of $a^k$ is a primitive root modulo $m$ , it must be that $\text{GCD}(k,\phi(m))=1$ .

$\Longleftarrow$
Suppose $\text{GCD}(k,\phi(m))=1$ . Let $\alpha$ be the order of $a^k$ modulo $m$ . By the definition of order, $a^{k \cdot \alpha}=(a^k)^\alpha \equiv 1 \ (\text{mod} \ m)$ . Based on the fact that the order of $a$ modulo $m$ is $\phi(m)$ , we have $\phi(m) \ \lvert \ k \cdot \alpha$ (also using Theorem 4). Since $\text{GCD}(k,\phi(m))=1$ , it must be the case that $\phi(m) \ \lvert \ \alpha$ .

On the other hand, $(a^k)^{\phi(m)}=(a^{\phi(m)})^k \equiv 1 \ (\text{mod} \ m)$ . Using the fact that the order of $a^k$ is $\alpha$ (and using Theorem 4), $\alpha \ \lvert \ \phi(m)$ .

With $\phi(m) \ \lvert \ \alpha$ and $\alpha \ \lvert \ \phi(m)$ , it follows that $\alpha = \phi(m)$ . This implies that $a^k$ is a primitive root modulo $m$ , and so is its least residue modulo $m$ . $\blacksquare$

Corollary 7

$m$

$\phi(\phi(m))$

$m$

Proof of Corollary 7

Let $a$ be a primitive root modulo $m$ . By Theorem 6, the least residue of $a^k$ is a primitive roots modulo $m$ if and only if $k$ is relatively prime to the number $\phi(m)$ . There are precisely $\phi(\phi(m))$ many such numbers $k$ .

Furthermore, according to Theorem 5, the least residues of the values in $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ are all distinct. Thus the least residues of the powers $a^k$ for the $\phi(\phi(m))$ many $k$ are primitive roots modulo $m$ . $\blacksquare$

___________________________________________________________________________________________________________________

An Algorithm

The theorems and corollaries in this post form an elementary algorithm for finding primitive roots of a modulus (if one is known to exist). The algorithm is described in the post An elementary algorithm for finding primitive roots. An example is given in the post Finding Primitive Roots.

___________________________________________________________________________________________________________________

Euler’s phi function, part 2

Posted on September 1, 2013 by Dan Ma

This is the part 2 of an introductory discussion on Euler’s phi function. See part 1 for a background discussion on the phi function $\phi$ .

In computing modular arithmetic where the modulus is $m$ , the following two sets of integers are of interest.

$\mathbb{Z}_m=\left\{0,1,2,\cdots,m-1 \right\}$

$(\mathbb{Z}_m)^*=\left\{a \in \mathbb{Z}_m: a \text{ is relatively prime to } m \right\}$

The first set $\mathbb{Z}_m$ is a representative set under the arithmetic modulo $m$ since every integer is congruent mod $m$ to exactly one number in $\mathbb{Z}_m$ . In many settings, the only results of interest for modulo $m$ calculations are values in $\mathbb{Z}_m$ (also called least residues).

The second set $(\mathbb{Z}_m)^*$ consists of all integers in $\mathbb{Z}_m$ that are relatively prime to the modulus $m$ (as the set is defined). So any integer that is relatively prime to the modulus $m$ is congruent to exactly one number in $(\mathbb{Z}_m)^*$ . Furthermore, the set $(\mathbb{Z}_m)^*$ is closed under multiplication modulo $m$ . It is also the case that every number in $(\mathbb{Z}_m)^*$ has a multiplicative inverse modulo $m$ . If we look for numbers a where $a^n \equiv 1 \ (\text{mod} \ m)$ , we do not need to look further than the set $(\mathbb{Z}_m)^*$ . We have the following theorem.

Theorem 1

Let $a$ be an integer in $\mathbb{Z}_m$ . The following conditions are equivalent.

$\text{GCD}(a,m)=1$ .
There is a $b \in \mathbb{Z}_m$ such that $a \cdot b \equiv 1 \ (\text{mod} \ m)$ .
Some positive power of $a$ modulo $m$ is $1$ , i.e., $a^n \equiv 1 \ (\text{mod} \ m)$ for some positive integer $n$ .

$\text{ }$

The proof of Theorem 1 is found in Euler’s phi function, part 1.

Euler’s phi function $\phi(m)$ is defined to be the number of elements in the set $(\mathbb{Z}_m)^*$ . In this post, we prove two elementary properties of the function $\phi$ . We have the following two results.

Theorem 2

Let $p$ be a prime number. Let $n$ be a positive integer. Then $\phi(p^n)=p^{n-1}(p-1)$ .

Theorem 3

Let $m$ and $n$ be two positive integers that are relatively prime. Then $\phi(m n)=\phi(m) \cdot \phi(n)$ .

Example

Before proving the theorems, we work some examples. Find $\phi(299376)$ . We factor $299376$ into its prime factors.

$299376=2^4 \cdot 3^5 \cdot 7 \cdot 11$

By Theorem 3, the function $\phi$ is multiplicative among integers that are relatively prime. Now we have $\phi(299376)=\phi(2^4) \cdot \phi(3^5) \cdot \phi(7) \cdot \phi(11)$ . Applying Theorem 2, we have:

$\displaystyle \begin{aligned} \phi(299376)&=\phi(2^4) \cdot \phi(3^5) \cdot \phi(7) \cdot \phi(11) \\&=2^3 (2-1) \cdot 3^4 (3-1) \cdot (7-1) \cdot (11-1) \\&=8 \cdot 162 \cdot 6 \cdot 10 \\&=77760 \end{aligned}$

Proof of Theorem 2

Among the integers $1,2,3,\cdots, p^n-1,p^n$ , the only ones that are not relatively prime to $p^n$ are multiples of $p$ (since $p$ is a prime number). There are $p^{n-1}$ many multiples of $p$ . They are:

$p, 2 \cdot p, 3 \cdot p, \cdots, p^{n-1} \cdot p$

Thus among the integers $1,2,3,\cdots, p^n-1,p^n$ , the number of integers that are relatively prime to $p^n$ must be $\phi(p^n)=p^n-p^{n-1}=p^{n-1}(p-1)$ . $\blacksquare$

Lemma 4 will be helpful in proving Theorem 3.

Lemma 4

If $a$ is relatively prime to $m$ and $a$ is relatively prime to $n$ , then $a$ is relatively prime to $mn$ .

Proof of Lemma 4

Since $a$ is relatively prime to $m$ , their greatest common divisor is one. Using the extended Euclidean algorithm, $ax+my=1$ for some integers $x$ and $y$ . Since $a$ is relatively prime to $n$ , $ah+nk=1$ for some integers $h$ and $k$ . Multiplying these two equations, we get:

$(ax+my) \cdot (ah+nk)=a(xah+xnk+myh)+mn(yk)=1$

The above equation means that $a(xah+xnk+myh) \equiv 1 \ (\text{mod} \ mn)$ . This shows that $xah+xnk+myh$ is the multiplicative inverse of $a$ modulo $mn$ . By Theorem 1, $a$ is relatively prime to $mn$ . $\blacksquare$

Proof of Theorem 3

Suppose $m$ and $n$ are relatively prime. We show that among the integers $1,2,3,\cdots,mn-1,mn$ , there are exactly $\phi(m) \cdot \phi(n)$ many numbers that are relatively prime to $mn$ . To facilitate the argument, we enumerate the integers $1,2,3,\cdots,mn-1,mn$ as in the following matrix.

$\displaystyle \begin{bmatrix} 1&\text{ }&1 \cdot m+1&\text{ }&2 \cdot m+1&\text{ }&\cdots&k \cdot m+1&\cdots&(n-1) \cdot m+1 \\\text{ }&\text{ }&\text{ } \\2&\text{ }&1 \cdot m+2&\text{ }&2 \cdot m+2&\text{ }&\cdots&k \cdot m+2&\cdots&(n-1) \cdot m+2 \\\text{ }&\text{ }&\text{ } \\3&\text{ }&1 \cdot m+3&\text{ }&2 \cdot m+3&\text{ }&\cdots&k \cdot m+3&\cdots&(n-1) \cdot m+3 \\\text{ }&\text{ }&\text{ } \\\cdots&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\text{ }&\cdots&\text{ }&\cdots \\\text{ }&\text{ }&\text{ } \\h&\text{ }&1 \cdot m+h&\text{ }&2 \cdot m+h&\text{ }&\cdots&k \cdot m+h&\cdots&(n-1) \cdot m+h \\\text{ }&\text{ }&\text{ } \\\cdots&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\text{ }&\cdots&\text{ }&\cdots \\\text{ }&\text{ }&\text{ } \\m&\text{ }&1 \cdot m+m&\text{ }&2 \cdot m+m&\text{ }&\cdots&k \cdot m+m&\cdots&(n-1) \cdot m+m \end{bmatrix}$

There are $m$ rows and $n$ columns in the matrix. The first observation is that if the first number of a row is $h$ and if $h$ and $m$ are not relatively prime, then there is $d>1$ that is a common divisor of $h$ and $m$ . Then $d$ also divides any other number on that row. So if the first number of a row is $h$ and if $h$ and $m$ are not relatively prime, then any number on the $h^{th}$ row is not relatively prime to $m$ , hence is not relatively prime to $mn$ .

Based on the above observation, to look for numbers that are relatively prime to $mn$ , we only need to look at rows where the first number $h$ is relatively prime to $m$ . There are exactly $\phi(m)$ many such rows.

We claim that in each of these $\phi(m)$ rows, there are exactly $\phi(n)$ many numbers that are relatively prime to $mn$ . It follows that there are exactly $\phi(m) \cdot \phi(n)$ many numbers in the entire matrix that are relatively prime to $mn$ . Thus the theorem will be established.

To establish the claim in the above paragraph, consider one such row where the first number $h$ is relatively prime to $m$ . First observe that the $n$ numbers in the $h^{th}$ row are distinct congruent modulo $m$ . Suppose that $k \cdot m+h \equiv j \cdot m+h \ (\text{mod} \ n)$ . Cancel out $h$ , we have $k \cdot m \equiv j \cdot m \ (\text{mod} \ n)$ . Since $m$ and $n$ are relatively prime, we can cancel out $m$ and obtain $k \equiv j \ (\text{mod} \ n)$ . Since both $k$ and $j$ are less than $n$ , it must be that $k=j$ . So if $k \ne j$ , $k \cdot m+h \not \equiv j \cdot m+h \ (\text{mod} \ n)$ .

Based on the observation in the above paragraph, the least residues modulo $n$ of the numbers in the $h^{th}$ row must be the set $\left\{0,1,2,\cdots,n \right\}$ . This follows from the fact that the $n$ numbers in the $h^{th}$ row are distinct congruent modulo $n$ . Hence their least residues must be $n$ distinct numbers too.

So in terms of congruence modulo $n$ , the $h^{th}$ row in the matrix is a mirror image of the least resides $\left\{0,1,2,\cdots,n \right\}$ . There are exactly $\phi(n)$ many least residues that are relatively prime to $n$ . Likewise, there are exactly $\phi(n)$ many numbers in the $h^{th}$ row that are relatively prime to $n$ . Furthermore, every number in the $h^{th}$ row is relatively prime to $m$ . By Lemma 4, there are exactly $\phi(n)$ many numbers in the $h^{th}$ row that are relatively prime to $mn$ . Thus the above claim is established. It follows that the theorem is established. $\blacksquare$

___________________________________________________________________________________________________________________

Exploring Number Theory

A blog on elementary number theory

Tag Archives: Number Theory

More about checking for primitive roots

Quadratic Residues

Solving Quadratic Congruences

Euler’s Criterion

Two Proofs of Wilson’s Theorem

Primitive roots of prime moduli

An elementary algorithm for finding primitive roots

Finding Primitive Roots

Defining Primitive Root

Euler’s phi function, part 2