1
$\begingroup$

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!

2 Answers 2

1

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

  • 0
    There aren't any primitive roots mod 39. The unit group of the integers modulo$39$is isomorphic to $({\bf Z}/3{\bf Z})^*\times({\bf Z}/13{\bf Z})^*$, which is abstractly $C_2\times C_{12}$, which isn't cyclic, which means it can't be generated by a single element, which is to say there is no primitive root. There is a primitive root modulo $q$ if and only if $q$ is 2, 4, $p^r$, or $2p^r$ with $p$ an odd prime and $r$ a positive integer.2012-05-06
2

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?)

  • 0
    Yes, $29$ was a typo. Thanks!2012-05-05