1
$\begingroup$

Let $C_n = \{1, x, \dots, x^{n-1}\}$ and define $\varphi_r : C_n \to C_n$ as $\varphi_r(x^s) = x^{rs}$.

Theorem: $\varphi_r$ is bijective $\iff$ $\gcd(r,n)=1$.

This is the proof given in a set of notes I'm using:

$\varphi_r$ is bijective $\iff \varphi_r$ is surjective $\iff$ $\{\varphi(x)^t : 0 \leq t < n\} = C_n \iff \mathrm{ord}( \varphi_r(x)) = n \iff \frac{n}{\gcd(r,n)} = n \iff \gcd(r,n)=1$

I'm confused by the step $\{\varphi(x)^t : 0 \leq t < n\} = C_n \iff \mathrm{ord}( \varphi_r(x)) = n$. What is the justification for this?

$\endgroup$
1
$\begingroup$

It is because the image of $\phi$ is generated by $\phi_r(x)$. So $\phi_r$ is surjective is equivalent to the fact that $x,\phi_r(x),...,\phi_r(x)^{n-1}$ are distinct.

$\endgroup$
  • $\begingroup$ How does distinctness of $x, \varphi_r(x), \dots, \varphi_r(x)^{n-1}$ demonstrate that $ord(\varphi_r(x)) = n$? $\endgroup$ – D G Jan 16 '18 at 9:56
  • $\begingroup$ because the order of $\phi_r(x)$ divides $n$ (Lagrange). $\endgroup$ – Tsemo Aristide Jan 16 '18 at 9:58
0
$\begingroup$

The order of an element is the same as the number of elements in the subgroup it generates.

Clearly, $\varphi_r(x)$ generates the image of $\varphi_r$, so the map is surjective if and only if $\varphi_r(x)$ has order $n$. The set $$ \{\varphi_r(x)^t:0\le t<n\}=\{\varphi_r(x^t):0\le t<n\} $$ is the image of $\varphi_r$.

By general results, the order of $x^r$ is $n/\!\gcd(n,r)$.

$\endgroup$

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.