$$a^{\varphi (n)} \equiv 1 \text{(mod n)}$$
Trong đó $\varphi (n)$ là phi hàm Euler, hàm này đếm số các số nguyên dương nhỏ hơn $n$ và nguyên tố cùng nhau với $n$.
Trường hợp đặc biệt, khi $n=p$ là số nguyên tố, ta có định lý Fermat nhỏ.
Ứng dụng:
1) Tìm số dư của $7^{100}$ khi chia cho $13$.
Giải
Ta có: $\varphi (13)=12$, nên:
$$7^{12} \equiv 1 \text{(mod 13)}$$
Do đó:
$$7^{100} \equiv (7^{12})^8.7^4 \equiv 9 \text{(mod 13)}$$
Vậy $7^{100}$ chia cho $13$ dư $9$
2) Chứng minh rằng $x^{n+8} \equiv x^n \text{ (mod 10), } \forall x$
Giải
Ta chỉ cần chứng minh rằng $x^n(x^8-1)$ đồng thời chia hết cho cả 2 và 5, với mọi số tự nhiên $x$.
* Nếu $x$ là số chẵn thì hiển nhiên $x^n(x^8-1)$ chia hết cho 2. Nếu $x$ là số lẻ thì $x^8$ là số lẻ, do đó $x^8-1$ chia hết cho 2.
Do đó $x^n(x^8-1)$ luôn chia hết cho 2 với mọi $x$.
* Nếu $x$ là bội của $5$ thì hiển nhiên $x^n(x^8-1)$ chia hết cho 5.
Nếu $x$ nguyên tố cùng nhau với 5 thì theo định lý Fermat nhỏ, $x^4 \equiv 1 \text{ (mod 5)}$. Do dó $x^8-1$ chia hết cho 5.
Do đó $x^n(x^8-1)$ luôn chia hết cho 5 với mọi $x$.
2) Chứng minh rằng $x^{n+8} \equiv x^n \text{ (mod 10), } \forall x$
Giải
Ta chỉ cần chứng minh rằng $x^n(x^8-1)$ đồng thời chia hết cho cả 2 và 5, với mọi số tự nhiên $x$.
* Nếu $x$ là số chẵn thì hiển nhiên $x^n(x^8-1)$ chia hết cho 2. Nếu $x$ là số lẻ thì $x^8$ là số lẻ, do đó $x^8-1$ chia hết cho 2.
Do đó $x^n(x^8-1)$ luôn chia hết cho 2 với mọi $x$.
* Nếu $x$ là bội của $5$ thì hiển nhiên $x^n(x^8-1)$ chia hết cho 5.
Nếu $x$ nguyên tố cùng nhau với 5 thì theo định lý Fermat nhỏ, $x^4 \equiv 1 \text{ (mod 5)}$. Do dó $x^8-1$ chia hết cho 5.
Do đó $x^n(x^8-1)$ luôn chia hết cho 5 với mọi $x$.
Ta có điều phải chứng mình
0 comments:
Đăng nhận xét