A. Lý thuyết
I. Các định nghĩa
1. Định nghĩa 1
Cho n > 1 và a là một số nguyên dương, (a, n) = 1. Số nguyên dương k nhỏ nhất thỏa mãn ak ≡ 1 (mod n) được gọi là cấp của a modulo n.
Kí hiệu k = ordn(a).
2. Định nghĩa 2
Cho n > 1 và a là một số nguyên dương, (a, n) = 1. Nếu (n) = ordn(a) thì a được gọi là một căn nguyên thủy modulo n.
Nhận xét: Từ định nghĩa trên ta dễ dàng suy ra
+) Nếu a là căn nguyên thủy ( modn) thì mọi số cùng lớp với a theo (modn) đều là căn nguyên thủy (modn).
II. Các định lý
1. Định lý 1
Cho a, n thỏa mãn n > 1, (a, n) = 1. Khi đó
ax ≡ 1 (mod n) x ordn (a).
Chứng minh
Giả sử ax ≡ 1 (mod n)
Đặt k = ordn (a)
Theo thuật toán Euclid ta có
x = kq + r, 0 ≤ r < k
Khi đó 1 ≡ ax ≡ (ak)qar ≡ ar (mod n)
Suy ra ar ≡ 1 (mod n) r = 0 (theo định nghĩa)
Vậy x k.
Chiều ngược lại hiển nhiên.
Hệ quả
Cho a, n thỏa mãn n > 1, (a, n) = 1. Khi đó
(n) ordn (a).
2. Định lí 2
Nếu a là căn nguyên thủy (mod n) thì tập A = {1, a, a2,…,ah-1} là hệ thặng dư thu gọn (mod n) (lúc này h = (n))
3. Định lí 3
Nếu p là một số nguyên tố thì có đúng (p - 1) căn nguyên thủy (mod p)
4. Định lít 4
Nếu p là một số nguyên tố lẻ và a là một căn nguyên thủy (mod p2) thì a cũng là căn nguyên thủy (mod pn) với n 3.
5. Định lý về sự tồn tại căn nguyên thủy
Cho m là một số nguyên, m > 1 khi đó m có căn nguyên thủy khi và chỉ khi m có một trong 4 dạng sau: 2, 4, p, 2p (trong đó p là 1 số nguyên tố lẻ)
(Phần chứng minh các định lí trên, xin nhường cho bạn đọc, sau đây là ứng dụng của chúng trong các bài toán số học)
B. Các ví dụ
Ví dụ 1 (6th IMO )
a) Tìm tất cả các số nguyên dương n sao cho 2n – 1 7.
b) Chứng minh rằng với mọi số nguyên dương n thì 2n + 1 7.
Lời giải
a) Ta có ord7(2) = 3 vì 21 ≡ 2 (mod 7), 22 ≡ 4 (mod 7), 23 ≡ 1 (mod 7)
Do đó 2n ≡ 1 (mod 7) n 3 n = 3k với k nguyên dương.
b) Giả sử tồn tại n nguyên dương sao cho 2n ≡ - 1(mod 7)
Suy ra 22n ≡ 1 (mod 7) 2n 3 n 3
Mà n 3 thì 2n ≡ 1 (mod 7)
Từ đó có điều phải chứng minh.
Ví dụ 2 (IMO Sorlist 2006) Tìm tất cả các cặp số nguyên dương x, y thỏa mãn
.
Lời giải
Giả sử p không đồng dư với 1 modulo 7, và là ước nguyên tố của
Đặt k = ordx(p)
Khi đó
x7 ≡ 1 (mod p) 7 k
Theo định lý Fermat nhỏ thì p – 1 k
Mà p không đồng dư với 1 modulo 7 nên (7, p - 1) = 1. Từ đó suy ra k = 1.
Hay x1 ≡ 1 (mod p)
Lại có
0 ≡ x6 + x5 + ... + 1 ≡ 7 (mod p) p = 7.
Như vậy nếu m | thì m ≡ 0 (mod 7) hoặc m ≡ 1 (mod 7).
Vì
= (y - 1)(y4 + y3 + ... + 1) y – 1 |
y ≡ 1, 2 (mod 7) y4 + y3 + ... + 1 ≡ 5, 3 (mod 7) ( vô lí)
Vậy không tồn tại x, y thỏa mãn yêu cầu bài toán.
Ví dụ 3. Cho p là số nguyên tố dạng 4k + 1. Giả sử rằng 2p + 1 cũng là số nguyên tố. Chứng minh rằng không tồn tại số tự nhiên k sao cho k < 2p và 2k ≡ 1 (mod 2p + 1).
Lời giải
Giả sử rằng có số tự nhiên k như vậy.
Đặt t = ord2p + 1 (2) 2t ≡ 1 (mod 2p + 1) t | (2p + 1) – 1 = 2p.
Theo bài ta có
2k ≡ 1 (mod 2p + 1) t | k
Mà k < 2p suy ra t = 1 hoặc t = 2 hoặc t = p.
Do p là số nguyên tố dạng 4k + 1 nên p ≥ 5 nên t ≠ 1, t ≠ 2 t = p.
Suy ra
2p + 1 ≡ 2 (mod 2p + 1)
Ta có điều này là không thể vì 2p + 1 ≡ 3 (mod 8).
Vậy có điều phải chứng minh.
Ví dụ 4. Cho p là một số nguyên tố. Chứng minh rằng tồn tại một số nguyên tố q sao cho với mọi số nguyên dương n ta có
np – p q.
Lời giải 1 (Sử dụng cấp phần tử)
Ta có
Nếu tất cả các ước nguyên tố của đều đồng dư với 1 (mod p2) thì
≡ 1 (mod p2), vô lý.
Vậy tồn tại ước nguyên tố q của sao cho q ≠ 1 (mod p2).
Ta sẽ chứng minh số q như vậy thỏa mãn bài toán.
Trước tiên, ta thấy rằng
+) Nếu p – 1 q thì p ≡ 1 (mod q) pp ≡ 1 (mod q)
+) Nếu p – 1 q thì (p – 1, q) = 1
Mà q pp – 1 q pp ≡ 1 (mod q).
Vậy ta luôn có pp ≡ 1 (mod q).
Giả sử rằng tồn tại n nguyên dương sao cho
np ≡ p (mod q)
Đặt k = ordq(n)
Khi đó k | p2
+) Nếu k = 1 n1 ≡ 1 (mod q) p ≡ 1 (mod q)
pp – 1 + pp – 2 + … + 1 ≡ p (mod q)
Mà q | = pp – 1 + pp – 2 + … + 1 p ≡ 0 (mod q) vô lí
+) Nếu k = p p ≡ np ≡ 1 (mod q) p ≡ 1 (mod q), theo chứng minh trên, trường hợp này cũng không xảy ra.
+) Nếu k = p2 p2 | (q) = q – 1 q ≡ 1 (mod p2), không thỏa mãn theo cách chon q.
Vậy có điều phải chứng minh.
Lời giải 2. (Sử dụng căn nguyên thủy)
Ví dụ 5. Cho thoả mãn 3n – 1 n . Chứng minh rằng n là số chẵn.
Lời giải
Do suy ra n ≥ 2. Gọi p là ước nguyên tố bé nhất của n.
Đặt h = ord3(p) .
Do
(mod p) p – 1 h p > h và n h
Mà p là ước nguyên tố nhỏ nhất của n suy ra h = 1
Vậy 3 ≡ 1 (mod p) 2 ≡ 0 (mod p) p = 2 n chẵn.
Ví dụ 6. Cho p là số nguyên tố lẻ, q và r là các số nguyên tố thỏa mãn
.
Chứng minh rằng: hoặc .
Lời giải
Đặt
Theo tính chất về cấp suy ra h | p - 1
Ta có
Suy ra
Nếu h = 2 thì q2 ≡ 1 (mod p) q2 – 1 p.
Nếu thì
Vậy có điều phải chứng minh.
Ví dụ 7. Tìm tất cả các bộ (b, q, r) nguyên tố thỏa mãn
p qr +1, q rp +1, r pq +1
Lời giải
Rõ ràng các nguyên tố p, q, r phải khác nhau
Giả sử p, q, r > 2
Theo kết quả của bài tập 6, ta có 2r | p – 1 hoặc p | q2 - 1
+) Nếu 2r | p – 1 thì p ≡ 1 (mod r) 0 ≡ pq + 1 ≡ 2 (mod r) r = 2 (loại)
+) Vậy p | q2 – 1
Xét p q - 1 thì q ≡ 1 (mod p) 0 ≡ qr + 1 ≡ 2 (mod p)
p = 2 (loại) p q + 1 mà q + 1 chẵn, p lẻ p .
Tương tự: q , r
p + q + r + +
p + q + r 3 (vô lý)
Vậy phải có ít nhất một số bằng 2. Giả sử p = 2
q, r lẻ và q r2 + 1 và r 2q +1
Ta có ordr¬ (2) 2q
Nếu ordr (2) q q r - 1 (do ordr (2) r-1)
q (r2 + 1) - (r2-1) = 2 q = 2 (loại)
Vậy ordr (2) 2 r 22 - 1 hay r 3 r = 3
q 10 q = 5
Vậy bộ (p, q, r) = (2, 5, 3) ; (3, 2, 5) . (5, 3, 2) là các bộ thỏa mãn đầu bài.
Ví dụ 8. Cho số nguyên và số nguyên dương n. Nếu p là ước nguyên tố lẻ của thì
Lời giải
Do p là ước của nên a p.
Theo giả thiết ta có
Đặt h = ordp(a) suy ra 2n + 1 h và 2n h h = 2n + 1.
Từ đó có điều phải chứng minh.
Ví dụ 9. Cho p là số nguyên tố lẻ thỏa mãn p | ( ). Chứng minh rằng
p ≡ 1 (mod 2n + 1).
Lời giải
Gọi h là cấp của a (mod p)
Ta có
Suy ra h | 2n + 1 mà h không là ước của 2n nên h = 2n + 1
Do h | p – 1 nên p ≡ 1 (mod h) hay p ≡ 1 (mod 2n + 1)
Ví dụ 10. Cho p là một số nguyên tố. dãy số (un) được xác định như sau
un ≡ nn (mod p), un {0, 1, ..., p - 1}
Chứng minh rằng dãy (un) tuần hoàn và tìm chu kì nhỏ nhất của dãy đó.
Lời giải
Ta sẽ chứng minh dãy (un) tuần hoàn với chu kì nhỏ nhất là p(p - 1).
Thật vậy, ta có
un + kp(p - 1) = (n + kp(p - 1))n + kp(p - 1) ≡ nn ≡ un (mod p)
Vậy un + kp(p - 1)= un với mọi k nên dãy trên là tuần hoàn.
Gọi T là chu kì của dãy trên, ta cần chứng minh T p(p - 1)
Ta có (n + T)n + T ≡ nn (mod p) với mọi n
Chon n ≡ 0 (mod p) Tn + T ≡ 0 (mod p) T ≡ 0 (mod p)
Mặt khác, ta cũng có
nn ≡ (n + pT)n + pT (mod p) ≡ (n + pT)n.(n + pT)pT (mod p)
Do nn ≡ (n + pT)n (mod p) với mọi n nên khi (n, p) = 1 ta có
1 ≡ (n + pT)pT (mod p).
Chon n là một căn nguyên thủy (mod p), ta có pT p – 1 T p – 1.
Suy ra T p(p - 1) nên T = p(p - 1) là chu kì nhỏ nhất của (un).
Ví dụ 11. Cho p và q là các số nguyên tố sao cho p có dạng 8k 3 và p = 2q+1. là nghiệm của phương trình . Tính tổng
Lời giải
2 không là số chính phương (mod p)
.
Gọi h là cấp của 2 theo mod p .Vậy ta có
do .
+) Nếu (loại)
+) Nếu (loại)
+) Nếu (loại)
+) 2 là căn nguyên thuỷ (mod p)
Suy ra là hệ thặng dư đầy đủ mod p nó là một hoán vị của tập trong Zp
Mà kp + r = r, nên
Ví dụ 12. Cho với n nguyên dương. Chứng minh rằng k là số nguyên tố khi và chỉ khi k là ước của .
Lời giải
Nếu k là ước của thì ta có
-1 (mod k) (1)
3k -1 1 (mod k) (2)
Gọi d là bậc của 3 modulo k
Từ (1) và (2) ta có d | k – 1 nhưng d lại không chia hết
d = k – 1 k là số nguyên tố.
Ngược lại, k là số nguyên tố
Ta có k là số nguyên tố dạng 4l + 1 nên theo luật tương hỗ Gauss ta có
Mà k 2 (mod 3) nên
(do 2 không phải số chính phương mod 3).
Từ đó suy ra
.
đpcm.
C. Bài tập
Bài 1. Chứng minh rằng: n (an - 1) với a, n N*, a 2
Bài 2. Tìm tất cả các số nguyên dương n sao cho 2n – 1 n
Bài 3(Bulgarian – 95). Tìm số các số tự nhiên n > 1 sao cho
a25 – a 0 (mod n)
Với mọi số tự nhiên a.
Bài 4. Tìm tất cả các số nguyên tố p sao cho
Bài 5. Cho m, n là các số nguyên sao cho A = là một số nguyên. Chứng minh rằng A là số lẻ.
Bài 6. Chứng minh rằng 2n + 1 không có ước nguyên tố dạng 8k + 7.
Chứng minh rằng có ít nhất n ước nguyên tố dạng 8k + 3.
Bài 7. Tìm số n nguyên dương nhỏ nhất thỏa mãn: 22005 17n - 1
Bài 8. Tìm tất cả các số nguyên tố p,q thỏa mãn
Bài 9. Tìm tất cả các bộ (b,q,r) nguyên tố thỏa mãn
p qr +1, q rp +1, r pq +1.
Bài 10. Cho số nguyên và số nguyên dương n và p là ước nguyên tố lẻ của . Chứng minh rằng
.
Bài 11. Cho n > 1, n nguyên dương lẻ. Chứng minh rằng
.
.
.
Bài 12. Tìm số nguyên tố p thỏa mãn
.
Bài 13. Tìm tất cả các cặp số nguyên dương (x, y) sao cho
.
No comments:
Post a Comment