1
$\begingroup$

I know how to prove Fermat's little theorem using the binomial expansion and induction.

How can I prove it using Lagrange's theorem?

So I want to show $c^p\equiv c\pmod p$, i.e. $c^{p-1}\equiv 1\pmod p$ since $\Bbb F_p$ is a field. We have for some $k\geq 1$ that $c^k\equiv 1\pmod p$. In partiular, $k\mid p-1$ (Lagrange) since $c$ is an element of multiplicative order $k$ in $\Bbb F_p$. Thus $k\in \{1, p-1\}$. How do I exclude the case $k=1$ now?

$\endgroup$
  • 2
    $\begingroup$ Because the onle element with order 1 is the identity $\endgroup$ – Martín Vacas Vignolo Jul 26 '16 at 14:42
  • $\begingroup$ I don't follow. If $k=1$ then $c\equiv 1\pmod p$. Hence $c\in \{1,p+1,2p+1,\cdots\}$. ? $\endgroup$ – MyNameIs Jul 26 '16 at 14:49
  • $\begingroup$ Your deduction that $k\in\{1,p-1\}$ is wrong. What if $p=7?$ Then $k$ can be, for example, $2.$ (In fact, $6^2=36\equiv 1.$) What Fermat's Little Theorem says is that $c^{p-1}$ is always congruent to 1 no matter what the $c$ is, not that $p-1$ is the only power such that $c^{p-1}\equiv 1.$ $\endgroup$ – dhk628 Jul 27 '16 at 1:30
4
$\begingroup$

The multiplicative group $(\mathbb{Z}/p\mathbb{Z})^\times$ has order $p-1.$ Take any $a\in\mathbb{Z}/p\mathbb{Z}$ and let $k$ be the order of $a,$ i.e. $k$ is the smallest positive integer such that $a^k=1 \bmod{p}.$ Then the group $\{1,a,a^2,\dots,a^{k-1}\}$ is a subgroup of $G$ of order $k.$ By Lagrange's theorem, $k$ divides $p-1$, i.e. $p-1=kn$ for some $n.$

Then $a^{p-1}=a^{kn}=(a^k)^n=1^n=1 \bmod{p}$

$\endgroup$
  • $\begingroup$ Somehow that's simpler than I thought it would be, thanks! $\endgroup$ – MyNameIs Jul 27 '16 at 7:06
  • $\begingroup$ Yup, it's really just a direct corollary of Lagrange's. A generalization would be that if $G$ is a finite group containing $g,$ then $g^{\lvert G\rvert}=e$ because the subgroup generated by $g$ has order $o(g),$ which divides $\lvert G\rvert,$ and $g^{o(g)}=e.$ This also explains why Euler's theorem (with the totient function) works. $\endgroup$ – dhk628 Jul 28 '16 at 5:15
1
$\begingroup$

The order of the group $(\mathbb{Z}/p)^\times$ is $p-1$. To use Lagrange means to know, that if $a$ is not devided by $p$ then there exists $b\in (\mathbb{Z}/p)^\times$ defined by $a$ with $b^{p-1}=1$ and therefore $a^{p-1}\equiv 1\mod p$. And so we get Fermat's Little Theorem.

$\endgroup$
  • $\begingroup$ I am having trouble parsing that. Could you please reformulate it or something? I don't understand the second or third sentence. Thanks. $\endgroup$ – MyNameIs Jul 26 '16 at 15:54
  • $\begingroup$ @MyNamels : dhk628 has done it. :-) $\endgroup$ – user90369 Jul 27 '16 at 8:03

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.