Question

[Phạm Đỗ Thành Hưng]

Chứng minh rằng: 25x11^200+ 2^506 chia hết cho 89

Answer 1

[Phạm Tuấn Kiệt]

Bước 1: Áp dụng định lý Fermat Định lý Fermat nói rằng nếu 𝑝 p là một số nguyên tố và 𝑎 a không chia hết cho 𝑝 p, thì: 𝑎 𝑝 − 1 ≡ 1 ( m o d 𝑝 ) a p−1 ≡1(modp) Trong trường hợp này, 𝑝 = 89 p=89, nên theo định lý Fermat: 𝑎 88 ≡ 1 ( m o d 89 ) a 88 ≡1(mod89) với mọi 𝑎 a không chia hết cho 89. Bước 2: Giải quyết 1 1 200 ( m o d 89 ) 11 200 (mod89) Ta cần tính 1 1 200 m o d     89 11 200 mod89. Theo định lý Fermat, ta có: 1 1 88 ≡ 1 ( m o d 89 ) 11 88 ≡1(mod89) Do đó, ta có thể viết: 1 1 200 = 1 1 88 ⋅ 2 + 24 = ( 1 1 88 ) 2 ⋅ 1 1 24 ≡ 1 2 ⋅ 1 1 24 ≡ 1 1 24 ( m o d 89 ) 11 200 =11 88⋅2+24 =(11 88 ) 2 ⋅11 24 ≡1 2 ⋅11 24 ≡11 24 (mod89) Vậy giờ ta chỉ cần tính 1 1 24 m o d     89 11 24 mod89. Để tính 1 1 24 m o d     89 11 24 mod89, ta có thể sử dụng phương pháp lũy thừa nhanh. Trước tiên ta tính các lũy thừa của 11 modulo 89: 1 1 2 = 121 ≡ 32 ( m o d 89 ) 11 2 =121≡32(mod89) 1 1 4 = ( 1 1 2 ) 2 = 3 2 2 = 1024 ≡ 49 ( m o d 89 ) 11 4 =(11 2 ) 2 =32 2 =1024≡49(mod89) 1 1 8 = ( 1 1 4 ) 2 = 4 9 2 = 2401 ≡ 9 ( m o d 89 ) 11 8 =(11 4 ) 2 =49 2 =2401≡9(mod89) 1 1 16 = ( 1 1 8 ) 2 = 9 2 = 81 ( m o d 89 ) 11 16 =(11 8 ) 2 =9 2 =81(mod89) Vậy: 1 1 24 = 1 1 16 ⋅ 1 1 8 ≡ 81 ⋅ 9 = 729 ≡ 18 ( m o d 89 ) 11 24 =11 16 ⋅11 8 ≡81⋅9=729≡18(mod89) Vậy, 1 1 200 ≡ 1 1 24 ≡ 18 ( m o d 89 ) 11 200 ≡11 24 ≡18(mod89). Bước 3: Giải quyết 2 506 ( m o d 89 ) 2 506 (mod89) Tiếp theo, ta tính 2 506 m o d     89 2 506 mod89. Theo định lý Fermat, ta có: 2 88 ≡ 1 ( m o d 89 ) 2 88 ≡1(mod89) Vậy: 2 506 = 2 88 ⋅ 5 + 78 = ( 2 88 ) 5 ⋅ 2 78 ≡ 1 5 ⋅ 2 78 ≡ 2 78 ( m o d 89 ) 2 506 =2 88⋅5+78 =(2 88 ) 5 ⋅2 78 ≡1 5 ⋅2 78 ≡2 78 (mod89) Vậy giờ ta chỉ cần tính 2 78 m o d     89 2 78 mod89. Tương tự như trước, ta tính các lũy thừa của 2 modulo 89: 2 2 = 4 2 2 =4 2 4 = 16 2 4 =16 2 8 = 1 6 2 = 256 ≡ 78 ( m o d 89 ) 2 8 =16 2 =256≡78(mod89) 2 16 = 7 8 2 = 6084 ≡ 62 ( m o d 89 ) 2 16 =78 2 =6084≡62(mod89) 2 32 = 6 2 2 = 3844 ≡ 12 ( m o d 89 ) 2 32 =62 2 =3844≡12(mod89) 2 64 = 1 2 2 = 144 ≡ 55 ( m o d 89 ) 2 64 =12 2 =144≡55(mod89) Vậy: 2 78 = 2 64 ⋅ 2 8 ⋅ 2 4 ≡ 55 ⋅ 78 ⋅ 16 ( m o d 89 ) 2 78 =2 64 ⋅2 8 ⋅2 4 ≡55⋅78⋅16(mod89) Ta tính từng bước: 55 ⋅ 78 = 4290 ≡ 22 ( m o d 89 ) 55⋅78=4290≡22(mod89) 22 ⋅ 16 = 352 ≡ 80 ( m o d 89 ) 22⋅16=352≡80(mod89) Vậy, 2 506 ≡ 2 78 ≡ 80 ( m o d 89 ) 2 506 ≡2 78 ≡80(mod89). Bước 4: Tổng kết Bây giờ ta có: 25 ⋅ 1 1 200 + 2 506 ≡ 25 ⋅ 18 + 80 ( m o d 89 ) 25⋅11 200 +2 506 ≡25⋅18+80(mod89) 25 ⋅ 18 = 450 ≡ 1 ( m o d 89 ) 25⋅18=450≡1(mod89) 1 + 80 = 81 ( m o d 89 ) 1+80=81(mod89) Vậy 25 ⋅ 1 1 200 + 2 506 ≡ 81 ( m o d 89 ) 25⋅11 200 +2 506 ≡81(mod89). Do đó, 25 ⋅ 1 1 200 + 2 506 25⋅11 200 +2 506 không chia hết cho 89.