Competition problem — Number theory

Library / /394 of 520

Number theory Difficulty 6.5 National olympiad Prove it

Fermat's Little Theorem: Let $p$ be a prime, and $a$ be any integer coprime to $p$ , then
$a^{p-1} \equiv 1(\bmod p)$

Fermat's Little Theorem has a variant form, which is sometimes more applicable:
For any integer $a$ , $a^{p} \equiv a(\bmod p)$ .
(When $p \nmid a$ , the two propositions are equivalent; when $p \mid a$ , the latter is obviously true.)

Solution

It is not difficult to give a proof of Fermat's Little Theorem by induction: It is easy to see that we only need to prove the proposition for $a=0$ , $1, \cdots, p-1$ . When $a=0$ , the conclusion is obviously true. If we already have $a^{p}=a(\bmod p)$ , then since $p \mid C_{p}^{i}(i=1,2, \cdots, p-1)$ , we have
$(a+1)^{p}=a^{p}+\mathrm{C}_{p}^{1} a^{p-1}+\cdots+\mathrm{C}_{p}^{p-1} a+1 \equiv a^{p}+1 \equiv a+1(\bmod p),$

This shows that the proposition also holds when $a$ is replaced by $a+1$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.