Section 10.4 Prime Numbers Have Primitive Roots
We use many of the same techniques and ideas in by proving that every prime numberxxxxxxxxxx
L=[(p,primitive_root(p)) for p in prime_range(100)]
for item in L:
print("A primitive root of %s is %s"%(item[0],item[1]))
Theorem 10.4.1. Primitive Roots Exist for Primes.
Every prime has a primitive root. In other words, the order
Proof.
Below, we will actually prove the stronger Claim 10.4.4, which states that the number of elements of order \(d\) (a positive divisor of \(n\)) is \(\phi(d)\text{.}\) Naturally this will be non-zero for \(d=p-1\text{,}\) which proves the theorem.
Example 10.4.2.
First, it is useful to see what these sets look like for two examples β one where we know we have a primitive root, and one where we know we don't.
Assuming you are online, evaluate the next cell to get the list of sets of different order elements for
xxxxxxxxxx
for d in divisors(40):
L=[]
for a in range(1,41):
if mod(a,41).multiplicative_order()==d:
L.append(a)
pretty_print(html(r"There are $%s=\phi(%s)$ elements of order $%s$ - "%(len(L),d,d)+str(L)))
But here is the list of sets for
xxxxxxxxxx
for d in divisors(euler_phi(32)):
L=[]
for a in range(1,32):
if mod(a,2)==1 and mod(a,32).multiplicative_order()==d:
L.append(a)
if len(L)==euler_phi(d):
pretty_print(html(r"There are $%s=\phi(%s)$ elements of order $%s$ - "%(len(L),d,d)+str(L)))
else:
pretty_print(html(r"There are $%s\neq\phi(%s)$ elements of order $%s$ - "%(len(L),d,d)+str(L)))
As always, doing an entire example manually is very instructive too.
Question 10.4.3.
Let
Can you see why the inverse of an even power of a primitive root is also an even power?
Do you think an odd power (greater than one) of a primitive root
could be a different primitive root Why or why not? What about even powers of a given primitive root β could they be primitive roots, at least in principle?
Claim 10.4.4.
If
Proof.
Assume that \(p\) is prime. For any of the divisors \(d\) of \(p-1\) (not just \(p-1\) itself), consider the possible number of elements of \(U_p\) with that order,
By Lemma 10.3.5, this quantity is clearly between zero and \(\phi(d)\text{.}\) On the other hand, by Lemma 10.3.4, once we find one \(a\) with order \(d\text{,}\) then all the powers of \(a\) coprime to \(d\) also have that order (and are distinct), so there are at least \(\phi(d)\) of them.
In particular, the cardinality of the set of elements of \(U_p\) of order \(d\) is always either zero or \(\phi(d)>0\text{,}\) so the entire proof boils down to finding at least one element \(a\) with order \(d\) for each potential order \(d\text{.}\) (The reason we just need to consider \(d\mid p-1\) is Theorem 8.3.12 that the order of any element of a group divides the order of the group, so the only possible orders of elements in \(U_p\) are positive divisors of \(p-1\text{.}\))
Suppose that at least one of the sets for some divisor \(d'\) (such as the set of primitive roots, if \(d'=p-1\)) is empty. Then on the one hand, every element of \(U_p\) has some order, so
On the other hand, Fact 9.5.4 with \(n=p-1\) tells us that
Combining these two inequalities yields \(p-1\lt p-1\text{,}\) an absurdity.
xxxxxxxxxx
def _(n=(25,[0..100])):
for d in divisors(euler_phi(n)):
L=[]
for a in range(1,n):
if gcd(a,n)==1 and mod(a,n).multiplicative_order()==d:
L.append(a)
if len(L)==euler_phi(d):
pretty_print(html(r"There are $%s=\phi(%s)$ elements of order $%s$ - "%(len(L),d,d)+str(L)))
else:
pretty_print(html(r"There are $%s\neq\phi(%s)$ elements of order $%s$ - "%(len(L),d,d)+str(L)))