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 < \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

  • $\begingroup$ possible duplicate of Order of Cyclic Subgroups $\endgroup$ – lhf Apr 19 '12 at 22:26
  • $\begingroup$ @lhf But, alas, the single answer to that question simply states the result without proof, so this should not be closed as a duplicate of that. But I do recall other answers covering this ground. $\endgroup$ – Bill Dubuque Apr 19 '12 at 22:40

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

  • $\begingroup$ @ArturoMagidinThanks for your as always really helpful explanations. Maybe there's a typo in the last equality, gcd(...,k) rather than d. $\endgroup$ – user12802 Apr 20 '12 at 1:29
  • $\begingroup$ @Andrew: Indeed there was a typo, thanks. $\endgroup$ – Arturo Magidin Apr 20 '12 at 2:49
  • $\begingroup$ @ArturoMagidin: Thank you for the answer. I wanted to ask you, continuing my answer, if $ k \neq r$ so $\varphi(m)a+kb=r$ and $g^{\varphi(m)a}g^{kb}=g^r$ so $kb=r$ so $k|r$ but $r|k$ so $k=r$ but if $k=r$ we already got a contradiction, will it do for proving the left to the right direction? $\endgroup$ – Jozef Apr 20 '12 at 7:33
  • 1
    $\begingroup$ @Andrew: Yes; it is implied in "$g$ is a primitive element modulo $m$". But it's really irrelevant to the argument: if the order of $g$ is $t$, then the order of $g^k$ is $t/\gcd(t,k)$, whatever $t$, $g$, and $k$ may be. $\endgroup$ – Arturo Magidin Apr 20 '12 at 14:06
  • 1
    $\begingroup$ @Jozef: No, you cannot conclude that $kb=r$; you can only conclude that $kb\equiv r\pmod{\varphi(m)}$, but you already knew that. You are looking at the wrong relationship: it's not the fact that you can write $r$ as a linear combination of $k$ and $\varphi(m)$ that gives you the result here. What you want to use is the fact that $r$ is a common divisor of $k$ and $\varphi(m)$. Write $k=r\kappa$, $\varphi(m)=rt$. Then what is $(g^k)^t$? $\endgroup$ – Arturo Magidin Apr 20 '12 at 14:17

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.


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.