0
$\begingroup$

For any suitable $n$ that has primitive roots (i.e. $n$ of the form $2, 4, p^j, 2p^j$, where $p$ is an odd prime), there exist primitive root(s). In the case that $n$ has more than one primitive root, how can I show that they don't generate $\mathbb{Z}^{\times}_n$ (the subset of $\mathbb{Z}_n$ whose elements are coprime to $n$) in the same order?

So, for $a$ and $b$ both distinct primitive roots, $a^k \neq b^k$, $k \in [1, \phi(n)-1]$.

$\endgroup$
  • $\begingroup$ Welcome to Mathematics Stack Exchange. Isn't $a^k\equiv b^k$ when $k=\phi(n)$? $\endgroup$ – J. W. Tanner Jul 17 at 4:54
  • $\begingroup$ Right, I missed that. I was thinking of the case where $n = 9$. $2$ and $5$ are both primitive roots, but they generate $\mathbb{Z}^{\times}_9$ in a different order. $\endgroup$ – user48939 Jul 17 at 4:58
  • $\begingroup$ For $2$, we get the set $2,4,8,7,5,1$ while for $5$, we get $5,7,8,4,2,1$. $\endgroup$ – user48939 Jul 17 at 4:59
  • 1
    $\begingroup$ $5$ and $11$ are primitive roots mod $18$, but $5^3\equiv11^3\bmod18$ $\endgroup$ – J. W. Tanner Jul 17 at 5:01
  • $\begingroup$ Is there any way to build a bijective map of $\mathbb{Z}^{\times}_n$ to itself, then? $\endgroup$ – user48939 Jul 17 at 5:03
0
$\begingroup$

The following is an argument that works, if I am interpreting "in the same order" correctly. Let $g$ and $h$ be primitive roots modulo $n$ and $i$ be a positive integer less than $\phi(n)$ such that $g^i \equiv h\pmod{n}.$ If the powers of $g$ and $h$ cycle through the coprime residues in the same order, then we have $$gh\equiv g^{i+1}\equiv h^2\pmod{n}.$$ Cancelling $h$ from both sides yields $g\equiv h\pmod{n},$ so $g$ and $h$ are not distinct modulo $n.$

| cite | improve this answer | |
$\endgroup$

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.