2
$\begingroup$

By the formula $$(a+b)^n=\sum_{k=0}^n \binom{n}{k}a^kb^{n-k}$$ we know that $(a+b)^p\equiv a^p+b^p \pmod{p}$,

Is there a proof of Fermat's Little Theorem based on this fact?

$\endgroup$
  • 2
    $\begingroup$ Yes, by induction. $\endgroup$ – Lord Shark the Unknown Jul 5 '18 at 20:13
  • 2
    $\begingroup$ My lord I'll try!!!!!!!!!! $\endgroup$ – Leaning Jul 5 '18 at 20:13
  • 1
    $\begingroup$ @LordSharktheUnknown Induction? Not the fact that $p$ divides $p$ choose $k$? $\endgroup$ – Sorfosh Jul 5 '18 at 20:22
  • 1
    $\begingroup$ @Sorfosh: The OP already has established $(a+b)^p\equiv a^p+b^p \pmod p$ using the fact you mentioned. The issue at hand is how to derive Fermat's Little theorem. That will, in fact, be a proof by induction — which appears in many, many algebra texts. $\endgroup$ – Ted Shifrin Jul 5 '18 at 20:30
  • 1
    $\begingroup$ See also: Deriving Fermat's little theorem from $(a+1)^p\equiv a^p+1$ modulo $p$? (The question is at least similar, maybe it could be considered even a duplicate.) $\endgroup$ – Martin Sleziak Jul 6 '18 at 7:29
2
$\begingroup$

As noted in the comment by Lord Shark, using that fact, for the induction step, assuming as hypotesis $a^p\equiv a \mod p$ we have

$$(a+1)^p\equiv a^p+1\equiv a+1 \mod p$$

$\endgroup$
  • $\begingroup$ Thanks to @ÍgjøgnumMeg for the edit! $\endgroup$ – user Jul 5 '18 at 22:03
  • $\begingroup$ I'm not sure if it's bad etiquette to edit without consultation, though I suppose if consultation were required there wouldn't be an option to edit! $\endgroup$ – ÍgjøgnumMeg Jul 6 '18 at 8:29

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.