2
$\begingroup$

If $\gcd(a,n) = 1$, then $a^{\phi(n)}\equiv 1\pmod n$. Here's a three-step proof.

  1. An integer a is invertible means there's some $a^{-1}$ such that $aa^{-1}\equiv 1 \pmod n$. By cause of Jones p84 lemma 5.1 and the Linear Congruence Theorem, an integer $a$ is invertible modulo $n \iff ax \equiv 1 \pmod n \iff \gcd(a,n) \mid 1 \iff \gcd(a,n) = 1.$

  2. Consider the Abelian group of all positive integers less than $n$ which are invertible modulo $n$. This is dubbed $U_n$ in Jones p85 or $\langle(Z_n',{\times})\rangle$ at Proofwiki.
    $ \phi(n)$ simply counts the number of positive integers $a$ coprime to a. So by 1., there are $\phi(n)$ elements in $G$. Tthe order of $G$ is $\phi(n)$.

  3. Lagrange's Theorem occasions Order of Group Element Divides ORder of Finite Group. Thence there must be some $k$ such that $a^{k}=1$ where $k$ divides the order of the group $\langle (Z_n',{\times})\rangle$. This is just $\phi(n)$. Let's say $km=\phi(n)$ Then $a^{\phi(n)}=(a^k)^m=1^m=1$.

(1) Is the last paragraph errorless? The last sentence contains equalities, but Proofwiki's last steps are congruences modulo $m$.

(2) What's the ground plan of the proof? It feels 'oracular' to me - how can you preconceive to consider this uncanny Abelian group, and then to use a corollary of Lagrange's Theorem?

$\endgroup$
  • 1
    $\begingroup$ Where you wrote \equiv 1\,(mod\, n), I changed it to \equiv 1\pmod n. That looks like this: ${}\equiv 1\pmod n$. Your code yields this: ${}\equiv 1\,(mod\, n)$. What I wrote is standard usage. The "p" in \pmod stands for "parentheses". If more than one character needs to be where $n$ is, then enclose them in braces thus: \pmod{23}. That yields $\pmod{23}$. I also changed $<(Z_n',{\times})>$ to $\langle(Z_n',{\times})\rangle$, which is also standard, and did some other similar MathJax emendations. $\endgroup$ – Michael Hardy May 10 '14 at 22:21
1
+50
$\begingroup$

Here is a simple proof that does not depend on Lagrange's theorem:

Consider the map $x\mapsto ax$ on $U_n$. This map is injective because $\gcd(a,n)=1$. Since $U_n$ is finite, the map is surjective, and so is a permutation of $U_n$. Hence $(ax_1)(ax_2)\cdots (ax_m)=x_1x_2\cdots x_m$, where $x_1, x_2,\cdots x_m$ are the elements of $U_n$. Hence $a^m x_1x_2\cdots x_m = x_1x_2\cdots x_m $ and so $a^m=1$, by cancellation. Finally, $m=\phi(n)$.

This proof actually works for all finite abelian groups.

$\endgroup$
  • 1
    $\begingroup$ I wish I knew a proof that $a^m=1$ for all $a\in G$ when $G$ is a group of order $m$ that does not depend on Lagrange's theorem. $\endgroup$ – lhf May 10 '14 at 22:46
0
$\begingroup$

Nothing special about the finite group is really being used, just its order, which you've already determined is $\phi(n)$. Step 3 would hold for any finite group $G$, with $\phi(n)$ replaced with $|G|$.

The last paragraph is fine: the operation in $(Z'_n,\times)$ is just multiplication modulo $n$. Two units $x,y$ modulo $n$ (elements in $\mathbb Z$) are congruent modulo $n$ just if their classes $\bar x, \bar y$ are equal in $(Z'_n,\times)$.

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