Định lý Euler

Cho $a,n$ là hai số nguyên dương, $(a,n)=1$, khi đó:

$$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$.

Ta có điều phải chứng mình