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!


  • 4
    $\begingroup$ 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$. $\endgroup$ – Daniel Fischer Sep 22 '15 at 11:25
  • $\begingroup$ 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$ $\endgroup$ – Kees Til Sep 22 '15 at 11:41
  • 2
    $\begingroup$ 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. $\endgroup$ – 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)$.

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

Like Order of numbers modulo $p^2$

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.