$g^k$ is a primitive element modulo $m$ iff $\gcd (k,\varphi(m))=1$

I'd really love your help with the following one: : Let $g$ a primitive element modulo $m$, $g^{\varphi(m)} \equiv 1\pmod{m}$. I need to prove that $g^k$ is a primitive element modulo $m$ iff $\gcd (k,\varphi(m))=1$.

First I tried to assume the left part, since $g^k$ is a primitive element so $g^k \equiv 1\pmod{m}$, so that $k \neq \varphi(m) $. so there is a $r$ such that $r| \varphi(m)$, $r|k$.

if $k=r$ so $\varphi(m)=kt$ for some $t$, $t &lt \varphi(m)$ so that $1 \equiv g^{\varphi(m)}=g^{kt}=(g^{k})^t$ so $g^k$ is not an primitive element. if $k \neq r$ so there are $a,b$ such that $\varphi(m)a+kb=r$ for $r\gt 1$, what can I do next?

I succeeded the other direction.

Thanks a lot

Solution 1:

Hint. Let $d=\gcd(k,\varphi(m))$.

$$\begin{align*} (g^k)^{\ell}\equiv 1\pmod{m} &\iff g^{k\ell}\equiv 1\pmod{m}\\ &\iff \varphi(m)\text{ divides }k\ell\\ &\iff \frac{\varphi(m)}{d}d\text{ divides } \frac{k}{d}d\ell\\ &\iff \frac{\varphi(m)}{d}\text{ divides }\frac{k}{d}\ell\\ &\iff \frac{\varphi(m)}{d}\text{ divides }\ell, \end{align*}$$ since $$\gcd\left(\frac{\varphi(m)}{d},\frac{k}{d}\right) = \frac{1}{d}\gcd(\varphi(m),k) = 1.$$

This in fact tells you the order of $g^k$ modulo $m$ for any $g$; more generally, it tells you that if you know the order of $g$, then you can compute the order of $g^k$ for any $k$, whether $g$ is a primitive root or not.

In fact, this is a special case of the result from basic Group Theory: if $a$ has order $m$, then $a^k$ has order $m/\gcd(m,k)$.

For your attempt: it is incorrect when you say that if $g^k$ is a primitive element then $g^k\equiv 1\pmod{m}$; that would imply that $\varphi(m)|k$, not that $g^k$ is a primitive element.

You don't want to use the fact that $\gcd(k,\varphi(m))$ is a linear combination of $k$ and $\varphi(m)$, you want to use the fact that $k\varphi(m)/r$ is the least common multiple of $k$ and $\varphi(m)$.

Solution 2:

Hint $\rm\ g^{kn}\! = 1\iff \varphi\: |\: kn\iff \varphi\: |\: kn,\varphi n\iff \varphi\: |\: (kn,\varphi n) = (k,\varphi)n\iff \smash[b]{\dfrac{\varphi}{(k,\varphi)} \bigg|\: n}$

Therefore $\rm\: g^k\:$ has order $\rm\:\varphi/(k,\varphi),\:$ which $\rm = \varphi\iff (k,\varphi) = 1.\ \ \ $ QED

Alternatively, one can give a dual proof, employing $\rm\ [k,\varphi] :=\: lcm(k,\varphi)$

Then $\rm\:\ g^{kn}\! = 1\iff \varphi\: |\: kn\iff k, \varphi\: |\: kn\iff [k,\varphi]\: |\: kn\iff \smash[t]{\dfrac{[k,\varphi]}k\bigg|\:n}$

The two proofs are equivalent since $\rm\:k\varphi = (k,\varphi)[k,\varphi]\: \Rightarrow\: \smash{\dfrac{\varphi}{(k,\varphi)} = \dfrac{[k,\varphi]}k}$

Remark $\: $ The efficiency of the above proof stems from use of the universal bidirectional $(\!\!\!\iff\!\!\!)$ characterizations of GCD, LCM, viz. in any integral domain one has these universal definitions

Definition of LCM $\quad$ If $\quad\rm a,b\:|\:c \;\iff\; [a,b]\:|\:c \quad\;$ then $\quad\rm [a,b] \;$ is an LCM of $\:\rm a,b$

Definition of GCD $\quad$ If $\quad\rm c\:|\:a,b \;\iff\; c\:|\:(a,b) \quad$ then $\quad\rm (a,b) \;$ is an GCD of $\:\rm a,b$

For many further examples see my posts emphasizing these universal properties of GCD, LCM. Many proofs in number theory become mechanical after one masters these properties.