Một chứng minh của định lí Fermat nhỏ


Trong bài này chúng tôi sẽ giới thiệu một chứng minh của định lí Fermat nhỏ, chứng minh này của Euler.

Định lí. Cho số nguyên tố p và số nguyên a không chia hết cho p. Khi đó a^{p-1}\equiv 1\pmod{p}.

Chứng minh. Vì có hai trong các số a^1,a^2,\ldots,a^p có cùng số dư khi chia cho p nên tồn tại số nguyên dương k sao cho k<pa^{k}\equiv 1\pmod{p}, chọn k nhỏ nhất có tính chất này. Nếu k=p-1 thì ta có điều cần chứng minh, sau đây ta xét trường hợp k<p-1.
Tồn tại số nguyên dương b<p không thuộc tập có k phần tử
A_1=\{a^1\mod p,a^2\mod p,\ldots,a^k\mod p\}. Khi đó tập A_2=\{b\times a^1\mod p,b\times a^2\mod p,\ldots,b\times a^k\mod p\}k phần tử và có giao bằng rỗng với A_1. Nếu A_1\cup A_2=\{1,2,\ldots,p-1\} thì p-1 chia hết cho k và ta có điều cần chứng minh. Nếu không, gọi c<p là một số nguyên dương không thuộc tập A_1\cup A_2 và xây dựng tập có k phần tử
A_3=\{c\times a^1\mod p,c\times a^2\mod p,\ldots,c\times a^k\mod p\}, và cứ thế. Cuối cùng ta sẽ có một phân hoạch của \{1,2,\ldots,p-1\}, trong đó mỗi khối có k phần tử. Suy ra p-1 chia hết cho k và định lí được chứng minh.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s