Section 10.3 When Does a Primitive Root Exist?
ΒΆFact 10.3.1.
There is no primitive root for n=12\text{.}
Proof.
See Exercise 10.6.4.
Subsection 10.3.1 Primitive roots of powers of two
ΒΆWe'll start this investigation by proving that most powers of 2 do not have primitive roots. The following should give you an error.xxxxxxxxxx
power=25
primitive_root(2^power)
Proposition 10.3.2.
For k> 2\text{,} there are no elements of U_{2^k} that have order \phi(2^k)=2^{k-1}\text{,} because the highest order they can have is 2^{k-2}\text{.}
Proof.
Assume \(n=2^k\) for \(k>2\text{.}\) (For \(n=2\) and \(n=4\text{,}\) there are primitive roots β check this if you haven't already). In Exercise 10.6.3 we show that \(n=8\) does not have a primitive root. In particular, each element of \(U_8\) has order \(2^{3-2}=2\text{,}\) so that \(a^2\equiv 1\) (mod \(8\)) for all \(a\in U_8\text{.}\)
Think of \(n=8=2^3\) as a base case for induction on \(k\geq 3\text{.}\) Now assume by induction that for \(n=2^k\) it is true that no element has order higher than \(2^{k-2}\text{.}\) I.e.,
By definition of divisibility, that means for any odd number \(a\text{,}\) we have that
for some integer \(m\text{.}\)
Next, let's look at what happens to everything in modulus \(2^{k+1}\text{.}\) We want that
While it's easy to get \(2^{k+1}\) from \(2^k\text{,}\) the only way to easily get \(a^{2^{k-1}}\) from \(a^{2^{k-2}}\) is by squaring. (Recall Fact 4.5.5 where we found powers quickly by using \((a^{2^e})^2=a^{2^{e+1}}\text{.}\))
So we write \(a^{2^{k-1}}\) as a square, substitute the above, and look at the remainders.
By induction we are done; because the highest possible order of an element is less than \(\phi\text{,}\) there are no primitive roots modulo \(2^k\) for \(k>2\text{.}\) (Remember by Lagrange's Theorem on Group Order in any case the order is a power of two.)
xxxxxxxxxx
primitive_root(64)
Fact 10.3.3.
It turns out that \pm 5 have order 2^{k-2} in U_{2^k}\text{.}
Proof.
We won't prove this, but it is easy if you use just a little group theory.
xxxxxxxxxx
def _(power=5):
a = mod(5,2^power)
pretty_print(html("Powers of 5 modulo $2^{%s}$ are"%power))
print([a^i for i in [1..2^(power-1)]])
Subsection 10.3.2 Two important lemmas
ΒΆSubsubsection 10.3.2.1 How the lemmas work
ΒΆLemma 10.3.4.
Suppose p is prime and the order of a modulo p is d\text{.} If b and d are coprime, then a^b also has order d modulo p\text{.}
Proof.
See Exercise 10.6.6.
Lemma 10.3.5.
Suppose p is prime and d divides p-1 (and hence is a possible order of an element of U_p). There are at most \phi(d) incongruent integers modulo p which have order d modulo p\text{.}
Proof.
See Exercise 10.6.7.
Fact 10.3.6.
If there is one primitive root of n\text{,} then there are actually \phi(\phi(n)) of them.
Proof.
We will only deal with the case of \(n=p\) prime (see Exercise 10.6.10 for the rest).
In Lemma 10.3.4, let the order of \(a\) be \(p-1\text{.}\) Then \(a\) is a primitive root modulo \(p\text{,}\) and so is \(a^b\) for every \(b\) coprime to \(p-1\text{.}\) Since there are \(\phi(p-1)\) of these, it satisfies the claim. By the Lemma 10.3.5, there can't be more.
xxxxxxxxxx
def _(p=(41,prime_range(100))):
a=mod(primitive_root(p),p)
pretty_print(html("$%s$ is a primitive root of $%s$, with order $%s$"%(a,p,p-1)))
L=[(i,a^i,(a^i).multiplicative_order()) for i in range(2,p-1) if gcd(i,p-1)==1]
for item in L:
pretty_print(html(r"$%s^{%s}\equiv %s$ also has order $%s$ (and $\gcd(%s,%s)=1$)"%(a, item[0], item[1], item[2], item[0], p-1)))
Subsubsection 10.3.2.2 How the lemmas (don't) fail
ΒΆTo continue, let's pick a non-prime number we know something about to see how many numbers we have with a given order. We saw in Proposition 10.3.2 that powers of two (past 4) do not have primitive roots, but U_{2^k} does have lots of elements with the next smallest possible order. So, for example, for n=32 we can look at whether powers b coprime to that order (8) of such an element are in fact also elements with the same order.xxxxxxxxxx
def _(n=5):
pretty_print(html("Modulo $2^%s"%n))
a=mod(5,2^n)
L=[(i,a^i,(a^i).multiplicative_order()) for i in range(1,a.multiplicative_order()) if gcd(i,a.multiplicative_order())==1]
for item in L:
pretty_print(html(r"$%s^{%s}\equiv %s$ has order $%s$ (and $\gcd(%s,%s)=1$)"%(a, item[0], item[1], item[2], item[0], a.multiplicative_order())))
xxxxxxxxxx
def _(n=5):
pretty_print(html("Modulo $2^%s"%n))
a=mod(-5,2^n)
L=[(i,a^i,(a^i).multiplicative_order()) for i in range(1,a.multiplicative_order()) if gcd(i,a.multiplicative_order())==1]
for item in L:
pretty_print(html(r"$%s^{%s}\equiv %s$ has order $%s$ (and $\gcd(%s,%s)=1$)"%(a, item[0], item[1], item[2], item[0], a.multiplicative_order())))