Luyện tập sử dụng định lý Euler (hay còn gọi là Euler-Fermat)
BÀI TOÁN
Tìm dư của phép chia số 55552222+22225555 cho 7. |
HƯỚNG DẪN GIẢI
Định lý Euler: Nếu n là số nguyên dương bất kỳ và a là số nguyên tố cùng nhau với n, thì aφ(n)≡1(mod n) .
Nếu n là số nguyên tố thì φ(n)=n−1. |
Để giải bài toán đã cho ta thực hiện một thao tác gọi là “tối giản cơ số và tối giản mũ”. Lấy ví dụ cho số 55552222. Vì 7 là số nguyên tố nên φ(7)=6.
Tối giản cơ số: 
. Tối giản mũ: 
.
Để nhập phép chia có dư ta bấm qT5
Ta thấy 7 và 5555 nguyên tố cùng nhau nên theo định lý Euler:
55552222≡42(mod 7).
Tương tự 
. Vậy 22225555≡35(mod 7).
Do đó 55552222+22225555≡42+35(mod 7).
Ta có: 
, nghĩa là số đã cho chia hết cho 7.
