Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
possible duplicate of Order of Cyclic Subgroups –  lhf Apr 19 '12 at 22:26
    
@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. –  Bill Dubuque Apr 19 '12 at 22:40
add comment

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
@ArturoMagidinThanks for your as always really helpful explanations. Maybe there's a typo in the last equality, gcd(...,k) rather than d. –  Andrew Apr 20 '12 at 1:29
    
@Andrew: Indeed there was a typo, thanks. –  Arturo Magidin Apr 20 '12 at 2:49
    
@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? –  Jozef Apr 20 '12 at 7:33
1  
@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. –  Arturo Magidin Apr 20 '12 at 14:06
1  
@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$? –  Arturo Magidin Apr 20 '12 at 14:17
show 1 more comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.