# How to find all primitive roots modulo 121?

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$$.

• 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$). – Dietrich Burde Nov 9 '18 at 19:04
• @DietrichBurde you are right! I placed your remark in the question. – Jens Wagemaker Nov 9 '18 at 19:09
• You can reduce computations a bit using the Theorem, mentioned by Álvaro Lozano-Robledo at this question. – 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:

$$\{2,12,17,22\}$$

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

$$\{3,8,13,23\}$$

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

$$\{2,3,8,12,13,17,22,23\}$$.

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.