5 Primitive Roots Modulo m.

Chapter 5
Primitive Roots Modulo $m$ .

5.1 Exponent of an Integer Modulo $m$

Let

a_{1}, a_{2}, \dots, a_{φ (m)}

(A)

be the set of $φ (m)$ positive integers not greater than $m$ and prime to $m$ ; and let $a$ denote any integer of the set (A). Now any positive integral power of $a$ is prime to $m$ and hence is congruent modulo $m$ to a number of the set (A). Hence, among all the powers of a there must be two, say $a^{n}$ and $a^{ν}$ , $n > ν$ , which, are congruent to the same integer of the set (A). These two powers are then congruent to each other; that is,

a^{n} \equiv a^{ν} mod m

Since $a^{ν}$ is prime to $m$ the members of this congruence may be divided by $a^{ν}$ . Thus we have

a^{n - ν} \equiv 1 mod m .

That is, among the powers of $a$ there is one at least which is congruent to $1$ modulo $m$ .

Now, in the set of all powers of $a$ which are congruent to $1$ modulo $m$ there is one in which the exponent is less than in any other of the set. Let the exponent of this power be $d$ , so that $a^{d}$ is the lowest power of $a$ such that

a^{d} \equiv 1 mod m .

(1)

We shall now show that if $a^{α} \equiv 1 mod m$ , then $α$ is a multiple of $d$ . Let us write

\begin{matrix} α = d δ + β, 0 ≦ β < d . \end{matrix}

Then

\begin{matrix} a^{α} \equiv 1 mod m, & (2) \\ a^{d δ} \equiv 1 mod m, & (3) \end{matrix}

the last congruence being obtained by raising (1) to the power $δ$ . From (3) we have

\begin{matrix} a^{d δ + β} \equiv a^{β} mod m; \end{matrix}

\begin{matrix} a^{β} \equiv 1 mod m . \end{matrix}

Hence $β = 0$ , for otherwise $d$ is not the exponent of the lowest power of $a$ which is congruent to 1 modulo $m$ . Hence $d$ is a divisor of $α$ .

These results may be stated as follows:

I. If $m$ is any integer and $a$ is any integer prime to $m$ , then there exists an integer $d$ such that

\begin{matrix} a^{d} \equiv 1 mod m \end{matrix}

while there is no integer $β$ less than $d$ for which

\begin{matrix} a^{β} \equiv 1 mod m . \end{matrix}

Further, a necessary and suﬃcient condition that

\begin{matrix} a^{ν} \equiv 1 mod m \end{matrix}

is that $ν$ is a multiple of $d$ .

DEFINITION. The integer $d$ which is thus uniquely determined when the two relatively prime integers $a$ and $m$ are given is called the exponent of $a$ modulo $m$ . Also, $d$ is said to be the exponent to which $a$ belongs modulo $m$ .

Now, in every case we have

a^{φ (m)} \equiv 1, a^{λ (m)} \equiv 1 mod m,

if $a$ and $m$ are relatively prime. Hence from the preceding theorem we have at once the following:

II. The exponent $d$ to which $a$ belongs modulo $m$ is a divisor of both $φ (m)$ and $λ (m)$ .

5.2 Another Proof of Fermat’s General Theorem

In this section we shall give an independent proof of the theorem that the exponent $d$ of $a$ modulo $m$ is a divisor of $φ (m)$ ; from this result we have obviously a new proof of Fermat’s theorem itself.

We retain the notation of the preceding section. We shall ﬁrst prove the following theorem:

I. The numbers

1, a, a^{2}, \dots, a^{a - 1}

(A)

are incongruent each to each modulo $m$ .

For, if $a^{α} \equiv a^{β} mod m$ , where $0 ≦ α < d$ and $0 ≦ β < d$ , $α > β$ , we have $a^{α - β} \equiv 1 mod m$ , so that $d$ is not the exponent to which $a$ belongs modulo $m$ , contrary to hypothesis.

Now any number of the set (A) is congruent to some number of the set

