An integer $k$ in $\mathbb{Z}_{n}$ is a generator of $\mathbb{Z}_{n}$ If and Only if $gcd\left ( n,k \right )=1$

My problem lies with proving the "If" condition and here is my attempt:

Suppose $gcd\left ( n,k \right )=1$

Observe $\frac{n}{gcd\left ( n,k \right )}=\frac{n}{1}=n$

But $\frac{n}{gcd\left ( n,k \right )}=\left | a^{k} \right |=\left | \left \langle a^{k} \right \rangle \right |=\left | \mathbb{Z}_{n} \right |$

But note that $\mathbb{Z}_{n}$ is an additive group so $\left | \left \langle ka \right \rangle \right |=\left | \mathbb{Z}_{n} \right |$

This implies $\left \langle ka \right \rangle=\mathbb{Z}_{n}$

Evidently, we are done if $a=1$ but I am unable to justify this.

A useful hint is appreciated. Thanks in advance.

  • $\begingroup$ the proof is standard in group/ring theory : $\mathbb{Z}_n$ is a finite group, hence the set $\{k, k+k, k+k+k, 4k, 5k, \ldots \}$ contains only finite number of different elements, hence there are $a,b$ with $b > a$ such that $k^b = k^b$ (in the group) i.e. in the integers $(b-a) k \equiv 0 \pmod n$. suppose that $(b-a) < n$, then $gcd(k,n) \ne 1$, and $k$ generates only $b-a$ numbers of $\mathbb{Z}_n$ (a subgroup). otherwise, if $gcd(n,k)=1$ then at least $b-a = n$ and $k$ generates the whole group. $\endgroup$ – reuns Apr 16 '16 at 4:14
  • $\begingroup$ @user1952009 You should post this as an answer $\endgroup$ – Stella Biderman Apr 16 '16 at 4:28

By the Bezout Identity, there exist integers $x$ and $y$ such that $xk+yn=1$. Without loss of generality we may take $x\ge 0$.

So for any $a$, we have $(ax)k\equiv a\pmod{n}$.

  • $\begingroup$ I'm unsure about the last equivalence $\endgroup$ – Mathematicing Apr 16 '16 at 4:58
  • $\begingroup$ We have $xk+yn=1$. Multiply by $a$. We get $(ax)k+(ay)n=a$. Thus $(ax)k=a-(ayn)$, so $(ax)k$ and $a$ differ by a multple of $n$, so $(ax)k\equiv a\pmod{n}$. Or faster, $(ax)k+(ay)n=a$. But $n\equiv 0\pmod{n}$, and the result follows. $\endgroup$ – André Nicolas Apr 16 '16 at 5:06
  • $\begingroup$ This is embarrassing for me as I haven't taken any classes in number theory. Indeed, $n\equiv 0(mod n)$ as (n-0) is an integer multiple of n. How does the result follows? $\endgroup$ – Mathematicing Apr 16 '16 at 5:21
  • $\begingroup$ The proof shows that an arbitrary $a$ can be expressed (modulo $n$) as a "multiple" of $k$, that is, $k$ added to itself a certain number of times. You may prefer (I do, but it takes longer to write out, and the Bezout Identity is very good to know) the counting argument described in the comments. $\endgroup$ – André Nicolas Apr 16 '16 at 5:27

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.