Định lý Fermat nhỏ về số nguyên tố

Định lý này có khi còn được gọi là định lý nhỏ của Fermat. Nó được phát biểu như sau:

Nếu p là số nguyên tố và có (a,p)=1, \forall a \in \mathbb{N} thì ta có: a^p \equiv a \pmod p

Ta có thể chứng minh bài toán này như sau:

Xét dãy số a,2a,3a,...,(p-1)a, ta thấy sẽ không tồn tại bất kỳ m, n sao cho: 0<n \ne m<pna \equiv ma \pmod p

Thật vậy, giả sử tồn tại m, n thỏa, ta có: ma-na = a(m-n) \vdots p.(m-n) < p \implies a \vdots p!!! (vô lý)

Như vậy, ta có thể khẳng định rằng số dư khi lấy từng phần từ của dãy a,2a,3a...(p-1)a cho p sẽ rải đều trên 1,2,3...,(p-1) . Xét tích a.2a.3a. (p-1)a = (p-1)!.a^{p-1} \equiv 1.2.3...(p-1) \pmod p

Giản ước hai vế ta có điều phải chứng minh: a^{p-1} \equiv 1 \pmod p.

No Comments

Post A Comment