This question is different from this question as I want to find all primitive roots, and not just some.

Is my following approach correct?

We have $121=11^2$, with $11$ an odd prime, and $2 \ge 1$, hence $\mathbb{Z}/ 11^2 \mathbb{Z}$ is cyclic.

Now we want to find a generator for $\mathbb{Z}/11^2\mathbb{Z}$. I found a suggestion for this here see the answer by Jack D'Aurizio, but it required some theory I didn't cover (Hensel's lifting lemma), so I try something different.

We have that $\phi(121) = 110 = 2*5*11$, hence we look for an element of order $110$. We pick elements from $k = 2,3,4, ...$, and compute $k^n$ for $n \in \{2,5,11,2*5,2*11,5*11 \}$ if all of these give $k^n\not=1$ we know that $k$ is a primitive root modulo $121$.

Can this process of finding a generator been done more efficient? An idea would be this: suppose we find $k,l,m$ of orders $2,5,11$ respectively we know that $klm$ has order $2*5*11$ by them being coprime. Am I correct?

Now we have the following group isomorphism $\psi : (\mathbb{Z}\backslash 110\mathbb{Z},+) \rightarrow (\mathbb{Z}\backslash 121\mathbb{Z})^*$ given by: $\psi(n) = k^n$. Now a primitive root modulo 121 are precisely the elements of order $110$. As Dietrich Burde mentioned: $(\mathbb{Z}\backslash 110\mathbb{Z},+)$ is cyclic, hence it has $\phi(110) = 40$ generators.

And as isomorphisms preserve order. It suffices to find all elements of order $110$ in $(\mathbb{Z}\backslash 110\mathbb{Z},+)$. But $n \in (\mathbb{Z}\backslash 110\mathbb{Z},+)$ has order 110 IFF $\gcd(n,121) = 1$. Hence we need to find all elements in $(\mathbb{Z}\backslash 110\mathbb{Z},+)$ that are coprime with $110$. Is there an efficient way to do this? Now given such an $n \in (\mathbb{Z}\backslash 110\mathbb{Z},+)$, we obtain the corresponding primitive root modulo $121$ via $\psi(n)=k^n$.

  • 1
    $\begingroup$ There are $\phi(\phi(121))=40$ primitive roots modulo $121$. See this question how to find them (there is no effective procedure in general, but $121=p^2$). $\endgroup$ – Dietrich Burde Nov 9 '18 at 19:04
  • $\begingroup$ @DietrichBurde you are right! I placed your remark in the question. $\endgroup$ – Jens Wagemaker Nov 9 '18 at 19:09
  • $\begingroup$ You can reduce computations a bit using the Theorem, mentioned by Álvaro Lozano-Robledo at this question. $\endgroup$ – Dietrich Burde Nov 9 '18 at 19:13

Here is one way to do it that requires knowing only a primitive root $\bmod p$ to get all primitive roots $\bmod p^2$, provided that $p$ is twice a smaller prime plus $1$, so that all nonzero residues besides $\pm 1$ are either quadratic or primitive. I will demonstrate it for $p=5$ letting you apply it for $p=11$.

Start with $2$ as a primitive root $\bmod 5$. Then there will be a series of primitive roots $\equiv 5k+2 \bmod 25$. For one residue $k \bmod 5$ we will have $(5k+2)^4\equiv 1 \bmod 25$ and that value of $k$ must be rejected, but other values of $k$ will all work.

Use the Binomial Theorem to get $(5k+2)^4$, but retain only the first ad zero powers of $k$ (why?). Thus

$(5k+2)^4 \equiv (4)(5k)(2^3)+2^4 \equiv 1 \bmod 25$

$10k+16 \equiv 1, 10k \equiv 10 \bmod 25$

Divide by $10$ noting that the modulus is to be divided by $gcd(10,25)=5$. Then $k\equiv 1 \bmod 5$ meaning $7$ will not be a primitive root $\bmod 25$ but all other residues two greater than a multiple of $5$ will work. We therefore get a subset of primitive roots:


Now take the root we rejected, $7$. If we multiply the above primitive roots by it, we get nonprimitive roots because these are quadratic residues. But multiply by $7$ twice, that is by $7^2$, and we get another set of primitive roots because the products are non-quadratic and also miss being $\equiv -1 \bmod 5$. Since $7^2 \equiv 24 \equiv -1 \bmod 25$ this gives another subset of primitive roots


Multiplying by $7^2$ again cycles us back to the first subset, so the complete set of primitive roots $\bmod 25$ will be the union of the two subsets


Now apply this method to$11=2×5+1$ and see what happens. Since $11$, like $5$, is not one greater or one less than a multiple of $8$, $2$ will be a primitive root $\bmod 11$. Since there are four such primitive roots $\bmod 11$ overall you will need to generate four subsets before taking their union.


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.