# Proving two distinct primitive roots do not generate $\mathbb{Z}^{\times}_n$ in the same order

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

• Welcome to Mathematics Stack Exchange. Isn't $a^k\equiv b^k$ when $k=\phi(n)$? – J. W. Tanner Jul 17 at 4:54
• 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. – user48939 Jul 17 at 4:58
• For $2$, we get the set $2,4,8,7,5,1$ while for $5$, we get $5,7,8,4,2,1$. – user48939 Jul 17 at 4:59
• $5$ and $11$ are primitive roots mod $18$, but $5^3\equiv11^3\bmod18$ – J. W. Tanner Jul 17 at 5:01
• Is there any way to build a bijective map of $\mathbb{Z}^{\times}_n$ to itself, then? – user48939 Jul 17 at 5:03

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