# Chứng minh định lí Fermat nhỏ

**1. Bài toán nhỏ**
- Trước khi đi vào c/m định lý, ta hãy cùng c/m bài toán nhỏ sau:

> $a$ $≡$ $b$ $(mod$ $p)$, $a \geq b$
>
> Thì $a - b$ $≡$ $0$ $(mod$ $p).$

- Gọi $\begin{cases} a = px + r\\b = py + r \end{cases}$

$\Rightarrow$ $a - b = p.x + r - p.y - r = p(x - y)$

Mà $(x - y)p$ $⋮$ $p$ nên $a - b$ $⋮$ $p$

$\Rightarrow$ $a - b ≡ 0$ $(mod$ $p)$, ==đpcm.==

**2. Chứng minh định lí Fermat nhỏ**

- Ta có dãy $A$: $a, 2a, 3a, ..., (p - 1)a$, $a$ không chia hết cho $p$.
- Và dãy $R$: $r_{1},~ r_{2}~, ~r_{3}, ..., ~r_{p-1}$ lần lượt là modulo các số trong dãy $A$ với $p$.
Các số trong dãy $R$ phải là KHÁC NHAU ĐÔI MỘT, bởi vì:
- Gia sử tồn tại $ia ≡ ja$ $(mod$ $p)$, $i$ $>$ $j$

$\Rightarrow$ i$a - ja ≡ 0$ $mod$ $p$ (theo bài toán nhỏ vừa c/m xong).

$\Rightarrow$ $(i - j)a ≡ 0$ $mod$ $p.$

MÀ $(i - j) < p$, các thừa snt trong $a$ không chứa $p$ (vì $a$ không chia hết cho $p$), $p$ là **snt** nên không thể xảy ra $(i - j)a ≡ 0$ $mod$ $p.$

$\Rightarrow$ Các số $r_{i}~$ tồn tại **ĐÔI MỘT**.

- Như vậy, khi lấy dãy $A$ nhân với nhau, ta được:

$a . ~2a . ~3a ~... ~(p-1)a.$

- Tách $a_{i}$ theo $r_{i}~$ ta được:

$((px_{1}~ + r_{1})+(px_{2}~ + r_{2})+…+(px_{p-1}~ + r_{p-1}))$.

- Đem modulo cho p ta được:

$((px_{1}~ + r_{1})+(px_{2}~ + r_{2})+…+(px_{p-1}~ + r_{p-1}))$ $mod$ $p.$

- Theo số học modulo:

$\Rightarrow$ $((px$~1~ $+ r$~1~$)$ mod $p$ $+$ $(px$~2~ $+$ $r$~2~$)$ mod $p$ $+…+$ $(px$~p-1~ $+$ $r$~p-1~$)$ mod $p)$ mod $p$

$\Leftrightarrow$ $(r$~1~ $+$ $r$~2~ $+ ... +$ $r$~p-1~$)$ mod $p$.

- Vì ta đã chứng minh $r$~1~, $r$~2~, ... $r$~p-1~ khác nhau đôi một rồi nên các số đó chính là $1, 2, ..., (p - 1)$.

$\Rightarrow$ $(px$~1~ $+$ $r$~1~$)+(p$x~2~ $+$ r~2~$)+…+($$px$~p-1~ $+$ $r$~p-1~$)$ $≡ 1 . 2 . 3 ... (p - 1)$ $($mod $p)$.

$\Leftrightarrow$ $a . 2a . 3a ... (p-1)a$ $≡$ $1 . 2 . 3 ... (p - 1)$ mod $p$

$\Leftrightarrow$ $(p - 1)! . a$^p-1^ $≡$ $(p-1)!$ mod $p$.

- Theo bài toán nhỏ ta vừa c/m:

$\Rightarrow$ $(p - 1)! . a$^p-1^ $-$ $(p-1)! ≡ 0$ mod $p.$

$\Leftrightarrow$ $(p-1)! . (a$^p-1^ $-$ $1) ≡ 0$ mod $p.$

Vì các **thừa snt** trong $(p - 1)!$ **không chứa $p$** nên thừa snt sẽ nằm trong $a$^p-1^ $-$ $1.$

$\Rightarrow$ $a$^p-1^ $-$ $1 ≡ 0$ mod $p.$

$\Leftrightarrow$ $a$^p-1^ $≡ 1$ mod $p$ ==(đpcm)==.