$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
 A: 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)$. 
A: 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.
