1
$\begingroup$

The theorem states: if $n\in\mathbb{N}$ and $(a,n)=1$ then $$a^{\varphi (n)}\equiv 1\bmod n$$ Where $\varphi$ is the Euler-Phi function

Take $a\in\mathbb{Z}$ such that $(a,n)=1$. Consider $\mathcal{U}_n$, the set of units modulo $n$. We know that $\varphi (n)=|\mathcal{U}_n |$. So $$\mathcal{U}_n=\lbrace 1=b_1 ,b_2 ,\ldots ,b_{\varphi (n)}\rbrace $$ where $1=b_1 < b_2 < \ldots < b_{\varphi (n)}<n$. Now consider $$a\mathcal{U}_n =\lbrace ab_1 , ab_2 ,\ldots , ab_{\varphi (n)}\rbrace$$ We claim that each element of $a\mathcal{U}_n$ is just the elements $b_1 ,b_2 ,\ldots ,b_{\varphi (n)}$ reordered (modulo $n$). It is trivial that $|a\mathcal{U}_n |\leq |\mathcal{U}_n |$. Assume that $ab_i \equiv ab_k \bmod n$ for $1\leq i<k\leq \varphi (n)$. We know that $(a,n)=1$. There exists $\hat{a}\in\mathbb{Z}$ such that $\hat{a}a\equiv 1\bmod n$. So $$\hat{a}a b_i \equiv \hat{a}ab_k \bmod n \Rightarrow b_i \equiv b_k \bmod n$$ Which is a contradicition

My question is why is this last statement a contradiction? What assumption does it break?

$\endgroup$
  • $\begingroup$ Ok that makes sense, but this course assumes no knowledge of Group Theory. How is it a direct contradiction to an earlier assumption? $\endgroup$ – Napthus Dec 9 '15 at 20:30
  • 2
    $\begingroup$ We assume $1=b_1<b_2<...<b_{\phi(n)}<n$, which implies that the $b_i$ are pairwise distinct modulo $n$. $\endgroup$ – Peter Dec 9 '15 at 20:32
  • 1
    $\begingroup$ As written, no asusmption is broken. Instead, you have shown $ab_i\equiv ab_k\implies b_i\equiv b_k$. This is fine enough to show that multiplication by $a$ is injective. It seems that the implicit assumption $b_i\ne b_k$ was (unnecessarily) made for the injectivity proof. -- Edit: Oh, wait: $i<k$ ! $\endgroup$ – Hagen von Eitzen Dec 9 '15 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.