How to find primitive roots of big numbers modulo n, like 121?

I know how to find primitive roots of prime numbers and small numbers as 14, where phi(14) = 6. At small numbers i just look at each element and determine the order. If the order is the same as $\phi(n)$ i have a primitive root, this is a lot of work but it seemed to work out if there is an easier method i would love to hear it :).

The problem is that when i look at a number such as $121$ i have $\phi(121) = 110$. I can't go through all elements, because that would cost me to much time. Are there neat tricks to solve this one.

I know $121 = 11 \cdot 11$ and i know the primitive roots of mod 11, if one can determine the primitive roots of $p^2$ by knowing the roots of $p$ i would like to know how that is possible (it's just an hypothesis, maybe this isn't true at all)

Any hints would be very welcome!

Kees

• If $a$ is a primitive root modulo $p$, it has a good chance of also being a primitive root modulo $p^2$. If it isn't, then $a + p$ is. And if $b$ is a primitive root modulo $p^2$, then it is a primitive root modulo $p^k$ for all $k$. – Daniel Fischer Sep 22 '15 at 11:25
• how do you check which one works, because in the case of 121, it is quite hard to see if $2^{110} = 1 \mod 121$ or $13^{110} = 1 \mod 121$ – Kees Til Sep 22 '15 at 11:41
• We know that $a^{110} \equiv 1 \pmod{11^2}$ for $11 \nmid a$ from Euler's theorem. If we know that the order of $a$ modulo $p$ is $p-1$, then the order modulo $p^2$ must be a multiple of $p-1$, and it must divide $(p-1)p$. So the only possibilities are that the order is $p-1$, or it is $(p-1)p$. Thus we look at $a^{p-1}$. If that is $\equiv 1 \pmod{p^2}$, we know $a$ is not a primitive root modulo $p^2$ [and then we know $a+p$ will be], and if $a^{p-1}\not\equiv 1 \pmod{p^2}$, it follows that $a$ is a primitive root. – Daniel Fischer Sep 22 '15 at 11:45

In general, if $g$ is a primitive root mod $p$ then $g$ or $g+p$ is a primitive root mod $p^2$.

For $p=11$, we have that $g=2$ works.

It is enough to test that $2^{110/q}\not \equiv 1 \bmod 121$ for $q=2,5,11$, the prime divisors of $110=\phi(121)$.

• how do you check that 2 works, do you calculate $2^{110}$? – Kees Til Sep 22 '15 at 11:37
• @KeesTil You calculate $2^{10}$ (modulo $11^2$). – Daniel Fischer Sep 22 '15 at 11:40

For prime $p,$

if ord$_pa=d,$

either ord$_{p^2}a=pd$ or ord$_{p^2}(a+kd)=pd$ if $(k,p)=1$

If $d=\phi(p)=p-1,a$ is primitive root of $p$

and $p=11$

Assume that $p>2$. In order to find a generator for $G=\left(\mathbb{Z}/_{p^k\mathbb{Z}}\right)^*$, we may apply the following algorithm:

Step 0: Find a generator of $\mathbb{F}_p^*$ by testing $2,3,4,\ldots$. Assuming the GRH, that step requires at most $C\log^2 p$ tests;

Step 1: Apply Hensel's lifting lemma to lift a generator for $\left(\mathbb{Z}/_{p^m\mathbb{Z}}\right)^*$ to a generator for $\left(\mathbb{Z}/_{p^{m+1}\mathbb{Z}}\right)^*$ through translations.