a_{1}, a_{2}, \dots, a_{φ (m)} .

(B)

Let us undertake to separate the numbers (B) into classes after the following manner: Let the ﬁrst class consist of the numbers

α_{1}, α_{2}, \dots, α_{a - 1},

(I)

where $α_{i}$ is the number of the set (B) to which $a^{i}$ is congruent modulo $m$ .

If the class (I) does not contain all the numbers of the set (B), let $a_{i}$ be any number of the set (B) not contained in (I) and form the following set of numbers:

α_{0} a_{i}, α_{1} a_{i}, α_{2} a_{i}, \dots, α_{d - 1} a_{i} .

(II’)

We shall now show that no number of this set is congruent to a number of class (I). For, if so, we should have a congruence of the form

\begin{matrix} a_{i} a_{j} \equiv a_{k} mod m; \end{matrix}

hence

\begin{matrix} a_{i} a^{j} \equiv a^{k} mod m, \end{matrix}

so that

\begin{matrix} a_{i} a^{d} \equiv a^{k + d - j} mod m; \end{matrix}

\begin{matrix} a_{i} \equiv a^{k + d - j} mod m, \end{matrix}

so that $a_{i}$ would belong to the set (I) contrary to hypothesis.

Now the numbers of the set (II $'$ ) are all congruent to numbers of the set (B); and no two are congruent to the same number of this set. For, if so, we should have two numbers of (II’) congruent; that is, $α_{k} a_{i} \equiv α_{j} a_{i} mod m,$ or $α_{k} \equiv α_{j} mod m;$ and this we have seen to be impossible.

Now let the numbers of the set (B) to which the numbers of the set (II’) are congruent be in order the following:

β_{0}, β_{1}, β_{2}, \dots, β_{d - 1} .

(II)

These numbers constitute our class (II).

If classes (I) and (II) do not contain all the numbers of the set (B), let $a_{j}$ be a number of the set ( $B$ ) not contained in either of the classes (I) and (II): and form the set of numbers

α_{0} a_{j}, α_{1} a_{j}, α_{2} a_{j}, \dots, α_{d - 1} a_{j} .

(III’)

Just as in the preceding case it may be shown that no number of this set is congruent to a number of class (I) and that the numbers of (III’) are incongruent each to each. We shall also show that no number of (III’) is congruent to a number of class (II). For, if so, we should have $a_{k} a_{j} \equiv β_{l} mod m$ . Hence $a^{k} a_{j} \equiv a^{l} a_{i} mod m$ ; or $a_{j} \equiv a^{l + d - k} mod m$ , from which it follows that $a_{j}$ is of class (II), contrary to hypothesis.

Now let the numbers of the set (B) to which the numbers of the set (III’) are congruent be in order the following:

γ_{0}, γ_{1}, γ_{2}, \dots, γ_{d - 1} .

(III)

These numbers form our class (III).

It is now evident that the process may be continued until all the numbers of the set (B) have been separated into classes, each class containing $d$ integers, thus:

\begin{matrix} (I) & α_{0}, & α_{1}, & α_{2}, & \dots, & α_{d - 1}, \\ (II) & β_{0}, & β_{1}, & β_{2}, & \dots, & β_{d - 1}, \\ (III) & γ_{0}, & γ_{1}, & γ_{2}, & \dots, & γ_{d - 1}, \\ . . . & . . . & . . . & . . & . . . . . \\ () & λ_{0}, & λ_{1}, & λ_{2}, & \dots, & λ_{d - 1} . \end{matrix}

The set (B), which consists of $φ (m)$ integers, has thus been separated into classes, each class containing $d$ integers. Hence we conclude that $d$ is a divisor of $φ (m)$ . Thus we have a second proof of the theorem:

II. If $a$ and $m$ are any two relatively prime integers and $d$ is the exponent to which $a$ belongs modulo $m$ , then $d$ is a divisor of $φ (m)$ .

In our classiﬁcation of the numbers (B) into the rectangular array above we have proved much more than theorem II; in fact, theorem II is to be regarded as one only of the consequences of the more general result contained in the array.

If we raise each member of the congruence

a^{d} \equiv 1 mod m

to the (integral) power $φ (m) / d$ , the preceding theorem leads immediately to an independent proof of Fermat’s general theorem.

5.3 Deﬁnition of Primitive Roots

DEFINITION. Let $a$ and $m$ be two relatively prime integers. If the exponent to which $a$ belongs modulo $m$ is $φ (m)$ , $a$ is said to be a primitive root modulo $m$ (or a primitive root of $m$ ).

In a previous chapter we saw that the congruence

a^{λ (m)} \equiv 1 mod m

is veriﬁed by every pair of relatively prime integers $a$ and $m$ . Hence, primitive roots can exist only for such a modulus $m$ as satisﬁes the equation

φ (m) = λ (m) .

(1)

We shall show later that this is also suﬃcient for the existence of primitive roots.

From the relation which exists in general between the $φ$ -function and the $λ$ -function in virtue of the deﬁnition of the latter, it follows that (1) can be satisﬁed only when $m$ is a prime power or is twice an odd prime power.

Suppose ﬁrst that $m$ is a power of $2$ , say $m = 2^{α}$ . Then (1) is satisﬁed only if $α = 0, 1, 2$ . For $α = 0$ or $1$ , $1$ itself is a primitive root. For $α = 2$ , $3$ is a primitive root. We have therefore left to examine only the cases

m = p^{α}, m = 2 p^{α}

where $p$ is an odd prime number. The detailed study of these cases follows in the next sections.

5.4 Primitive roots modulo $p$ .

We have seen that if $p$ is a prime number and $d$ is the exponent to which $a$ belongs modulo $p$ , then $d$ is a divisor of $φ (p) = p - 1$ . Now, let

\begin{matrix} d_{1}, d_{2}, d_{3}, \dots, d_{r} \end{matrix}

be all the divisors of $p - 1$ and let $ψ (d_{i})$ denote the number of integers of the set

\begin{matrix} 1, 2, 3, \dots, p - 1 \end{matrix}

which belong to the exponent $d_{i}$ . If there is no integer of the set belonging to this exponent, then $ψ (d_{i}) = 0$ .

Evidently every integer of the set belongs to some one and only one of the exponents $d_{1}, d_{2}, \dots, d_{r}$ . Hence we have the relation

\begin{matrix} ψ (d_{1}) + ψ (d_{2}) + \dots + ψ (d_{r}) = p - 1 . & (1) \end{matrix}

But

\begin{matrix} φ (d_{1}) + φ (d_{2}) + \dots + φ (d_{r}) = p - 1 . & (2) \end{matrix}

If then we can show that

ψ (d_{i}) ≦ φ (d_{i})

(3)

for $i = 1, 2, \dots, r$ , it will follow from a comparison of (1) and (2) that

\begin{matrix} ψ (d_{i}) = φ (d_{i}) . \end{matrix}

Accordingly, we shall examine into the truth of (3).

Now the congruence

x^{d_{i}} \equiv 1 mod p

(4)

has not more than $d_{i}$ roots. If no root of this congruence belongs to the exponent $d_{i}$ , then if $ψ (d_{i}) = 0$ and therefore in this case we have $ψ (d_{i}) < φ (d_{i})$ . On the other hand if $a$ is a root of (4) belonging to the exponent $d_{i}$ , then

a, a^{2}, a^{3}, \dots, a^{d_{i}}

(5)

are a set of $d_{i}$ incongruent roots of (4); and hence they are the complete set of roots of (4).

But it is easy to see that $a^{k}$ does or does not belong to the exponent $d_{i}$ according as $k$ is or is not prime to $d_{i}$ ; for, if $a^{k}$ belongs to the exponent $t$ , then $t$ is the least integer such that $k t$ is a multiple of $d_{i}$ . Consequently the number of roots in the set (5) belonging to the exponent $d_{i}$ is $φ (d_{i})$ . That is, in this case $ψ (d_{i}) = φ (d_{i})$ . Hence in general $ψ (d_{i}) ≦ φ (d_{i})$ Therefore from (1) and (2) we conclude that

ψ (d_{i}) = φ (d_{i}), i = 1, 2, \dots, r .

The result thus obtained may be stated in the form of the following theorem:

I. If $p$ is a prime number and $d$ is any divisor of $p - 1$ , then the number of integers belonging to the exponent $d$ modulo $p$ is $φ (d)$ .

In particular:

II. There exist primitive roots modulo $p$ and their number is $ψ (p - i)$ .

5.5 Primitive Roots Modulo $p^{α}$ , $p$ an Odd Prime

In proving that there exist primitive roots modulo $p^{α}$ , where $p$ is an odd prime and $α > 1$ , we shall need the following theorem:

I. There always exists a primitive root $γ$ modulo $p$ for which $γ^{p - 1}$ is not divisible by $p^{2}$ .

Let $g$ be any primitive root modulo $p$ . If $g^{p - 1}$ is not divisible by $p^{2}$ our theorem is veriﬁed. Then suppose that $g^{p - 1} - 1$ is divisible by $p^{2}$ , so that we have

\begin{matrix} g^{p - 1} - 1 = k p^{2} \end{matrix}

where $k$ is an integer. Then put

\begin{matrix} γ = g + x p \end{matrix}

where $x$ is an integer. Then $γ = g mod p$ , and hence

\begin{matrix} γ^{h} \equiv g^{h} mod p; \end{matrix}

whence we conclude that $γ$ is a primitive root modulo $p$ . But

\begin{array}{l} γ^{p - 1} - 1 & = g^{p - 1} - 1 + \frac{p - 1}{1!} g^{p - 2} x p + \frac{(p - 1) (p - 2)}{2!} g^{p - 3} x^{2} p^{2} + \dots \\ = p (k p + \frac{p - 1}{1!} g^{p - 2} x + \frac{(p - 1) (p - 2)}{2!} g^{p - 3} x^{2} p + \dots) . \end{array}

Hence

γ^{p - 1} - 1 \equiv p (- g^{p - 2} x) mod p^{2} .

Therefore it is evident that $x$ can be so chosen that $γ^{p - 1} - 1$ is not divisible by $p^{2}$ . Hence there exists a primitive root $γ$ modulo $p$ such that $γ^{p - 1} - 1$ is not divisible by $p^{2}$ . Q. E. D.

We shall now prove that this integer $γ$ is a primitive root modulo $p^{α}$ , where $α$ is any positive integer.

γ^{k} \equiv 1 mod p .

then $k$ is a multiple of $p - 1$ , since $γ$ is a primitive root modulo $p$ . Hence, if

γ^{k} \equiv 1 mod p^{α},

then $k$ is a multiple of $p - 1$ .

Now, write

γ^{p - 1} = 1 + h p .

Since $γ^{p - 1}$ is not divisible by $p^{2}$ , it follows that $h$ is prime to $p$ . If we raise each member of this equation to the power $β p^{α - 2}$ , $α \overset{=}{>} 2$ , we have

γ^{β p^{α - 2} (p - 1)} = 1 + β p^{α - 1} h + p^{α} I,

where $I$ is an integer. Then if

γ^{β p^{α - 2} (p - 1)} \equiv 1 mod p^{α},

$β$ must be divisible by $p$ . Therefore the exponent of the lowest power of $γ$ which is congruent to $1$ modulo $p^{α}$ is divisible by $p^{α - 1}$ . But we have seen that this exponent is also divisible by $p - 1$ . Hence the exponent of $γ$ modulo $p^{α}$ is $p^{α - 1} (p - 1)$ since $φ (p^{α}) = p^{α - 1} (p - 1)$ . That is, $γ$ is a primitive root modulo $p^{α}$ .

It is easy to see that no two numbers of the set

γ, γ^{2}, γ^{3}, \dots, γ^{p^{α - 1} (p - 1)}

(A)

are congruent modulo $p^{α}$ ; for, if so, $γ$ would belong modulo $p^{α}$ to an exponent less than $p^{α - 1} (p - 1)$ and would therefore not be a primitive root modulo $p^{α}$ . Now every number in the set (A) is prime to $p^{α}$ ; their number is $φ (p^{α}) = p^{α - 1} (p - 1)$ . Hence the numbers of the set (A) are congruent in some order to the numbers of the set (B):

a_{1}, a_{2}, a_{3}, \dots, a_{p^{α - 1} (p - 1)},

(B)

where the integers (B) are the positive integers less than $p^{α}$ and prime to $p^{α}$ .

But any number of the set (B) is a solution of the congruence

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

(1)

Further, every solution of this congruence is prime to $p^{α}$ . Hence the integers (B) are a complete set of solutions of (1). Therefore the integers (A) are a complete set of solutions of (1). But it is easy to see that an integer $γ^{k}$ of the set (A) is or is not a primitive root modulo $p^{α}$ according as $k$ is or is not prime to $p^{α - 1} (p - 1)$ . Hence the number of primitive roots modulo $p^{α}$ is $φ {p^{α - 1} (p - 1)} .$

The results thus obtained may be stated as follows:

II. If $p$ is any odd prime number and $α$ is any positive integer, then there exist primitive roots modulo $p^{α}$ and their number is $φ {φ (p^{α})}$ .

5.6 Primitive Roots Modulo $2 p^{α}$ , $p$ an Odd Prime

In this section we shall prove the following theorem:

If $p$ is any odd prime number and $α$ is any positive integer, then there exist primitive roots modulo $2 p^{α}$ and their number is $φ {φ (2 p^{α})} .$

Since $2 p^{α}$ is even it follows that every primitive root modulo $2 p^{α}$ is an odd number. Any odd primitive root modulo $p^{α}$ is obviously a primitive root modulo $2 p^{α}$ . Again, if $γ$ is an even primitive root modulo $p^{α}$ then $γ + p^{α}$ is a primitive root modulo $2 p^{α}$ . It is evident that these two classes contain (without repetition) all the primitive roots modulo $2 p^{α}$ . Hence the theorem follows as stated above.

5.7 Recapitulation

The results which we have obtained in §§5.3–5.6 inclusive may be gathered into the following theorem:

In order that there shall exist primitive roots modulo $m$ , it is necessary and suﬃcient that $m$ shall have one of the values

m = 1, 2, 4, p^{α}, 2 p^{α}

where $p$ is an odd prime and $α$ is a positive integer.

If $m$ has one of these values then the number of primitive roots modulo $m$ is $φ {φ (m)}$ .

5.8 Primitive $λ$ -roots

In the preceding sections of this chapter we have developed the theory of primitive roots in the way in which it is usually presented. But if one approaches the subject from a more general point of view the results which may be obtained are more general and at the same time more elegant. It is our purpose in this section to develop the more general theory.

We have seen that if $a$ and $m$ are any two relatively prime positive integers, then

a^{λ (m)} \equiv 1 mod m .

Consequently there is no integer belonging modulo $m$ to an exponent greater than $λ (m)$ . It is natural to enquire if there are any integers $a$ which belong to the exponent $λ (m)$ . It turns out that the question is to be answered in the aﬃrmative, as we shall show. Accordingly, we introduce the following deﬁnition:

DEFINITION. If $a^{λ (m)}$ is the lowest power of $a$ which is congruent to $1$ modulo $m$ , $a$ is said to be a primitive $λ$ -root modulo $m$ . We shall also say that it is a primitive $λ$ -root of the congruence $x^{λ (m)} = 1 mod m$ . To distinguish we may speak of the usual primitive root as a primitive $φ$ -root modulo $m$ .

From the theory of primitive $φ$ -roots already developed it follows that primitive $λ$ -roots always exist when $m$ is a power of any odd prime, and also when $m = 1, 2, 4$ ; for, for such values of $m$ we have $λ (m) = φ (m)$ .

We shall next show that primitive $λ$ -roots exist when $m = 2^{α}$ , $a > 2$ , by showing that 5 is such a root. It is necessary and suﬃcient to prove that $5$ belongs modulo $2^{α}$ to the exponent $2^{α - 2} = λ (2^{α})$ . Let $d$ be the exponent to which $5$ belongs modulo $2^{α}$ . Then from theorem II of §5.1 it follows that $d$ is a divisor of $2^{α - 2} = λ (2^{α})$ . Hence if $d$ is diﬀerent from $2^{α - 2}$ it is $2^{α - 3}$ or is a divisor of $2^{α - 3}$ . Hence if we can show that $5^{2^{α - 3}}$ is not congruent to $1$ modulo $2^{α}$ we will have proved that $5$ belongs to the exponent $2^{α - 2}$ . But, clearly,

\begin{matrix} 5^{2^{α - 3}} = {(1 + 2^{2})}^{2^{α - 3}} = 1 + 2^{α - 1} + I \cdot 2^{α}, \end{matrix}

where $I$ is an integer. Hence

\begin{matrix} 5^{2^{α - 3}} ≢ 1 mod 2^{α} . \end{matrix}

Hence 5 belongs modulo $2^{α}$ to the exponent $λ (2^{α})$ .

By means of these special results we are now in position to prove readily the following general theorem which includes them as special cases:

I. For every congruence of the form

\begin{matrix} x^{λ (m)} \equiv 1 mod m \end{matrix}

a solution $g$ exists which is a primitive $λ$ -root, and for any such solution $g$ there are $φ {λ (m)}$ primitive roots congruent to powers of $g$ .

If any primitive $λ$ -root $g$ exists, $g^{ν}$ is or is not a primitive $λ$ -root according as $ν$ is or is not prime to $λ (m)$ ; and therefore the number of primitive $λ$ -roots which are congruent to powers of any such root $g$ is $φ {λ (m)}$ .

The existence of a primitive $λ$ -root in every case may easily be shown by induction. In case $m$ is a power of a prime the theorem has already been established. We will suppose that it is true when $m$ is the product of powers of $r$ diﬀerent primes and show that it is true when $m$ is the product of powers of $r + 1$ diﬀerent primes; from this will follow the theorem in general.

Put $m = p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{r}^{α_{r}} p_{r + 1}^{α_{r + 1}}, n = p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{r}^{α_{r}}$ , and let $h$ be a primitive $λ$ -root of

x^{λ (n)} \equiv 1 mod n .

(1)

Then

h + n y

is a form of the same root if $y$ is an integer.

Likewise, if $c$ is any primitive $λ$ -root of

x^{λ} (p_{r + 1}^{α_{r + 1}}) \equiv 1 mod p_{r + 1}^{α_{r + 1}}

(2)

a form of this root is

c + p_{r + 1}^{α_{r + 1}} z

where $z$ is any integer.

Now, if $y$ and $z$ can be chosen so that

h + n y = c + p_{r + 1}^{α_{r + 1}} z

the number in either member of this equation will be a common primitive $λ$ -root of congruences (1) and (2); that is, a common primitive $λ$ -root of the two congruences may always be obtained provided that the equation

p_{1}^{α_{1}} \dots p_{r}^{α_{r}} y - p_{r + 1}^{α_{r + 1}} z = c - h

has always a solution in which $y$ and $z$ are integers. That this equation has such a solution follows readily from theorem III of §1.9; for, if $c - h$ is replaced by $1$ , the new equation has a solution $\bar{y}$ , $\bar{z}$ ; and therefore for $y$ and $z$ we may take $y = \bar{y} (c - h)$ , $z = \bar{z} (c - h)$ .

Now let $g$ be a common primitive $λ$ -root of congruences (1) and (2) and write

g^{ν} \equiv 1 mod m,

where $ν$ is to be the smallest exponent for which the congruence is true. Since $g$ is a primitive $λ$ -root of (1) $ν$ is a multiple of $λ (p_{1}^{α_{1}} \dots p_{r}^{α_{r}})$ . Since $g$ is a primitive $λ$ -root of (2) $ν$ is a multiple of $λ (p_{r + 1}^{α_{r + 1}})$ . Hence it is a multiple of $λ (m)$ . But $g^{λ (m)} \equiv 1 mod m$ ; therefore $ν = λ (m)$ . That is, $g$ is a primitive $λ$ -root modulo $m$ .

The theorem as stated now follows at once by induction.

There is nothing in the preceding argument to indicate that the primitive $λ$ -roots modulo $m$ are all in a single set obtained by taking powers of some root $g$ ; in fact it is not in general true when $m$ contains more than one prime factor.

By taking powers of a primitive $λ$ -root $g$ modulo $m$ one obtains $φ {λ (m)}$ diﬀerent primitive $λ$ -roots modulo $m$ . It is evident that if $γ$ is any one of these primitive $λ$ -roots, then the same set is obtained again by taking the powers of $γ$ . We may say then that the set thus obtained is the set belonging to $g$ .

II. If $λ (m) > 2$ the product of the $φ {λ (m)}$ primitive $λ$ -roots in the set belonging to any primitive $λ$ -root $g$ is congruent to $1$ modulo $m$ .

These primitive $λ$ -roots are

\begin{matrix} g, g^{c_{1}}, g^{c_{2}}, \dots, g^{c_{μ}} \end{matrix}

where

\begin{matrix} 1, c_{1}, c_{2}, \dots, c_{μ} \end{matrix}

are the integers less than $λ (m)$ and prime to $λ (m)$ . If any one of these is $c$ another is $λ (m) - c$ , since $λ (m) > 2$ . Hence

\begin{matrix} 1 + c_{1} + c_{2} + \dots + c_{μ} \equiv 0 mod λ (m) . \end{matrix}

Therefore

\begin{matrix} g^{1 + c_{1} + c_{2} + \dots + c_{μ}} \equiv 1 mod m . \end{matrix}

From this the theorem follows.

COROLLARY.The product of all the primitive $λ$ -roots modulo $m$ is congruent to $1$ modulo $m$ when $λ (m) > 2$ .

EXERCISES

1.: If $x_{1}$ is the largest value of $x$ satisfying the equation $λ (x) = a$ , where $a$ is a given integer, then any solution $x_{2}$ of the equation is a factor of $x_{1}$ .
2*.: Obtain an eﬀective rule for solving the equation $λ (x) = a$ .
3*.: Obtain an eﬀective rule for solving the equation $φ (x) = a$ .
4.: A necessary and suﬃcient condition that $a^{P - 1} \equiv 1 mod P$ for every integer $a$ prime to $P$ is that $P \equiv 1 mod λ (P)$ .
5.: If $a^{P - 1} \equiv 1 mod P$ for every a prime to $P$ , then (1) $P$ does not contain a square factor other than $1$ , (2) $P$ either is prime or contains at least three diﬀerent prime factors.
6.: Let $p$ be a prime number. If $a$ is a root of the congruence $x^{q} \equiv 1 mod p$ and $α$ is a root of the congruence $x^{δ} \equiv 1 mod p$ , then $a α$ is a root of the congruence $x^{d δ} \equiv 1 mod p$ . If $a$ is a primitive root of the ﬁrst congruence and $α$ of the second and if $d$ and $δ$ are relatively prime, then $a α$ is a primitive root of the congruence $x^{d δ} \equiv 1 mod p$ .

ptail

top

Chapter 5Primitive Roots Modulo m.

5.1 Exponent of an Integer Modulo m

5.2 Another Proof of Fermat’s General Theorem

5.3 Deﬁnition of Primitive Roots

5.4 Primitive roots modulo p.

5.5 Primitive Roots Modulo pα, p an Odd Prime

5.6 Primitive Roots Modulo 2pα, p an Odd Prime