Bài tập phương trình đồng dư

BÀI TẬP VỀ PHƯƠNG TRÌNH ĐỒNG DƯ
Bài tập về phương trình đồng dư
Giải phương trình:
Do nên phương trình luôn có nghiệm duy nhất.
Ta tìm một số nguyên k sao cho chia hết cho 12. Chọn
1/ 12x 7 (mod 23)



Vậy số nghiệm của phương trình ban đầu là
2/ 6x 27 (mod 33)
Ta có

Áp dụng tính chất bắc cầu của quan hệ đồng dư
Ta được phương trình tương đương (mod 11)
Chia hai vế cho 2 (vì (2,11) = 1)
3x 1 (mod 11) .
Lấy
Lại có (17,11) =1
phương trình có nghiệm duy nhất x 4 (mod 11)
3/ 17x 13 (mod 11)
4/ Tìm số dư trong phép chia a cho 73 biết rằng
a100
(mod 73), a101
Ta có
a101
69 (mod 73)
(mod 73)
(mod 73)
(mod 73)
(mod 73)
(mod 73) (vì (2,73)=1)
Vậy a chia cho 73 có số dư là 71
2
69 (mod 73)
Lại có a100
2
(mod 73)
5/ CM: Cho p, q là các số nguyên tố khác nhau thì
Ta có
q là số nguyên tố, (p,q)=1, theo định lý Fermat:
1 (mod p)
0 (mod q)

p là số nguyên tố, (p,q)=1, theo định lý Fermat:
(mod q)
0 (mod p)
(1),(2)
(2)
(vì (p,q)=1)
(mod pq)
(mod pq)
q
(1)
p
6/ Chứng minh rằng nếu p là một số nguyên tố lẻ thì ta có
Ta có
suy ra
(1)
suy ra
(2, p+1)=1, (1),(2)

Lại có
(2)
7/ CM: Nếu (a,7)=1 thì a12-1
Vì (a,7)=1 nên theo định lý Fermat, ta có a6
1(mod 7)
0 (mod 7)
8/ Nếu (a, 240)=1 thì a4-1
240=3.5.24
Ta có (a, 240)=1
a không phân tích ra thừa số nguyên tố 2, 3, 5
Ta có

Ta có (a, 240) =1
là số lẻ
2 số lẻ liên tiếp số chẵn
0 (mod 240)