Ứng Dụng Các định Lý Euler Và Fecmat - 123doc

2 Các dạng toán về số chính phương

3.2 Ứng dụng các định lý Euler và Fecmat

Định lý Euler và định lý Fermat có nhiều ứng dụng, ở đây ta nêu lên một số ứng dụng về việc tìm số dư trong phép chia một lũy thừa cho một số đã cho và nói riêng là chứng minh sự chia hết.

Ví dụ 3.1. Tìm số dư trong phép chia 109345 cho 14. Lời giải.

Bởi vì 109 ≡ −3 (mod 14) nên 109345 ≡(−3)345 (mod 14).

ƯCLN(-3, 14) = 1, áp dụng định lý Euler ta có (−3)ϕ(14) ≡ 1 (mod 14). Nhưng ϕ(14) = 6 nên (−3)6 ≡ 1 (mod 14), hơn nữa 345 = 6.57 + 3 cho nên:(−3)345 = [(−3)6]57(−3)3 ≡ −27 (mod 14)và từ −27 ≡1 (mod 14)

Ta được: 109345 ≡ 1 (mod 14).

Vậy số dư trong phép chia 109345 cho 14 là 1.

Ví dụ 3.2. Chứng minh rằng với nlà một số tự nhiên, ta có: 234n+1+ 3...11. Lời giải. Ta có ϕ(11) = 10, ϕ(10) = 4.

+ Nên ta có 34 =≡ 1 (mod 10) do đó 34n+1 ≡ 3 (mod 10). Vậy ắt có số tự nhiên k sao cho 34n+1 = 10k+ 3 .

+ ƯCLN(2, 11) = 1 nên ta có 210 =≡1 (mod 11) do đó 234n+1 = 210k+3 = 23 (mod 11). Vậy 234n+1 + 3 chia hết cho 11.

Ví dụ 3.3. Tìm hai chữ số tận cùng bên phải khi viết số 21954 trong hệ thập phân.

Lời giải. Thực chất của bài toán là tìm số dư r trong phép chia 21954

cho 100, nghĩa là tìm số tự nhiên r thỏa mãn:

21954 ≡ r (mod 100), 0 ≤ r < 100.

Ta thấy ƯCLN(2, 100) = 2 nên ta chưa áp dụng định lý Euler trực tiếp được. Bởi vì (21954,100) = 4 nên ta đặt r = 4x và bài toán được chuyển

về tìm số dư x trong phép chia 21952 cho 25. Từ ƯCLN(2, 25) = 1, theo định lý Euler ta có:

2ϕ(25) ≡ 1 (mod 25) nghĩa là 220 ≡ 1 (mod 25).

Nhưng 1952 = 20.97 + 12 nên 21952 = (220)97212 ≡ 212 (mod 25) suy ra

21952 ≡ 21 (mod 25). Bằng cách nhân cả hai vế và môđun của đồng dư thức cuối cùng này với 4 ta được: 21954 ≡84 (mod 100).

Vậy hai chữ số tận cùng bên phải khi viết số 21954 trong hệ thập phân là 84.