# Finding all the primitive roots modulo $25$ and $26$- methods and theorems.

I'd really love your help with the following problem. I'm trying to use couple of theorems that I know, but I'm not sure if I'm allowed to and if I'm doing it correctly.

The question is simple: I need to find all the four primitive roots of modulo 26 and the eight primitive roots modulo 25, it's just that I'm kind of lost with what to use or to do in this case.

This is what I tried to do: 26 is not a prime number. $26=2^1 \cdot 13^1$, so $u(\mathbb{Z}/_{26}\mathbb{Z})\simeq u(\mathbb{Z}/_{2}\mathbb{Z})u\times (\mathbb{Z}/_{13}\mathbb{Z})$, I already know that the primitive roots of 13 are $2,6,7,11$.

$(a)$What does $u(\mathbb{Z}/_{26}\mathbb{Z})\simeq u(\mathbb{Z}/_{2}\mathbb{Z})u\times (\mathbb{Z}/_{13}\mathbb{Z})$ really mean? and $(b)$ how does it help me find all the primitive roots of modulo 26 once I already know $13$s?

For 25, there's a theorem saying that $g^k$ is a primitive root modulo m if and only if $(k, \phi (m)) = 1$, for a primitive root modulo $m$. since I already know that $2$ is a primitive root modulo $25$, I can use this theorem.$(c)$ Can I use the same method for $26$?

Thanks a lot!

In answer to (a), what it really means is that there is a group isomorphism from the left side to the right side; moreover, that isomorphism is quite simple; given $x$ on the left side, map it to $(x\mod2,x\mod{13})$ on the right. In practice, it means that for any residue mod 13, there's an odd number which leaves the same residue mod 13, and that's the corresponding element in the 26-group. To be completely explicit, and to answer (b), 2, 6, 7, 11 correspond to 15, 19, 7, 11, respectively, mod 26, and so those should be your primitive roots.

For 25, I don't see how the theorem you quote is of any use, and I don't see how 29 gets a mention. For $25=5^2$, you can use a theorem that says that if $g$ is a primitive root modulo a prime $p$, then at least one of the numbers $g$, $g+p$ is a primitive root modulo $p^2$.

• The isomorphism is even stronger: it's a ring isomorphism. – huon May 5 '12 at 12:36
• sorry $29$ was a typo. – Jozef May 5 '12 at 12:46
• Well, then the generators of $\Bbb Z/25\Bbb Z$ are the powers $2^k$ with $k$ not divisible by $5$. – Andrea Mori May 5 '12 at 12:50
• @dbaupp, I'm taking the $u$ to mean the units, so we don't have a ring, just a group. Of course you are right that the group isomorphism is just the restriction to the units of a ring homomorphism. – Gerry Myerson May 5 '12 at 12:54
• @GerryMyerson, ah, of course! (I must've missed the $u$ the first time.) – huon May 5 '12 at 12:56

If you have a product $C_1\times C_2$ of cyclic groups of coprime order, you should check that an element $(g_1,g_2)$ is s generator for the product if and only if $g_1$ is a generator of $C_1$ and $g_2$ is a generator of $C_2$.

Thus, knowing the generators (or primitive roots, as you call them) of $\Bbb Z/13\Bbb Z$ is helpful in finding the generators of $\Bbb Z/26\Bbb Z\simeq\Bbb Z/2\Bbb Z\times\Bbb Z/13\Bbb Z$ since it reduces the task to finding the generators of $\Bbb Z/2\Bbb Z$ (which has an obvious answer)

In general you know that if $g$ generates $C$ and $|C|=n$, then all the generators of $C$ are exactly the powers $g^k$ with $k$ coprime to $n$. This reduces the task to finding just a single generator and can be applied to any of your examples.

Yet, knowing that $2$ generates $\Bbb Z/29\Bbb Z$ will not be of any help in finding the generators of $\Bbb Z/25\Bbb Z$ (or was that a typo?)

• Yes, $29$ was a typo. Thanks! – Jozef May 5 '12 at 12:46