ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- PHAN THỊ MỪNG
THẶNG DƢ TOÀN PHƢƠNG VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2019
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KHOA HỌC ---------------------------
PHAN THỊ MỪNG
THẶNG DƢ TOÀN PHƢƠNG VÀ ỨNG DỤNG
Chuyên ngành: Phƣơng pháp Toán sơ cấp
Mã số: 8 46 01 13
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
GS.TSKH. ĐẶNG HÙNG THẮNG
THÁI NGUYÊN - 2019
iii
Mục lục
Bảng ký hiệu 1
Mở đầu 2
1 Đồng dư và phương trình đồng dư
1.3.1 Định lý Euler 1.3.2 Định lý Fermat
1.1 Đồng dư thức . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Khái niệm đồng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 Tính chất của đồng dư thức 1.2 Hệ thặng dư và lớp thặng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Định lý Euler và định lý Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Phương trình đồng dư một ẩn . . . . . . . . . . . . . . . . . 4 4 4 5 8 9 9 10 10
2 Thặng dư toàn phương
2.1 Thặng dư toàn phương . . . . . . . . . . . . . . . . . . . . . 2.2 Ký hiệu Legendre . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Định luật tương hỗ . . . . . . . . . . . . . . . . . . . . . . . 2.4 Ký hiệu Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . 14 14 15 22 25
3 Một số ứng dụng của thặng dư toàn phương
3.1 Kiểm tra tính chất nguyên tố của số Fermat . . . . . . . . . . 3.2 Khái niệm số giả nguyên tố Euler . . . . . . . . . . . . . . . 3.3 Giải một số bài toán khó trong số học phổ thông . . . . . . . 32 32 33 41
Kết luận 46
Tài liệu tham khảo 47
1
Bảng ký hiệu
(a, b): Ước chung lớn nhất của a và b
[a, b]: Bội chung lớn nhất của a và b
a|b: a là ước của b
a (cid:54) |b: a không là ước của b
[x]: Phần nguyên của số thực x
ai: a1 + ... + an
ai: a1...an
n (cid:80) i=1 n (cid:81) i=1
a ≡ b(modn): a đồng dư với b modulo n
a (cid:54)≡ b(modn): a không đồng dư với b modulo n
ordma: cấp của a modulo m
Fn: Số Fermat thứ n
φ(n): Hàm Euler
(cid:19) : Ký hiệu Legendre
(cid:17) : Ký hiệu Jacobi (cid:18)a p (cid:16) a n
2
Mở đầu
Lý thuyết thặng dư - lý thuyết đặc biệt quan trọng trong số học và đã được nhiều nhà Toán học nghiên cứu, vận dụng trong việc giải nhiều bài toán hay, khó và có ứng dụng thực tế.
Trong các kì thi Olympic Toán học ở Việt Nam và các nước trên thế giới thì lý thuyết thặng dư là phần được quan tâm đáng kể, vì thế việc có những hiểu biết ban đầu về thặng dư sẽ giúp ta giải nhiều bài toán khó trong số học một cách nhẹ nhàng, ngắn gọn và đẹp.
Tuy nhiên, trong nhà trường phổ thông thì thời lượng giảng dạy cho phần lý thuyết thặng dư chưa nhiều nên học sinh thường thấy phần kiến thức này rất khó, vượt ra hiểu biết của các em. Vì vậy để giúp bản thân có những hiểu biết sâu sắc hơn về lý thuyết thặng dư, phục vụ tốt hơn cho công tác bồi dưỡng học sinh giỏi, tôi chọn đề tài "Thặng dư toàn phương và ứng dụng" để nghiên cứu.
Ngoài phần mở đầu và kết luận, nội dung chính của luận văn được trình
bày trong ba chương:
Chương 1. Đồng dư và phương trình đồng dư
1.1. Đồng dư thức 1.2. Hệ thặng dư và lớp thặng dư 1.3. Định lý Euler và định lý Fermat 1.4. Phương trình đồng dư một ẩn
Chương 2. Thặng dư toàn phương
2.1. Thặng dư toàn phương 2.2. Ký hiệu Legendre 2.3. Định luật tương hỗ 2.4. Ký hiệu Jacobi
3
Chương 3. Một số ứng dụng của thặng dư toàn phương
3.1. Kiểm tra tính chất nguyên tố của số Fermat 3.2. Khái niệm số giả nguyên tố Euler 3.3. Giải một số bài toán khó trong Số học phổ thông
Để hoàn thành bản luận văn này, tôi xin được bày tỏ lòng biết ơn sâu sắc tới GS. TSKH Đặng Hùng Thắng, người thầy nhiệt huyết đã truyền thụ kiến thức, đã chỉ ra hướng đề tài và tận tình hướng dẫn trong suốt quá trình làm luận văn. Đồng thời, tôi xin chân thành cảm ơn các thầy, cô phản biện đã dành thời gian đọc và đóng góp những ý kiến quý báu cho bản luận văn này.
Tôi xin chân thành cảm ơn toàn thể các thầy cô trong Khoa Toán - Tin, Trường Đại học Khoa học - Đại học Thái Nguyên đã tận tình hướng dẫn, truyền đạt kiến thức trong suốt thời gian theo học, thực hiện và hoàn thành luận văn. Qua luận văn này, tôi cũng muốn gửi lời cảm ơn tới gia đình, bạn bè đã luôn động viên, giúp đỡ tôi trong thời gian làm luận văn.
Mặc dù đã có nhiều cố gắng hoàn thiện luận văn bằng tất cả sự nhiệt tình và năng lực của mình. Tuy nhiên, luận văn không thể tránh khỏi những thiếu sót, tôi rất mong nhận được những đóng góp quý báu của thầy cô và các bạn.
Thái Nguyên, ngày 29 tháng 12 năm 2019
Tác giả luận văn
Phan Thị Mừng
4
Chương 1
Đồng dư và phương trình đồng dư
1.1 Đồng dư thức
1.1.1 Khái niệm đồng dư
Cho trước số tự nhiên m lớn hơn 1. Ta nói các số nguyên a, b đồng dư với nhau theo modulo m nếu khi chia a và b cho m ta được cùng một số dư. Kí hiệu:
a ≡ b(modm)
(1.1)
Nói cách khác, a đồng dư với b theo modulo m nếu a và b biểu diễn được
a = pm + r b = qm + r (0 ≤ r < m)
dưới dạng:
a ≡ b(modm)
Từ đó suy ra:
m/a − b.
khi và chỉ khi
a = b + mt.
khi và chỉ khi tồn tại số nguyên t sao cho
Hệ thức (1.1) được gọi là một đồng dư thức.
5
1.1.2 Tính chất của đồng dư thức
• Nếu
a) • a ≡ a(modm)∀a.
a ≡ b(modm) b ≡ c(modm)
• Nếu
thì a ≡ c(modm)
a1 ≡ b1(modm) a2 ≡ b2(modm)
thì a1 ± a2 ≡ b1 ± b2(modm)
Chứng minh. Ta chỉ chứng minh với phép toán cộng, phép trừ hoàn
toàn tương tự.
a1 = b1 + mt1 a2 = b2 + mt2
Từ giả thiết ta có:
(a1 + a2) = (b1 + b2) + m(t1 + t2)
Cộng từng vế của hai đẳng thức ta có:
a1 + a2 ≡ b1 + b2(modm).
Chứng tỏ
Từ tính chất này ta suy ra:
a + c ≡ b(modm)
* Có thể thêm, bớt cùng một số ở hai vế của một đồng dư thức. Nghĩa là: Nếu a ≡ b(modm) thì a + c ≡ b + c(modm) với c là số nguyên tùy ý. * Có thể chuyển vế (phải đổi dấu) các số hạng của một đồng dư thức. Nghĩa là:
a ≡ b − c(modm)
khi và chỉ khi
a ≡ b(modm)
* Có thể thêm, bớt một vế của đồng dư thức một bội số của m. Nghĩa là:
a + tm ≡ b(modm)
thì
a1 ≡ b1(modm) a2 ≡ b2(modm)
b) Nếu
a1.a2 ≡ b1.b2(modm)
thì
6
a1 = b1 + mt1 a2 = b2 + mt2 (t1, t2 ∈ Z)
Chứng minh. Từ giả thiết ta có:
a1.a2 ≡ b1.b2 + mT
Nhân từng vế của hai đẳng thức ta được:
⇒ a1.a2 ≡ b1.b2(modm)
trong đó T là một số nguyên.
Từ tính chất này ta có thể suy ra các tính chất sau: * Có thể nhân cả hai vế của một đòng dư thức với cùng một số nguyên. Chính xác hơn:
Nếu a ≡ b(modm) thì ak ≡ bk(modm)
* Có thể nâng lên lũy thừa nguyên dương hai vế của một đồng dư thức. Tức là:
Nếu a ≡ b(modm) thì an ≡ bn(modm) trong đó n nguyên dương bất kì.
a = a1.a2.
c) Đặc biệt khi m = p là số nguyên tố,
a ≡ 0(modp)
Ta có khẳng định sau:
khi và chỉ khi:
(cid:20) a1 ≡ 0(modp) a2 ≡ 0(modp)
⇔
a ≡ 0(modp) ⇔ p/a ⇔ p/a1a2 (cid:20) p/a1 p/a2
⇔
Chứng minh.
(cid:20) a1 ≡ 0(modp) a2 ≡ 0(modp)
7
=
(modm)
a d
b d
d) Nếu a ≡ b(modm), d/a, d/b, (d, m) = 1 thì
a ≡ b(modm) ⇒ m/a − b ⇒ m/d(a1 − b1),
Chứng minh. Giả sử a = a1d, b = b1d. Ta có:
mà (d, m) = 1 nên m/a1 − b1. ⇒ a1 ≡ b1(modm).
e) a ≡ b(modm) khi và chỉ khi ak ≡ bk(modmk) trong đó k nguyên
dương bất kì.
a ≡ b(modm) ⇔ a = b + mt ⇔ ak = bk + mkt ⇔ ak ≡ bk(modmk)
Chứng minh.
g) Nếu thì a ≡ b(modm) trong đó m = [m1, m2] (cid:26) a ≡ b(modm1) a ≡ b(modm2)
Chứng minh. Từ giả thiết ta có:
(cid:26) m1/a − b m2/a − b
tức là a − b là bội chung của m1 và m2.
m/a − b ⇒ a ≡ b(modm)
Theo định nghĩa bội chung nhỏ nhất ta có
d > 1.
h) Nếu a ≡ b(modm) thì a ≡ b(modd) trong đó d là ước số của m với
a ≡ b(modm) ⇒ m/a − b,
Chứng minh.
8
d/hm ⇒ d/a − b. ⇒ a ≡ b(modd).
mà
k) Nếu a ≡ b(modm) thì tập hợp các ước số chung của a, m trùng với
tập hợp các ước số chung của b, m. Đặc biệt (a, m) = (b, m).
a ≡ b(modm).
1.2 Hệ thặng dư và lớp thặng dư
• Xét m là một số nguyên dương lớn hơn 1. Ta có mỗi số nguyên a đều viết được duy nhất dưới dạng a = qm + r, với 0 ≤ r ≤ m − 1. Với mỗi r(0 ≤ r ≤ m − 1), tập hợp Ar tất cả các số nguyên khi chia cho m có cùng số dư r được gọi là lớp thặng dư modulo m và mỗi phần tử của Ar được gọi là một thặng dư modulo m.
Chứng minh. Tính chất này trực tiếp suy ra từ định nghĩa
Ar = Z,
m−1 (cid:83) r=0
Ai ∩ Aj = φ, với mọi i (cid:54)= j, 0 ≤ i, j ≤ m − 1.
• Trong mỗi lớp thặng dư modulo m lấy một thặng dư đại diện.
Vì mỗi số nguyên a, có duy nhất q và r với 0 ≤ r ≤ m − 1 sao cho a = qm + r, nên a thuộc và chỉ thuộc duy nhất một lớp thặng dư modulo m là Ar. Hơn nữa hợp tất cả các lớp thặng dư modulo m chính là tập hợp Z các số nguyên. Nghĩa là
H = {0, 1, ..., m − 1}
Tập hợp m phần tử đó được gọi là một hệ thặng dư đầy đủ modulo m. Nói cách khác, hệ thặng dư đầy đủ modulo m là tập hợp m số nguyên đôi một không đồng dư modulo m. Đặc biệt hệ
được gọi là hệ thặng dư đầy đủ modulo m không âm nhỏ nhất.
a = q1m + r, b = q2m + r(q1, q2 ∈ Z).
Nhận xét 1.2.1. Tất cả các số nguyên thuộc một lớp thặng dư modulo m có cùng ước chung lớn nhất với m. Thật vậy, giả sử a, b ∈ Ar, tức là
9
(a, m) = (q1m + r, m) = (r, m) = (q2m + r, m) = (b, m)
• Bây giờ đặt ϕ(m) là số các số tự nhiên nhỏ hơn m và nguyên tố với m. Theo nhận xét ở trên có đúng ϕ(m) lớp thặng dư, trong đó mọi thặng dư đều nguyên tố với m. Trong mỗi lớp thặng dư đó lấy một thặng dư đại diện, ta được một hệ thặng dư thu gọn modulo m. Nói cách khác hệ thặng dư thu gọn modulo m là tập hợp gồm ϕ(m) số nguyên, nguyên tố cùng nhau với m và đôi một không đồng dư với nhau modulo m. Nếu tập hợp ϕ(m) phần tử này được chọn từ hệ thặng dư đầy đủ modulo m không âm nhỏ nhất ta được hệ thặng dư thu gọn không âm nhỏ nhất modulo m.
1.3 Định lý Euler và định lý Fermat
Khi đó
1.3.1 Định lý Euler
aϕ(m) ≡ 1(modm)
Nếu m > 1 và (a, m) = 1 thì
Chứng minh. Cho x chạy qua hệ thặng dư thu gọn không âm nhỏ (cid:9). Khi đó ax cũng chạy qua một hệ thặng dư thu gọn. (cid:9) là các thặng dư không âm nhỏ nhất cùng lớp với
ar1 ≡ s1(modm) ar2 ≡ s2(modm) ... arϕ(m) ≡ sϕ(m)(modm)
nhất: (cid:8)r1, r2, ..., rϕ(m) Giả sử (cid:8)s1, s2, ..., sϕ(m) ax1, ax2, ..., axϕ(m). Ta có:
aϕ(m)r1r2...rϕ(m) ≡ s1s2...sϕ(m)(modm)
Nhân từng vế các đồng dư thức ta được:
Vì (cid:8)r1, r2, ..., rϕ(m) (cid:9) và (cid:8)s1, s2, ..., sϕ(m)
aϕ(m) ≡ 1(modm)
(cid:9) cùng là hệ thặng dư thu gọn không âm nhỏ nhất nên chúng chỉ khác nhau về thứ tự. Đồng thời mỗi số trong đó đều nguyên tố với m. Chia hai vế của đồng dư thức nhận được cho tích r1, r2, ..., rϕ(m) ta được:
Xét trường hợp đặc biệt của định lý Euler khi m là số nguyên tố và a
không chia hết cho m. Khi đó ta có định lý Fermat.
10
1.3.2 Định lý Fermat
ap−1 ≡ 1(modp)
Nếu p là số nguyên tố và a không chia hết cho p thì:
Bằng cách nhân cả hai vế của đồng dư thức này với a ta được một dạng
ap ≡ a(modp)
khác của định lý Fermat phát biểu như sau:
Với p là số nguyên tố và a là số nguyên bất kì (Để ý rằng khi a chia hết
1.4 Phương trình đồng dư một ẩn
• Đồng dư thức có dạng
f (x) ≡ 0(modm)
cho p định lý hiển nhiên đúng).
• Giải một phương trình đồng dư là tìm tất cả các giá trị của ẩn số để khi thay vào, đồng dư thức bằng số được thỏa mãn. Ta cũng nói giá trị đó nghiệm đúng phương trình đồng dư đang xét.
trong đó f (x) = aoxn + a1xn−1 + ... + an với ao không chia hết cho m, được gọi là phương trình đồng dư bậc n.
Áp dụng các phép biến đổi tương đương đồng dư thức, ta thấy rằng nếu
f (x) ≡ 0(modm)
r nghiệm đúng phương trình đồng dư
thì mọi số cùng lớp thặng dư với r modulo m đều nghiệm đúng phương trình đó.
y ≡ r(modm) ⇒ yi ≡ ri(modm), (i ∈ N) ⇒ an−iyi ≡ an−iri(modm)
Thật vậy: Giả sử y thuộc lớp thặng dư với r:
với mọi 1 ≤ i ≤ n − 1.
Mặt khác an ≡ an(modm) Cộng từng vế n + 1 đồng dư thức ta được:
11
f (y) ≡ f (r)(modm) ⇒ f (y) ≡ 0(modm) Mỗi lớp đồng dư modulo m như vậy được gọi là một nghiệm của phương
(Vì f (r) ≡ 0(modm)).
• Ta có:
f (x) ≡ 0(modm)
trình đồng dư.
f (x) = mt
khi và chỉ khi
f (x) − mt = 0.
hay
Do vậy việc giải phương trình đồng dư f (x) ≡ 0( mod m) tương đương với
f (x) + my = 0.
• Xét phương trình đồng dư
f (x) ≡ 0(modm),
giải một phương trình bất định dạng
trong đó m = m1.m2, (m1, m2) = 1. Theo tính chất g) và h) ở mục 1.1.2, đồng dư thức đang xét tương đương với hệ
(cid:26) f (x) ≡ 0(modm1) f (x) ≡ 0(modm2)
• Xét phương trình
f (x) ≡ 0(modpα), p ∈ P, a ∈ N, α > 1.
Như vậy về nguyên tắc, có thể chuyển việc nghiên cứu các phương trình đồng dư modulo bất kì về việc xét các phương trình đồng dư với modulo là lũy thừa của một số nguyên tố.
Do đó, có thể tìm nghệm của phương trình đồng dư modulo là lũy thừa của một số nguyên tố trong tập hợp các nghiệm của phương trình đồng dư tương tự với modulo là lũy thừa bậc nhỏ hơn của số nguyên tố đó.
x4 + 7x + 4 ≡ 0(mod32)
Ví dụ 1.4.1. Giải phương trình:
12
x4 + 7x + 4 ≡ 0(mod3).
Giải. Xét phương trình
x = 3t + 1.
Dễ thấy phương trình có nghiệm là x ≡ 1(mod3). Tức là
Thay x vào phương trình cần giải và bỏ đi những số hạng chia hết cho 9
6t + 3 ≡ 0(mod9) ⇔ 2t + 1 ≡ 0(mod3) ⇔ t ≡ 1(mod3) ⇔ t = 3k + 1.
ta được
x = 9k + 4,
Kết luận: Vậy nghiệm của phương trình cần giải là
x ≡ 4(mod9).
• Xét phương trình đồng dư modulo nguyên tố
f (x) ≡ 0(modp)
hay
f (x) = (xp − x).g(x) + r(x)
có bậc n > p. Bằng cách chia f (x) cho xp − x ta được các đa thức hệ số nguyên g(x) và r(x) sao cho:
xp − x ≡ 0(modp)
trong đó r(x) có bậc nhỏ hơn p hoặc r(x) = 0. Theo định lý Fermat ta có:
r(x) ≡ 0(modp)
nên phương trình đang xét hoặc tương đương với
là phương trình có bậc nhỏ hơn p hoặc nghiệm đúng với mọi x.
Do đó, để xét một phương trình đồng dư modulo nguyên tố bậc n bất kì,
ta có thể đưa về xét một phương trình có bậc nhỏ hơn p.
13
Chú ý 1.4.2. Nếu phương trình đồng dư có dạng
h(x).g(x) ≡ 0(modp)
(1.2)
(1.2) ⇔
trong đó p là một số nguyên tố, theo tính chất c) mục 1.1.2 ta sẽ có
• Cuối cùng, chỉ cần xét phương trình đồng dư modulo p nguyên tố bậc
n < p:
(cid:20) g(x) ≡ 0(modp) h(x) ≡ 0(modp).
f (x) ≡ 0(modp)
(1.3)
f (x1) ≡ 0(modp).
Giả sử x1 nghiệm đúng phương trình, tức là
f (x) = (x − x1).f1(x) + r
Chia f (x) cho (x − x1) ta được
r = f (x1).
trong đó f1(x) là đa thức hệ số nguyên có bậc nhỏ hơn n và hằng số r được xác định bởi
(x − x1).f (x) ≡ 0(modp) ⇔
Vậy phương trình đang xét tương đương với
(cid:20) x − x1 ≡ 0(modp) f1(x) ≡ 0(modp)
f1(x) ≡ 0(modp),
Ta lại xét tiếp phương trình
trong đó bậc của f1(x) nhỏ hơn bậc của f (x)...
Nhận xét 1.4.3. Sau mỗi lần chia bậc của phương trình lại nhỏ đi và số nghiệm của phương trình nhiều nhất là bằng số bậc.
14
Chương 2
Thặng dư toàn phương
2.1 Thặng dư toàn phương
Định nghĩa 2.1.1. Giả sử m là một số dương, chúng ta nói rằng số nguyên dương a là một thặng dư bậc hai (còn gọi là thặng dư toàn phương) của m nếu (a, m) = 1 và phương trình đồng dư x2 ≡ a(modm) có nghiệm. Giả sử phương trình đồng dư x2 ≡ a(modm) không có nghiệm, ta nói a không phải là thặng dư bậc hai của m.
Ví dụ 2.1.2. Để xác định số nguyên nào là thặng dư bậc hai của 11, chúng ta tính bình phương của các số nguyên 1, 2, 3, ..., 10. Chúng ta thấy rằng 12 ≡ 102 ≡ 1(mod11), 22 ≡ 92 ≡ 4(mod11), 32 ≡ 82 ≡ 9(mod11), 42 ≡ 72 ≡ 5(mod11), và 52 ≡ 62 ≡ 3(mod11).
Như vậy thặng dư bậc hai của 11 là 1, 3, 4, 5, 9; các số nguyên 2, 6, 7, 8, 10
không phải thặng dư bậc hai của 11.
Lưu ý rằng thặng dư bậc hai của thặng dư nguyên dương của m với k = 2. Chúng ta sẽ chỉ ra rằng nếu p là một số nguyên tố lẻ, thì có chính xác có nhiều thặng dư bậc hai như các phần tử bậc hai của p trong số các số nguyên 1, 2, ..., p − 1. Để chứng minh thực tế này, chúng ta sử dụng bổ đề sau đây.
Bổ đề 2.1.3. Giả sử p là số nguyên tố lẻ và số nguyên không chia hết cho p. Khi đó, phương trình đồng dư x2 ≡ a(modp) hoặc không có nghiệm hoặc chính xác là có hai nghiệm modulo p.
Chứng minh. Nếu x2 ≡ a(modp) là một nghiệm, giả sử x = x0, thì chúng ta có thể dễ dàng chứng minh rằng nghiệm không phù hợp thứ hai. Vì (−x0)2 = x2 0 ≡ a(modp), chúng ta thấy rằng −x0 là một nghiệm. Chúng ta lưu ý rằng x0 (cid:54)≡ −x0( mod p), vì nếu x0 ≡ −x0( mod p), thì chúng ta có 2x0 ≡
15
0 ≡ a(modp) và
0(modp). Điều này là không thể vì p là số lẻ và p (cid:54) |x0 (sin x2 p (cid:54) |a).
1 ≡ a(modp), do đó x2
0 = x2
0 − x2
Để chỉ ra rằng không có nhiều hơn hai nghiệm modulo p, giả sử rằng x = x0 và x = x1 là cả hai nghiệm của phương trình đồng dư x2 ≡ a( mod p). Khi đó ta có x2 1 = (x0 + x1)(x0 − x1) ≡ 0(modp). Vì thế, p|(x0 + x1) hoặc p|(x0 − x1), do đó x1 ≡ −x0(modp) hoặc x1 ≡ x0(modp). Vì thế nếu đó là một nghiệm của phương trình đồng dư x2 ≡ a(modp) đó chính xác là có hai nghiệm.
Định lý 2.1.4. Nếu p là một số nguyên tố lẻ, thì có đúng (p − 1)/2 thặng dư bậc hai của p và (p − 1)/2 không là thặng dư bậc hai của p trong các số nguyên 1, 2, ..., p − 1 .
2.2 Ký hiệu Legendre
Chứng minh. Tìm tất cả các thặng dư bậc hai của p trong các số nguyên 1, 2, ..., p − 1 chúng ta tính toán thặng dư nhỏ nhất modulo p của bình phương của các số nguyên 1, 2, ..., p − 1. Vì có p − 1 để xét và phương trình đồng dư x2 ≡ a(modp) có không hoặc hai nghiệm, phải có chính xác một bình phương để xem xét và vì mỗi thặng dư (p − 1)/2 dư của p trong các số nguyên 1, 2, ..., p − 1. Các số nguyên dương p − 1 − (p − 1)/2 = (p − 1)/2 còn lại nhỏ hơn p − 1 là các giá trị không bậc hai của p. Ký hiệu đặc biệt liên quan đến thặng dư bậc hai được mô tả trong định nghĩa sau:
Định nghĩa 2.2.1. (Ký hiệu Legendre) Giả sử p là số nguyên tố lẻ và a là (cid:19) được định nghĩa như (cid:18)a p số nguyên không chia hết cho p. Ký hiệu Legendre sau:
=
−1 nếu a không là thặng dư bậc hai của p
(cid:19) (cid:26) 1 nếu a là thặng dư bậc hai của p
(cid:18)a p
, a = 1, 2, ..., 10,
(cid:17) Ví dụ 2.2.2. Ví dụ trước cho thấy các ký hiệu Legendre (cid:16) a 11 có các giá trị sau:
=
=
=
=
= 1
(cid:19) (cid:19) (cid:19) (cid:19) (cid:19)
=
=
=
=
= −1
(cid:19) (cid:19) (cid:19) (cid:19) (cid:19)
(cid:18) 1 11 (cid:18) 2 11 (cid:18) 3 11 (cid:18) 6 11 (cid:18) 4 11 (cid:18) 7 11 (cid:18) 5 11 (cid:18) 8 11 (cid:18) 9 11 (cid:18)10 11
16
Định lý 2.2.3. (Tiêu chuẩn của Euler) Giả sử p là số nguyên tố lẻ và để a là số nguyên dương không chia hết cho p. Khi đó
≡ a(p−1)/2(modp).
(cid:19)
(cid:18)a p
= 1. Khi đó, phương trình
(cid:19) Chứng minh. Đầu tiên, giả sử rằng (cid:18)a p
0)(p−1)/2 = xp−1
0 ≡ 1(modp).
đồng dư x2 ≡ a(modp) có một nghiệm, giả sử x = x0. Sử dụng định lý nhỏ của Fermat, chúng ta thấy
a(p−1)/2 = (x2 (cid:19)
= 1, chúng ta biết rằng
= a(p−1)/2(modp).
= −1. Khi đó, phương trình đồng dư
(cid:19) Do đó, nếu (cid:18)a p (cid:18)a p (cid:19) Bây giờ hãy xem xét trường hợp
(p − 1)! ≡ a(p−1)/2(modp).
(cid:18)a p x2 ≡ a( mod p) không có nghiệm. Cho mỗi số nguyên i sao cho 1 ≤ i ≤ p − 1, có một số nguyên j duy nhất có 1 ≤ j ≤ p − 1, sao cho ij ≡ a(modp). Hơn nữa, vì phương trình đồng dư x2 ≡ a(modp) không có nghiệm, chúng ta biết rằng i (cid:54)= j. Do đó, chúng ta có thể nhóm các số nguyên 1, 2, ..., p − 1 thành (p − 1)/2 cặp với mỗi sản phẩm a. Nhân các cặp này với nhau, chúng ta thấy rằng
Vì định lý của Wilson cho chúng ta biết (p − 1)! ≡ −1(modp), chúng ta
−1 ≡ a(p−1)/2(modp). (cid:19)
thấy
= a(p−1)/2(modp).
Trong trường hợp này, chúng ta cũng có (cid:18)a p
=
=
.
= 1.
Định lý 2.2.4. Giả sử p là số nguyên tố lẻ và số nguyên a, b không chia hết cho p. Khi đó: (cid:19) (cid:19) . (cid:18)a p (cid:18) b p (i) Nếu a ≡ b(modp), thì (cid:19) (cid:19) (ii) (cid:18)ab p (cid:19) (cid:18) b p (cid:19) (iii) (cid:18)a p (cid:18)a2 p
17
x2 ≡ b(modp) có một nghiệm. Do đó,
=
≡ a(p−1)/2(mod
(cid:19) (cid:19) . Chứng minh. (i) Nếu a ≡ b(modp), thì x2 ≡ a(modp) có một nghiệm khi và chỉ khi (cid:18)a p (cid:18) b p (cid:19)
≡ b(p−1)/2(modp),
p),
(cid:18)a p (cid:19)
(ii) Theo tiêu chuẩn của Euler, chúng ta biết rằng (cid:18) b p
≡ (ab)(p−1)/2(modp).
(cid:19)
(cid:18)ab p
Do đó,
≡ a(p−1)/2b(p−1)/2 ≡ (ab)(p−1)/2 ≡
(modp).
(cid:19) (cid:19)
(cid:18)a p (cid:19) (cid:18) b p (cid:18)ab p
Vì các giá trị duy nhất có thể có của ký hiệu Legendre là ±1, nên chúng
ta kết luận rằng
=
.
(cid:19) (cid:19)
(cid:18)a p (cid:19) (cid:18) b p (cid:18)ab p
= ±1, từ phần (ii) ta có
(cid:19) (iii) Vì (cid:18)a p
=
= 1
(cid:19) (cid:19)
(cid:18)a2 p (cid:18)a p (cid:19) (cid:18)a p
Phần (ii) của Định lý 2.2.4 có kết quả thú vị sau đây. Tích của hai thặng dư bậc hai là thặng dư bậc hai, hoặc tích của hai thặng dư không bậc hai là thặng dư bậc hai của số nguyên tố, trong khi tích của thặng dư bậc hai và thặng dư không bậc hai là một thặng dư không bậc hai.
Sử dụng tiêu chuẩn của Euler, chúng ta có thể phân loại các số nguyên tố
đó có −1 là thặng dư bậc hai.
Định lý 2.2.5. Nếu p là số nguyên tố lẻ, thì
=
(cid:19) (cid:26) 1
nếu p ≡ 1(mod4) −1 nếu p ≡ −1(mod4) (cid:18)−1 p
Chứng minh. Theo tiêu chuẩn của Euler, chúng ta biết rằng
= (−1)(p−1)/2(modp)
(cid:19)
(cid:18)−1 p
18
(−1)(p−1)/2 = (−1)2k = 1
Nếu p ≡ 1(mod4), thì p = 4k + 1 cho một số nguyên k. Do đó,
= 1. Nếu p ≡ 3(mod4), thì p = 4k + 3 cho một số nguyên k.
(cid:19) Vậy (cid:18)−1 p
(−1)(p−1)/2 = (−1)2k+1 = −1,
Do đó,
= −1.
(cid:19) Như vậy (cid:18)−1 p
a, 2a, 3a, ..., ((p − 1)/2)a lớn hơn hơn p/2, khi đó
= (−1)s.
Bổ đề 2.2.6. (Bổ đề Gauss) Giả sử p là số nguyên tố lẻ và a là số nguyên với (a, b) = 1. Nếu s là số thặng dư dương nhỏ nhất của các số nguyên (cid:19)
(cid:18)a p
Chứng minh. Xét các số nguyên a, 2a, ..., ((p−1)/2)a. Giả sử u1, u2, ..., us,
là thặng dư dương nhỏ nhất của các phần tử lớn hơn p/2 và để v1, v2, ..., vt, là phần dư nhỏ nhất của các số nguyên nhỏ hơn p/2. Vì (ja, p) = 1 với 1 ≤ j ≤ (p − 1)/2, các thặng dư dương nhỏ nhất này nằm trong tập 1,2 ..., p- 1.
(cid:48)s là đồng dư modulo p và không có Rõ ràng không có hai trong số các ui (cid:48)s; nếu một sự đồng dư của một hai trong số các đồng dư modulo p của vi trong hai loại này được thỏa mãn, chúng ta sẽ có ma = na(modp) trong đó m và n đều là các số nguyên dương không vượt quá (p − 1)/2. Vì p (cid:54) |a, điều này ngụ ý rằng m ≡ n(modp) là không thể.
Cho tất cả j chúng ta sẽ chỉ ra rằng, bao gồm tập hợp các số nguyên 1, 2, ..., (p − 1)/2, theo một số thứ tự. Để thấy điều này, chúng ta chỉ cần chỉ ra rằng không có hai số nguyên nào là modulo p đồng dư, vì có đúng (p − 1)/2 số trong tập hợp và tất cả đều là số nguyên dương không vượt quá (p − 1)/2.
Ngoài ra, một trong các số nguyên p − ui không thể đồng dư với vj , vì nếu có như vậy, chúng ta có ma ≡ p − na(modp), do đó ma ≡ −na(modp). Vì p (cid:54) |a, điều này ngụ ý rằng m ≡ −n(modp) không thể vì cả m và n đều nằm trong tập 1, 2, ....(p − 1)/2 .
1, 2, ., (p − 1)/2, theo một thứ tự, chúng ta kết luận rằng
Bây giờ chúng ta biết rằng p−u1, p−u2, ..., p−us, v1, v2, ..., vt là số nguyên
!(modp),
(p − u1)(p − u2)...(p − us)v1v2...vt ≡
(cid:19)
(cid:18)p − 1 2
19
ngụ ý rằng
!(modp).
(−1)su1u2 · · · usv1v2 · · · vt ≡
(cid:19) (2.1) (cid:18)p − 1 2
((p − 1)/2)a, chúng ta cũng biết rằng
Nhưng, vì u1, u2, ..., us, v1, v2, ..., vt là thặng dư nhỏ nhất của a, 2a, ...,
a
u1u2 · · · usv1v2 · · · vt ≡ a · 2a · · ·
(cid:19) (2.2) (cid:18)p − 1 2
p−1 2
= a
!(modp).
(cid:19)
(cid:18)p − 1 2
Do đó, từ (2.1) và (2.2) chúng ta thấy rằng
p−1 2
(−1)sa
! ≡
!(modp).
(cid:19) (cid:19)
(cid:18)p − 1 2 (cid:18)p − 1 2
p−1
(−1)sa
2 ≡ 1(modp).
Vì (p, ((p − 1)/2)!) = 1, sự đồng dư này ngụ ý rằng
p−1
a
2 ≡ (−1)s(modp).
Bằng cách nhân cả hai vế với (−1)s, chúng ta thu đươc
p−1
2 ≡
(modp), nó
(cid:19) Vì tiêu chuẩn của Euler cho chúng ta biết rằng a (cid:18)a p
≡ (−1)s(modp),
tuân theo điều đó (cid:19)
(cid:18)a p
thiết lập bổ đề Gauss.
(cid:19) bổ đề Gauss, chúng Ví dụ 2.2.7. Giả sử a = 5 và p = 11. Để tìm ra (cid:18) 5 11
= (−1)2 = 1.
ta tính toán các thặng dư nhỏ nhất của 1 · 5, 2 · 5, 3 · 5, 4 · 5 và 5 · 5. Đây là 5, 10, 4, 9 và 3, tương ứng. Vì chính xác hai trong số này lớn hơn 11/2, bổ đề (cid:19) Gauss cho chúng ta biết rằng (cid:18) 5 11
Sử dụng bổ đề Gauss, chúng ta có thể mô tả tất cả các số nguyên tố có 2
là thặng dư bậc hai .
20
Định lý 2.2.8. Nếu p là số nguyên tố lẻ, thì
= (−1)(p2−1)/8.
(cid:19)
(cid:18)2 p
Do đó, 2 là thặng dư bậc hai của tất cả các số nguyên tố p ≡ ±1(mod8)
và không là thặng dư bậc hai của tất cả các số nguyên tố p ≡ ±3(mod8) .
Chứng minh. Theo bổ đề Gauss, chúng ta biết rằng nếu s là số thặng
dư nhỏ nhất của các số nguyên
1 · 2, 2 · 2, 3 · 2, ...,
· 2
(cid:19)
(cid:18)p − 1 2
= (−1)s. Vì tất cả các số nguyên này đều nhỏ
(cid:19) lớn hơn p/2, sau đó (cid:18)2 p
hơn p, nên chúng ta chỉ cần đếm những số nguyên lớn hơn p/2 để tìm xem có bao nhiêu thặng dư có ít nhất dương hơn p/2. Số nguyên 2j, trong đó 1 ≤ j ≤ (p − 1)/2, nhỏ hơn p/2 khi j ≤ p/4 . Do đó, có các số nguyên [p/4]
− [p/4] lớn hơn p/2. Do đó, bằng
p − 1 2
trong tập nhỏ hơn p/2. Do đó, có s =
bổ đề của Gauss, chúng ta thấy rằng
p−1
= (−1)
2 −[p/4].
(cid:19)
(cid:18)2 p
− [p/4] ≡ (p2 − 1)/8(mod2).
p − 1 2
Để chứng minh định lý, chúng ta phải chỉ ra rằng
Để thiết lập điều này, chúng ta cần xem xét lớp đồng quy của p modulo 8, vì, như chúng ta sẽ thấy, cả hai mặt của sự đồng dư trên chỉ phụ thuộc vào lớp đồng quy của p modulo 8.
8k ± 1 trong đó k là một số nguyên, sao cho
(p2 − 1)/8 = ((8k ± 1)2 − 1)/8 = (64k2 ± 16k)/8 = 8k2 ± 2k ≡ 0(mod2).
Trước tiên, chúng ta xem xét (p2 − 1)/8. Nếu p ≡ ±1(mod8), thì p =
(p2−1)/8 = ((8k ± 3)2−1)/8 = (64k2±48k+8)/8 = 8k2+6k+1 ≡ 1( mod 2).
Nếu p ≡ ±3(mod8), thì p = 8k ± 3 trong đó k là số nguyên, do đó
21
− [p/4]. Nếu p ≡ 1( mod 8) , sau đó p = 8k + 1
p − 1 2
Bây giờ hãy xem xét
− [p/4] = 4k − [2k + 1/4] = 2k ≡ 0(mod2);
p − 1 2
cho một số nguyên k và
− [p/4] = 4k + 1 − [2k + 3/4] = 2k + 1 ≡ 1(mod2);
p − 1 2
Nếu p ≡ 3(mod8) , thì p = 8k + 3 cho một số nguyên k và
− [p/4] = 4k + 2 − [2k + 5/4] = 2k + 1 ≡ 1(mod2);
p − 1 2
Nếu p ≡ 5(mod8), thì p = 8k + 5 cho một số số nguyên k, và
− [p/4] = 4k + 3 − [2k + 7/4] = 2k + 2 ≡ 0(mod2).
p − 1 2
Nếu p ≡ 7(mod8), thì p = 8k + 7 đối với một số nguyên k, và
− [p/4] và (p2 − 1)/8 cho
p − 1 2
So sánh các lớp đồng dư modulo 2 của
rằng chúng ta luôn có
p − 1 2 số nguyên tố p chúng ta có
= (−1)(p2−1)/8.
(cid:19)
bốn lớp đồng dạng có thể có của số nguyên tố p modulo 8 lẻ, chúng ta thấy − [p/4] ≡ (p2 − 1)/8(mod2). Theo sau với mọi (cid:18)2 p
= 1 nếu p ≡ ±1(mod8), trong khi
= −1 nếu p ≡ ±3(mod
8) .
Từ các tính toán của lớp đồng dư của (p2 − 1)/8(mod2), chúng ta thấy (cid:19) (cid:19) rằng (cid:18)2 p (cid:18)2 p
Ví dụ 2.2.9. Theo Định lý 2.2.8 chúng ta thấy
=
=
=
= 1,
(cid:19) (cid:19) (cid:19) (cid:19)
(cid:18)2 7 (cid:18) 2 17 (cid:18) 2 23 (cid:18) 2 31
trong khi
=
=
=
=
=
= −1.
(cid:19) (cid:19) (cid:19) (cid:19) (cid:19) (cid:19)
(cid:18)2 3 (cid:18)2 5 (cid:18) 2 11 (cid:18) 2 13 (cid:18) 2 19 (cid:18) 2 29
Bây giờ chúng ta trình bày một ví dụ để chỉ ra cách đánh giá các ký hiệu
Legendre.
22
(cid:19) , chúng ta sử dụng một phần (i) của Định Ví dụ 2.2.10. Để đánh giá (cid:18)317 11
lý 2.2.4 để thu được
=
=
= 1,
(cid:19) (cid:19) (cid:19)2
(cid:18)317 11 (cid:18) 9 11 (cid:18) 3 11
kể từ 317 ≡ 9(mod11).
, kể từ khi 89 ≡ −2(mod13), chúng ta có
=
=
= 1 . Kể từ khi 13 ≡ −3(mod8), chúng ta thấy từ Định lý 2.2.8 rằng
(cid:19) (cid:19) Đánh giá (cid:18)89 13 (cid:19) (cid:19) . Vì 13 ≡ 1(mod4), Định lý 2.2.5 cho chúng ta biết (cid:18)89 13 (cid:19) (cid:18) 2 13 (cid:18)−1 13 (cid:19)
= −1. Do đó,
= −1.
(cid:19) (cid:19)
2.3 Định luật tương hỗ
(cid:18)−2 13 (cid:18)−1 13 (cid:18) 2 13 (cid:18)89 13
Giả sử p và q là các số nguyên tố lẻ phân biệt. Giả sử thêm rằng chúng ta biết liệu q có phải là thặng dư bậc hai của p hay không. Chúng ta cũng biết liệu p có phải là thặng dư bậc hai của q không? Câu trả lời cho câu hỏi này đã tìm thấy câu trả lời bằng cách kiểm tra bằng chứng bằng số, nhưng anh ta không chứng minh rằng câu trả lời của mình là đúng. Sau đó, vào năm 1785, Legendre đã điều chỉnh lại câu trả lời của Euler, dưới hình thức trong một định lý được gọi là định luật tương hỗ. Định lý này cho chúng ta biết liệu phương trình đồng dư x2 ≡ q(modp) có nghiệm hay không, một khi chúng ta biết liệu có nghiệm nào của phương trình đồng dư x2 ≡ p(modq).
Định lý 2.3.1. (Định luật tương hỗ) Giả sử p và q là số nguyên tố lẻ. Khi đó
p−1
= (−1)
2 · q−1 2 .
(cid:19)
(cid:18)p q (cid:19) (cid:18)q p
Legendre đã công bố một số chứng minh đề xuất của định lý này. Chứng minh chính xác đầu tiên được tuyên bố là đã khám phá lại kết quả này khi ông 18 tuổi. Gauss dành sự quan tâm đáng kể để tìm kiếm một bằng chứng. Trên thực tế, ông đã viết rằng "trong cả năm, định lý này đã hành hạ tôi và tiếp thu những nỗ lực lớn nhất của tôi cho đến khi cuối cùng tôi có được một bằng chứng." Dựa trên một cách tiếp cận khác việc tìm ra những chứng minh mới và khác nhau về định luật tương hỗ bậc hai đã thách thức các nhà toán
23
học từ lâu. Nhiều chứng minh đáng ngạc nhiên và tuyệt vời đã được tìm thấy. Để cung cấp một ý tưởng sơ bộ về việc có bao nhiêu chứng minh khác nhau được biết đến, một bài báo được xuất bản gọi là "chứng minh thứ 152" về luật tương hỗ bậc hai được cung cấp bởi Gauss, người sau khi tìm thấy một chứng minh, ông đã nghĩ ra thêm bảy chứng minh, mỗi năm cách đây vài năm đã đưa ra những gì đã được thể hiện một cách lịch sự. Trước khi chúng ta chứng minh luật tương hỗ bậc hai, chúng ta sẽ thảo luận về hậu quả của nó và cách nó được sử dụng để đánh giá các ký hiệu Legendre. Trước tiên chúng ta lưu ý rằng số lượng (p − 1)/2 là chẵn khi p ≡ 1(mod4) và lẻ khi p ≡ 3(mod4)
·
q − 1 2
. Do đó, thấy rằng nếu p ≡ 1(mod4) hoặc khi q ≡ 1(mod4),
·
p − 1 2 q − 1 2
p − 1 2
trong khi là số lẻ nếu p ≡ q ≡ 3(mod4). Do đó, chúng ta có
p ≡ 1(mod4)
=
−1 nếu p ≡ q ≡ 3(mod4).
(cid:19) nếu (cid:26) 1 hoặc q ≡ 1(mod4) (hoặc cả hai)
(cid:18)p q (cid:19) (cid:18)q p
(cid:19) (cid:19) Vì các giá trị duy nhất có thể có và là ±1, nên chúng ta thấy (cid:18)p q (cid:18)q p
rằng
p ≡ 1(mod4)
=
(cid:19) nếu hoặc q ≡ 1(mod4) (hoặc cả hai) (cid:19)
−
(cid:19) (cid:18)p q nếu p ≡ q ≡ 3(mod4) (cid:18)q p (cid:18)q p
=
= (cid:18)p q
(cid:19) (cid:19) Điều này có nghĩa là nếu p và q là các số nguyên tố lẻ, thì (cid:18)p q (cid:18)q p (cid:19) trừ khi cả p và q đồng dạng với 3 modulo 4, và trong trường hợp đó,
.
−
(cid:19)
(cid:18)q p
. Theo phần (i) của Định
=
, và từ phần (iii) của Định lý 2.2.4,
=
= 1. Kết hợp các đẳng thức này, chúng ta kết luận
=
(cid:19) (cid:19) đảo bậc hai cho chúng ta biết rằng (cid:18)17 13 (cid:19) (cid:19) lý 2.2.4 chúng ta biết rằng Ví dụ 2.3.2. Cho p = 13 và q = 17. Vì p ≡ q ≡ 1(mod4), định luật nghịch (cid:18)13 17 (cid:18) 4 13 (cid:18)17 13 (cid:19) (cid:19)
= 1.
(cid:18) 22 13 (cid:18) 4 13 (cid:19) rằng theo sau (cid:18)13 17
24
= − (cid:19)
=
Ví dụ 2.3.3. Cho p = 7 và q = 19. Vì p ≡ q ≡ 3(mod4), theo định luật (cid:19) (cid:19) . Từ phần (i) của (cid:18) 7 19 (cid:18)19 7 (cid:19) Định lý 2.2.4, chúng ta thấy rằng . Một lần nữa, sử dụng định (cid:18)5 7
=
(cid:19) (cid:19) . Phần (i) của Định lý 2.2.4 và Định lý 2.2.8, chúng ta biết rằng
= −1. Do đó
= 1.
=
(cid:19) (cid:19) (cid:19)
tương hỗ bậc hai, chúng ta biết rằng (cid:18)19 7 luật tương hỗ bậc hai, kể từ khi 5 ≡ 1(mod4) và 7 ≡ 3(mod4), chúng ta có (cid:18)5 7 (cid:18)7 5 (cid:18)7 5 (cid:18)2 5 (cid:18) 7 19
= (−1)T (a,p),
Bổ đề 2.3.4. Nếu p là số nguyên tố lẻ và a là số nguyên lẻ không chia hết cho p, thì (cid:19)
(cid:18)a p
(p−1)/2 (cid:88)
T (a, p) =
[ja/p].
j=1
(cid:48)s. Bằng cách thêm các
(cid:48)s hoặc vj
trong đó
(p−1)/2 (cid:88)
(p−1)/2 (cid:88)
s (cid:88)
t (cid:88)
Chứng minh. Xét các thặng dư dương nhỏ nhất của các số nguyên a, 2a, ..., ((p − 1)/2)a; Đặt u1, u2, ..., us là những số lớn hơn p/2 và để v1, v2, ..., vt là những số nhỏ hơn p/2. Thuật toán phân chia cho chúng ta biết rằng ja = p[ja/p] + phần còn lại, trong đó phần còn lại là một trong các uj phương trình (p − 1)/2 của loại này, chúng ta thu được
ja =
p[ja/p] +
v(cid:48)
uj +
j.
j=1
j=1
j=1
j=1
(2.3)
(p−1)/2 (cid:88)
s (cid:88)
t (cid:88)
s (cid:88)
t (cid:88)
Như chúng ta đã trình bày trong chứng minh về Bổ đề của Gauss, các số nguyên p − u1, ..., p − us, v1, ..., vt chính xác là các số nguyên 1, 2, ..., (p − 1)/2, theo một số thứ tự. Do đó, tổng hợp tất cả các số nguyên này, chúng ta thu được
j =
(p − uj) +
vj = ps −
uj +
vj.
j=1
j=1
j=1
j=1
j=1
(2.4)
Trừ (2.4) từ (2.3), chúng ta thấy rằng
25
(p−1)/2 (cid:88)
(p−1)/2 (cid:88)
(p−1)/2 (cid:88)
s (cid:88)
ja −
j =
p[ja/p] − ps + 2
uj
j=1
j=1
j=1
j=1
(p−1)/2 (cid:88)
[ja/p],
j=1 (p−1)/2 (cid:88)
s (cid:88)
(a − 1)
j = pT (a, p) − ps + 2
uj.
j=1
j=1
tương đương, vì T (a, p) =
0 ≡ T (a, p) − s(mod2).
Giảm phương trình cuối cùng này modulo 2, vì a và p là số lẻ, mang lại
T (a, p) ≡ s(mod2).
Do đó,
Để hoàn thành chứng minh, chúng ta lưu ý rằng từ Gauss ’lemma
= (−1)s.
(cid:19)
(cid:18)a p
Do đó, vì (−1)s = (−1)T (a,p) , theo sau đó
= (−1)T (a,p).
(cid:19)
2.4 Ký hiệu Jacobi
(cid:18)a p
Trong phần này, chúng ta định nghĩa ký hiệu Jacobi, được đặt theo tên nhà toán học người Đức Carl Jacobi, người đã giới thiệu ký hiệu này. Ký hiệu Jacobi là một khái quát hóa ký hiệu Legendre được nghiên cứu trong hai phần trước. Ký hiệu Jacobi rất hữu ích trong việc đánh giá các ký hiệu Legendre và trong định nghĩa về một loại giả nguyên tố.
(cid:17) được xác định bởi Định nghĩa 2.4.1. Giả sử n là số nguyên dương lẻ với thừa số nguyên tố 1 pt2 n = pt1 2 · · · ptm m và giả sử a là số nguyên tương đối nguyên tố với n. Khi đó, (cid:16) a ký hiệu Jacobi n
a
=
=
· · ·
,
(cid:18) (cid:19) (cid:19)t2 (cid:19)tm (cid:17)
m
1 pt2 pt1
2 · · · ptm
(cid:16) a n (cid:18) a p1 (cid:19)t1(cid:18) a p2 (cid:18) a pm
trong đó các ký hiệu ở phía bên phải của đẳng thức là ký hiệu Legendre.
26
Ví dụ 2.4.2. Từ định nghĩa của ký hiệu Jacobi, chúng ta thấy rằng
=
=
= (−1)2 (−1) = −1,
(cid:19) (cid:19) (cid:19) (cid:18) 2
32 · 5
(cid:18) 2 45 (cid:18)2 3 (cid:19)2 (cid:18)2 5
và
=
=
=
(cid:19) (cid:19) (cid:19) (cid:19) (cid:18) 109
5 · 7 · 11
(cid:18)109 385 (cid:18)4 5 (cid:19) (cid:18)4 7 (cid:19) (cid:18)10 11
=
= (−1)212 (−1) = −1.
(cid:19) (cid:18)109 11 (cid:19)
(cid:18)109 5 (cid:18)2 5 (cid:19) (cid:18)109 7 (cid:19)2 (cid:18)−1 11 (cid:19)2(cid:18)2 7
(cid:17)
(cid:16) a n
(cid:17) Khi n là số nguyên tố, ký hiệu Jacobi giống với ký hiệu Legendre. Tuy nhiên, khi n là hợp số, giá trị của ký hiệu Jacobi cho dù phương trình đồng dư x2 ≡ a(modn) có nghiệm hay không. Chúng ta biết rằng nếu phương trình đồng dư x2 ≡ a(modn) có các nghiệm, thì = 1. Để thấy điều này, (cid:16) a n
m (cid:89)
= 1. Để thấy rằng
=
= 1 . Do đó,
j=1
lưu ý rằng nếu p là ước số nguyên tố của n và nếu phương trình đồng dư x2 ≡ a(modn) có các nghiệm, thì phương trình đồng dư x2 ≡ a(modp) cũng (cid:19) (cid:19)j (cid:17) có các nghiệm. Do đó, (cid:18)a p (cid:16) a n (cid:18) a pj
= 1 khi có các nghiệm x2 ≡ a(modn), hãy để a = 2 và n = 15.
(cid:17) có thể là
= (−1) (−1) = 1. Tuy nhiên, không có các
=
(cid:19) (cid:19) Lưu ý rằng (cid:16) a n (cid:18) 2 15 (cid:18)2 3 (cid:19) (cid:18)2 5
nghiệm cho phương trình đồng dư x2 ≡ 2(mod15), vì các phương trình đồng dư x2 ≡ 2(mod3) và x2 ≡ 2(mod5) không có nghiệm.
Bây giờ chúng ta cho thấy ký hiệu Jacobi có một số tính chất tương tự
như ký hiệu Legendre.
Định lý 2.4.3. Giả sử n là số nguyên dương lẻ và cho a và b là số nguyên tương đối nguyên tố với n. Khi đó
=
,
(cid:19) (cid:17) (i) Nếu a ≡ b(modn), thì (cid:16) a n (cid:18) b n
=
,
(cid:19) (cid:19) (ii) (cid:16) a n (cid:17) (cid:18) b n
= (−1)(n−1)/2,
(cid:19) (iii)
= (−1)(n2−1)/8.
(iv) (cid:18)ab n (cid:18)−1 n (cid:19) (cid:18) 2 n
27
Chứng minh. Tất cả bốn phần của định lý này, chúng ta sử dụng thừa
1 pt2
2 · · · ptm m .
số nguyên tố n = pt1
a ≡ b(modp).
Chứng minh (i). Chúng ta biết rằng nếu p là số nguyên tố chia n, thì
=
(cid:19) (cid:17) . Do đó, chúng ta thấy Do đó, từ Định lý 2.2.4 (i), chúng ta có (cid:16)a b (cid:18) b p
rằng
=
· · ·
=
· · ·
=
.
(cid:19)t2 (cid:19)tm (cid:19)t2 (cid:19)tm (cid:19) (cid:17)
(cid:16) a n (cid:18) b n (cid:18) a p1 (cid:19)t1(cid:18) a p2 (cid:18) a pm (cid:18) b p1 (cid:19)t1(cid:18) b p2 (cid:18) b pm
Chứng minh (ii). Từ Định lý 2.2.4 (ii), chúng ta biết rằng
=
.
(cid:19) (cid:19)
(cid:18)ab pi (cid:18) a pi (cid:19) (cid:18) b pi
Do đó,
(cid:19)tm (cid:19)t2 (cid:19)
· · ·
=
(cid:18) ab pm (cid:19)t2 (cid:19)tm
· · · (cid:19)t2(cid:18) b p2
=
.
(cid:19)t1(cid:18)ab p2 (cid:19)t1(cid:18) a p2 (cid:18) a pm (cid:19)tm(cid:18) b pm (cid:18)ab = p1 (cid:19)t1(cid:18) b p1 (cid:19)
(cid:18)ab n (cid:18) a p1 (cid:17) (cid:18) b (cid:16) a n n
=
(−1)(p−1)/2 . Do đó
(cid:19) Chứng minh (iii). Theo Định lý 2.2.5 nếu p là số nguyên tố, thì (cid:18)−1 p
=
···
= (−1)t1(p1−1)/2+t2(p2−1)/2+···+tm(pm−1)/2.
(cid:19) (cid:19)t2 (cid:19)tm
(cid:18)−1 n (cid:18)−1 p1 (cid:19)t1(cid:18)−1 p2 (cid:18)−1 pm
n = (1 + (p1 − 1))t1(1 + (p2 − 1))t2 · · · (1 + (pm − 1))tm.
Từ hệ số nguyên tố của n, ta có
(1 + (pi − 1))ti ≡ 1 + ti(pi − 1)(mod4)
Vì (pi − 1) là chẵn, theo sau đó
(1 + ti(pi − 1))(1 + tj(pj − 1)) ≡ 1 + ti(pj − 1) + tj(pj − 1)(mod4).
và
28
n ≡ 1 + t1(p1 − 1) + t2(p2 − 1) + · · · + tm(pm − 1)(mod4).
Do đó,
Điều này ngụ ý rằng
(n − 1)/2 ≡ t1(p1 − 1)/2 + t2(p2 − 1)/2 + · · · + tm(pm − 1)/2(mod2). (cid:18)−1 n
(cid:19)
n−1
= (−1)
2 .
= (−1)(p2−1)/8. Do
(cid:19) cho Cho thấy kết hợp sự đồng dạng này cho (n − 1)/2 với biểu thức (cid:18)−1 n (cid:19) Chứng minh (iv). Nếu p là số nguyên tố, sau đó (cid:18)2 p
đó,
1−1)/8+t2(p2
2−1)/8+···+tm(p2
· · ·
= (−1)t1(p2
m−1)/8.
=
(cid:19)t2 (cid:19)tm (cid:19)
(cid:18) 2 n (cid:18) 2 p1 (cid:19)t1(cid:18) 2 p2 (cid:18) 2 pm
n2 = (1 + (p2
1 − 1)t1(1 + (p2
2 − 1))t2 · · · (1 + (p2
m − 1))tm.
Như trong chứng minh về (iii), chúng ta lưu ý rằng
j − 1 ≡ 0(mod8), chúng ta thấy rằng
(1 + (p2
i − 1))ti ≡ 1 + ti(p2
i − 1)(mod64)
Vì p2
(1 + ti(p2
i − 1))(1 + tj(p2
j − 1)) ≡ 1 + ti(p2
i − 1) + tj(p2
j − 1)(mod64).
và
n2 ≡ 1 + t1(p2
1 − 1) + t2(p2
2 − 1) + · · · + tm(p2
m − 1)(mod64).
Do đó,
(n2 − 1)/8 ≡ t1(p2
1 − 8) + t2(p2
2 − 1)/8 + · · · + tm(p2
m − 1)/8(mod8). (cid:19)
Điều này ngụ ý rằng
= (−1)(n2−1)/8.
cho chúng Kết hợp sự đồng dạng này cho (n2 − 1)/8 với biểu thức (cid:18) 2 n (cid:19) ta biết rằng (cid:18) 2 n
Bây giờ chúng ta chứng minh rằng luật tương hỗ giữ cho ký hiệu Jacobi
cũng như ký hiệu Legendre.
29
n−1
Định lý 2.4.4. (Luật tương hỗ cho các ký hiệu Jacobi) Giả sử n và m là các số nguyên dương tương đối nguyên tố. Khi đó,
m−1 2
= (−1)
2 .
(cid:17)
1 pa2 2 ·
· · pas
(cid:16) n m (cid:17) (cid:16)m n
r . Chúng ta thấy rằng
2 · · · qbr
1 qb2
Chứng minh. Giả sử các thừa số nguyên tố của m và n có m = pa1 s và n = qb1
r (cid:89)
r (cid:89)
s (cid:89)
=
=
(cid:19)bi (cid:19)biaj (cid:17)
i=1
i=1
j=1
(cid:16)m n (cid:18)m qi (cid:18)pj qj
s (cid:89)
s (cid:89)
r (cid:89)
=
=
.
và (cid:19)aj (cid:19)ajbi (cid:17)
j=1
j=1
i=1
(cid:16) n m (cid:18) n pj (cid:18) qi pj
Như vậy,
r (cid:89)
s (cid:89)
=
.
(cid:19)(cid:21)ajbi (cid:17)
i=1
j=1
(cid:16)m n (cid:17) (cid:16) n m (cid:20)(cid:18)pj qi (cid:19) (cid:18) qi pj
(cid:17)( qi−1
(cid:16) pj −1 2
= (−1)
2 ).
(cid:19)
Theo định luật tương hỗ bậc hai chúng ta biết rằng (cid:18)pj qi (cid:19) (cid:18) qi pj
(cid:17)
aj
(cid:16) pj −1 2
(cid:17) bi( qi−1 2 )
Vì thế,
r (cid:89)
s (cid:89)
bi( qi−1
(cid:16) pj −1 2
r (cid:80) i=1
s (cid:80) j=1
2 ) = (−1)
=
.
(−1)aj
i=1
j=1
(cid:17) (2.5) (cid:16)m n (cid:17) (cid:16) n m
Chúng ta lưu ý rằng
r (cid:88)
s (cid:88)
s (cid:88)
=
.
bi
aj
aj
bi
(cid:19) (cid:19) (cid:19) r (cid:19) (cid:88)
i=1
j=1
j=1
i=1
(cid:18)pj − 1 2 (cid:18)qi − 1 2 (cid:18)pj − 1 2 (cid:18)qi − 1 2
Như chúng ta đã chứng minh trong Định lý 2.4.3 (iii),
s (cid:88)
≡
(mod2)
aj
(cid:19)
m − 1 2
j=1
(cid:18)pj − 1 2
r (cid:88)
≡
(mod2).
bi
và (cid:19)
n − 1 2
i=1
(cid:18)qi − 1 2
30
Như vậy,
r (cid:88)
s (cid:88)
≡
·
(mod2).
bi
aj
m − 1 2
n − 1 2
i=1
j=1
(cid:19) (cid:19) (2.6) (cid:18)pj − 1 2 (cid:18)qi − 1 2
m−1
Do đó, bằng các phương trình (2.5) và (2.6) chúng ta có thể kết luận rằng
= (−1)
2 · n−1 2 .
(cid:17)
(cid:16)m n (cid:17) (cid:16) n m
401 = 111 · 3 + 22 · 17 111 = 17 · 6 + 20 · 9 17 = 9 · 1 + 23 · 1
Ví dụ 2.4.5. Giả sử a = 401 và b = 111. Khi đó
Sử dụng chuỗi các phương trình mà chúng ta đã mô tả, cùng với các thuộc tính của ký hiệu Jacobi, chúng ta chứng minh định lý sau, đưa ra thuật toán để đánh giá các ký hiệu Jacobi.
R2
n−1
Định lý 2.4.6. Giả sử a và b là các số nguyên dương với a > b. Khi đó
· R2−1
·
R2 1 8 +···+s
8 + R1−1
2
2 +···+
Rn−2−1 2
Rn−1−1 2
= (−1)s1
,
(cid:17)
(cid:16)a b
trong đó các số nguyên Rj và sj, j = 1, 2, ..., n − 1, như được mô tả trước đây.
Chứng minh. Từ phương trình đầu tiên và (i), (ii), (iii) của Định lý 2.4.3, chúng ta có
R2 1−1 8
=
=
=
= (−1)s1
.
(cid:19) (cid:19) (cid:19) (cid:19) (cid:17)
(cid:16)a b (cid:18)R0 R1 (cid:18)2s1R2 R1 (cid:18) 2 R1 (cid:19)s1 (cid:18)R2 R1 (cid:18)R2 R1
Sử dụng Định lý 2.4.4, định luật tương hỗ cho các ký hiệu Jacobi, chúng
ta có
R1−1 2
· R2−1 2
= (−1)
,
(cid:19) (cid:19)
(cid:18)R2 R1 (cid:18)R1 R2
sao cho
· R2−1
R1−1 2
2 +s1
R2 1−1 8
= (−1)
.
(cid:19) (cid:17)
(cid:16)a b (cid:18)R1 R2
Tương tự, sử dụng các cách chia tiếp theo, chúng ta thấy rằng
Rj+1−1
·
Rj −1 2
2 +sj
R2 j −1 8
= (−1)
(cid:19) (cid:19)
(cid:18)Rj−1 Rj (cid:18) Rj Rj+1
31
(cid:17) cho j = 2, 3, ..., n − 1. Khi chúng ta kết hợp tất cả các đẳng thức, chúng ta . thu được biểu thức mong muốn
Ví dụ 2.4.7. Để đánh giá , chúng ta sử dụng chuỗi các phân chia (cid:16)a b (cid:19) (cid:18)401 111
trong ví dụ trước và Định lý 2.4.6. Điều này cho chúng ta biết rằng
· 17−1
· 9−1
8 +0· 172−1
8 +3· 92−1
8 + 111−1
2
2 + 17−1
2
= (−1)2· 1112−1
2 = 1.
(cid:19)
(cid:18)401 111
32
Chương 3
Một số ứng dụng của thặng dư toàn phương
3.1 Kiểm tra tính chất nguyên tố của số Fermat
3(Fm−1)/2 ≡ −1(modFm).
Định lý 3.1.1. Số Fermat Fm = 22m + 1 là số nguyên tố khi và chỉ khi
Chứng minh. Trước tiên chúng ta sẽ chỉ ra rằng Fm là số nguyên tố nếu
3(Fm−1)/2 ≡ −1(modFm).
tính đồng dư trong phát biểu của định lý. Giả sử rằng
3Fm−1 ≡ 1(modFm).
Sau đó, bằng cách bình phương cả hai vế, chúng ta thu được
3Fm−1 ≡ 1(modp),
Từ sự đồng dư này, chúng ta thấy rằng nếu p là số nguyên tố chia Fm, thì
.
ordp3(Fm − 1) = 22m
và do đó,
ordp3 (cid:54) |22m−1
= (Fm − 1)/2,
Do đó, ordp3 phải là lũy thừa của 2. Tuy nhiên,
Khi 3(Fm−1)/2 ≡ −1(modFm). Do đó, khả năng duy nhất là ordp3 = 22m = Fm − 1. Khi ordp3 = Fm − 1 ≤ p − 1 và pFm, chúng ta thấy rằng p = Fm, và do đó Fm phải là số nguyên tố.
33
Ngược lại, nếu p = Fm = 22m−1 + 1 là số nguyên tố cho m ≥ 1, thì luật
tương hỗ bậc hai cho chúng ta biết rằng
=
=
= −1,
(cid:19) (cid:19) (cid:19) (3.1) (cid:18)Fm 3 (cid:18)2 3 (cid:18) 3 Fm
Khi Fm ≡ 1(mod4) và Fm ≡ 2(mod3). Bây giờ, bằng cách sử dụng tiêu chuẩn của Euler, chúng ta biết rằng
≡ 3(Fm−1)/2(modFm).
(cid:19) (3.2) (cid:18) 3 Fm
(cid:19) Bằng hai phương trình liên quan đến , (3.1) và (3.2), chúng ta kết (cid:18) 3 Fm
3(Fm−1)/2 = −1(modFm).
luận rằng
3.2 Khái niệm số giả nguyên tố Euler
Điều này kết thúc chứng minh.
Gọi p là số nguyên tố lẻ và cho b là số nguyên không chia hết cho p. Theo
tiêu chuẩn của Euler, chúng ta biết rằng
(modp).
b(p−1)/2 ≡
(cid:19)
(cid:18) b p
Do đó, nếu chúng ta muốn kiểm tra số nguyên dương n cho số nguyên b,
với (b, n) = 1, và xác định xem
b(p−1)/2 ≡
(modn),
(cid:19)
(cid:18) b n
trong đó ký hiệu ở phía bên phải của đồng dư là ký hiệu Jacobi. Nếu chúng ta thấy rằng sự đồng dư này không thỏa mãn, thì n là hợp số.
= −1. Do đó, 2170 (cid:54)≡
(mod314). Điều này chứng tỏ
Ví dụ 3.2.1. Cho n = 341 và b = 2. Chúng ta tính toán rằng 2170 ≡ 1(mod314). Vì 314 ≡ −3(mod8), sử dụng Định lý 2.4.3 (iv), chúng ta thấy (cid:19) (cid:19) rằng (cid:18) 2 314 (cid:18) 2 314
rằng 341 không phải là số nguyên tố.
Do đó, chúng ta có thể định nghĩa một loại giả nguyên tố dựa trên tiêu
chuẩn của Euler.
34
Định nghĩa 3.2.2. Một hợp số n lẻ thỏa mãn đồng dư
b(n−1)/2 ≡
(modn),
(cid:19)
(cid:18) b n
trong đó b là một số nguyên dương được gọi là giả nguyên tố Euler cho cơ sở b.
1(mod1105). Kể từ 1105 ≡ 1(mod8), chúng ta thấy rằng
= 1.
1105
Ví dụ 3.2.3. Cho n = 1105 và b = 2. Chúng ta tính toán rằng 2552 ≡ (cid:19) (cid:18) 2
(mod1105). Bởi vì 1105 là một hợp số nên nó là
1105
(cid:19) (cid:18) 2 Do đó, 2552 ≡
một giả nguyên tố Euler cơ sở 2.
Định lý sau đây cho thấy rằng mỗi giả nguyên tố Euler cho cơ sở b là một
giả nguyên tố cho cơ sở này.
Định lý 3.2.4. Nếu n là một giả nguyên tố Euler cho cơ sở b, thì n là một giả nguyên tố cho cơ sở b.
Chứng minh. Nếu n là một giả nguyên tố Euler cho cơ sở b, thì
b(n−1)/2 ≡
(modn).
(cid:19)
(cid:18) b n
Do đó, bằng cách bình phương cả hai vế của đồng dư này, chúng ta thấy
rằng
(b(n−1)/2)2 ≡
(modn).
(cid:19)2
(cid:18) b n
= ±1 chúng ta thấy rằng bn−1 ≡ 1( mod n). Điều này có nghĩa là
n là một giả nguyên tố cho cơ sở b.
(cid:19) Vì (cid:18) b n
Không phải mọi giả nguyên tố đều là một giả nguyên tố Euler. Ví dụ, số nguyên 341 không phải là giả nguyên tố Euler đối với cơ sở 2, như chúng ta đã chỉ ra, nhưng là một giả nguyên tố cho cơ sở này.
Chúng ta biết rằng mỗi giả nguyên tố Euler là một giả nguyên tố. Tiếp theo, chúng ta cho thấy rằng mỗi giả nguyên tố mạnh là một giả nguyên tố Euler.
Định lý 3.2.5. Nếu n là một giả nguyên tố mạnh đối với cơ sở b, thì n là một giả nguyên tố Euler cho cơ sở này.
35
m (cid:89)
Chứng minh. Giả sử n là một giả nguyên tố mạnh cho cơ sở b. Khi đó, nếu n − 1 = 2st, trong đó t là số lẻ, thì bt ≡ 1(modn) hoặc b2t ≡ −1(modn)
pai i
i=1
trong đó 0 ≤ r ≤ s − 1. Gọi n = là hệ số công suất nguyên tố của n.
b(p−1)/2 ≡ 1(modp).
Trước tiên, hãy xem xét trường hợp bt ≡ 1( mod n). Gọi p là ước số nguyên tố của n. Vì bt ≡ 1( mod p), chúng ta biết rằng ordpb|t. Vì t là số lẻ nên chúng ta thấy ordpb cũng là số lẻ. Do đó, ordpb|(p − 1)/2, vì ordpb là ước số lẻ của số nguyên chẵn φ(p) = p − 1. Do đó,
(cid:19) Do đó, theo tiêu chuẩn của Euler, chúng ta có
= 1. (cid:19)
= 1 cho tất cả các
(cid:19) , chúng ta lưu ý rằng Để tính ký hiệu Jacobi (cid:18) b p (cid:18) b p
(cid:18) b n số nguyên tố p chia n. Do đó,
b
m (cid:89)
=
= 1.
=
(cid:19) (cid:19)ai
i=1
pai i
≡ 1(modn). Do
m (cid:81) i=1 Vì bt ≡ 1(modn), chúng ta biết rằng b(n−1)/2 = (bt)2s−1 (cid:19)
≡ 1(modn) .
(cid:18) b n (cid:18) b pi
đó, chúng ta có b(n−1)/2 ≡ (cid:18) b n
b2rt ≡ −1(modn)
Chúng ta kết luận rằng n là một giả nguyên tố Euler cho cơ sở b. Tiếp theo, hãy xem xét trường hợp
b2rt ≡ −1(modp).
cho một số r với 0 ≤ r ≤ s − 1. Nếu p là ước số nguyên tố của n, thì
b2r+1t ≡ 1(modp).
Bình phương cả hai vế của sự đồng dư này, chúng ta thu được
ordpb = 2r+1c, trong đó c là số nguyên lẻ. Vì ordpb|(p − 1) và 2r+1|ordpb, theo đó 2r+1|(p − 1).
Điều này hàm ý rằng ordpb|2r+1t, nhưng ordpb (cid:54) |2rt. Do đó,
36
b(ordpb)/2 ≡ −1(modp),
Do đó, chúng ta có p = 2r+1d + 1, trong đó d là một số nguyên. Vì
nên ta có
≡ b(p−1)/2 = b(ordpb/2)((p−1)/ordpb)
(cid:19)
≡ (−1)(p−1)/ordpb = (−1)(p−1)/2r+1c(modp)
(cid:18) b p
(−1)c = −1 ordpb = 2r+1|o
Vì c là số lẻ, nên chúng ta biết rằng
= (−1)(p−1)/2r+1
= (−1)d,
Do đó, (cid:19) (3.3) (cid:18) b p
n =
pai i
=
m (cid:81) i=1 (2r+1di + 1)ai
≡
m (cid:81) i=1 m (cid:81) i=1
≡ 1 + 2r+1
aidi(mod22r+2).
(1 + 2r+1aidi) m (cid:80) i=1
nhắc lại rằng d = (p − 1)/2r+1. Vì mỗi số nguyên tố pi chia n có dạng pi = 2r+1di + 1, nên theo đó là dạng
m (cid:88)
t2s−1 = (n − 1)/2 ≡ 2r
aidi(mod2r+1).
i=1
Do đó,
m (cid:88)
t2s−1−r ≡
aidi(mod2)
i=1
Sự phù hợp này ngụ ý rằng
aidi(modn)
m (cid:80) i=1
và
b(p−1)/2 = (b2rt)2s−1−r
≡ (−1)2s−1−r
= (−1)
.
(3.4)
Mặt khác, từ (3.3), chúng ta có
37
aidi
m (cid:89)
m (cid:89)
m (cid:89)
m (cid:80) i=1
=
=
((−1)di)ai =
(−1)aidi = (−1)
.
(cid:19) (cid:19)ai
i=1
i=1
i=1
(cid:18) b p (cid:18) b pi
Do đó, kết hợp phương trình trước với (3.4), chúng ta thấy rằng
b(p−1)/2 ≡
(modn).
(cid:19)
(cid:18) b n
Do đó, n là một giả nguyên tố Euler cho cơ sở b.
Mặc dù mọi giả nguyên tố mạnh cơ sở b là một giả nguyên tố Euler cho cơ sở này, lưu ý rằng không phải mọi giả nguyên tố Euler cho cơ sở b đều là một giả nguyên tố mạnh đối với cơ sở b, như ví dụ sau đây cho thấy.
2(1105−1)/2 = 2552 ≡ 1(mod1105),
Ví dụ 3.2.6. Trước đây chúng ta đã chỉ ra rằng số nguyên 1105 là một giả nguyên tố Euler cho cơ sở 2. Tuy nhiên, 1105 không phải là một giả nguyên tố mạnh cho cơ sở 2 kể từ
2(1105−1)/22
= 2276 ≡ 781 (cid:54)≡ ±1(mod1105).
trong khi
Một giả nguyên tố Euler cho cơ sở b không phải lúc nào cũng là một giả nguyên tố mạnh. Mặc dù đối với cơ sở này, khi một số điều kiện bổ sung được đáp ứng, trên thực tế, một giả nguyên tố Euler đối với cơ sở b là một giả nguyên tố mạnh đối với căn cứ này. Hai định lý sau đây cho kết quả của loại này.
Định lý 3.2.7. Nếu n ≡ 3(mod4) và n là một giả nguyên tố Euler cho cơ sở b, thì n là một giả nguyên tố mạnh cho cơ sở b.
bt = b(n−1)/2 ≡
(modn).
Chứng minh. Từ đồng dư n ≡ 3( mod 4), chúng ta biết rằng n − 1 = 2 · t trong đó t = (n − 1)/2 là số lẻ. Vì n là là một giả nguyên tố Euler cho cơ sở b, nên theo đó (cid:19)
(cid:18) b n
= ±1 , chúng ta biết rằng bt ≡ 1(modn) hoặc bt ≡ −1(modn).
(cid:19) Vì (cid:18) b n
Do đó, một trong những đồng dư trong định nghĩa của một số giả nguyên tố mạnh đối với cơ sở b phải giữ. Do đó, n là một giả nguyên tố mạnh cho cơ sở b.
38
= −1,
(cid:19) Định lý 3.2.8. Nếu n là một giả nguyên tố Euler cho cơ sở b và (cid:18) b n
thì n là một giả nguyên tố mạnh cho cơ sở b.
Chứng minh. Chúng ta viết n − 1 = 2st, trong đó t là số lẻ và s là số nguyên dương. Vì n là một giả nguyên tố Euler cho cơ sở b nên chúng ta có
b2s−1t = b(n−1)/2 ≡
(modn).
(cid:19)
(cid:18) b n
= −1, chúng ta thấy rằng
bt2s−1
≡ −1(modn)
(cid:19) Nhưng kể từ (cid:18) b n
Đây là một trong những sự phù hợp trong định nghĩa của một giả nguyên tố mạnh đối với cơ sở b. Vì n là hợp số, nó là một giả nguyên tố mạnh cơ sở b. Sử dụng khái niệm giả nguyên tố Euler, kiểm định nguyên thủy. Kiểm định này lần đầu tiên được đề xuất bởi Solovay và Strassen.
= −1, trong
Bổ đề 3.2.9. Nếu n là số nguyên dương lẻ không phải là một số chính phương, (cid:19) thì có ít nhất một số nguyên b với 1 < b < n, (b, n) = 1 và (cid:18) b n (cid:19) đó là ký hiệu Jacobi. (cid:18) b n
Chứng minh. Nếu n là số nguyên tố, sự tồn tại của số nguyên b như vậy được đảm bảo bởi Định lý 2.1.4. Nếu n là hợp số, vì n không phải là một số chính phương, chúng ta có thể viết n = rs trong đó (r, s) = 1 và r = pe, với p là một số nguyên tố lẻ và e là một số nguyên dương lẻ.
b ≡ t(modr)
b ≡ 1(mods).
Bây giờ, hãy để ý t là một số nguyên tố bậc hai của số nguyên tố p; như vậy tồn tại bởi Định lý 2.1.4. Chúng ta sử dụng định lý thặng dư Trung Hoa để tìm một số nguyên b với 1 và sao cho b thỏa mãn hai đồng dư 1 < b < n, (b, n) = 1.
Khi đó
=
=
= (−1)e = −1,
(cid:19) (cid:19) (cid:19)e
=
= −1.
= 1. Vì
(cid:19) (cid:18) b p (cid:19) (cid:19) (cid:19) , theo đó và (cid:18) b r (cid:18) b n (cid:18) b pe (cid:18) b r (cid:19) (cid:18) b s (cid:18) b n (cid:18) b s
39
Bổ đề 3.2.10. Giả sử số nguyên n là hợp số lẻ. Khi đó, có ít nhất một số nguyên b với 1 < b < n, (b, n) = 1, và
b(n−1)/2 ≡
(modn).
(cid:19)
(cid:18) b n
Chứng minh. Giả sử rằng với tất cả các số nguyên dương không vượt
quá n và tương đối nguyên tố so với n, điều đó
b(n−1)/2 ≡
(modn).
(cid:19) (3.5) (cid:18) b n
Bình phương cả hai vế của sự đồng dư này cho chúng ta biết rằng
≡ (±1)2 = 1(modn),
bn−1 ≡
(cid:19)2
(cid:18) b n
n = q1q2 · · · qr, trong đó q1, q2, ..., qr, là số lẻ.
Nếu (b, n) = 1. Do đó, n phải là một số Carmichael. Do đó, chúng ta có
b(n−1)/2 ≡ 1(modn)
Bây giờ chúng ta sẽ chỉ ra rằng
Với mọi số nguyên b với 1 < b < n và (b, n) = 1. Giả sử b là một số nguyên
b(n−1)/2 ≡ −1(modn).
sao cho
1 < a < n, (a, n) = 1 và
a ≡ b(modq1) a ≡ 1(modq1q2 · · · qr).
Chúng ta sử dụng định lý thặng dư Trung Hoa của một số nguyên với
Khi đó, chúng ta quan sát rằng
a(n−1)/2 ≡ b(n−1)/2 ≡ −1(modq1),
(3.6)
trong khi
a(n−1)/2 ≡ 1(modq2q3 · · · qr).
(3.7)
Từ đồng dư (3.6) và (3.7), chúng ta thấy rằng
40
a(n−1)/2 (cid:54)≡ ±1(modm),
b(n−1)/2 ≡ 1(modn),
mâu thuẫn với (3.5). Do đó, chúng ta phải có
với mọi b với 1 < b < n và (b, n) = 1. Do đó, từ định nghĩa của một giả nguyên tố Euler, chúng ta biết rằng
b(n−1)/2 ≡
= 1(modn)
(cid:19)
(cid:18) b n
với tất cả b với 1 < b < n và (b, n) = 1. Tuy nhiên, Bổ đề (2.2.8) cho chúng ta biết điều này là không thể. Do đó, giả định ban đầu là sai. Phải có ít nhất một số nguyên b với 1 < b < n và (b, n) = 1, và
b(n−1)/2 (cid:54)≡
(modn).
(cid:19)
(cid:18) b n
Bây giờ chúng ta có thể nêu và chứng minh định lý là cơ sở của kiểm tra
tính nguyên thủy xác suất.
Định lý 3.2.11. Giả sử số nguyên n là hợp số lẻ. Khi đó, số nguyên dương nhỏ hơn n và tương đối nguyên tố với n là các cơ sở mà n là giả nguyên tố Euler, không vượt quá φ(n)/2.
Chứng minh. Theo bổ đề 3.2.10 chúng ta biết rằng có một số nguyên b
với 1 < b < n, (b, n) = 1 và
(mod2n).
b(n−1)/2 (cid:54)≡
(cid:19) (3.8) (cid:18) b n
Bây giờ, hãy để a1, a2, ..., am biểu thị các số nguyên dương nhỏ hơn n thỏa
mãn 1 ≤ aj ≤ n, (aj, n) = 1, và
(modn),
≡
a(n−1)/2 j
(cid:17) (3.9) (cid:16)aj n
cho j = 1, 2, .., m.
Giả sử r1, r2, ..., rm là thặng dư nhỏ nhất của các số nguyên ba1, ba2, ..., bam modulo n. Hơn nữa, chúng ta lưu ý rằng các số nguyên rj là khác biệt và (rj, n) = 1 cho j = 1, 2, ..., m. Hơn nữa,
(cid:54)≡
(modn).
r(n−1)/2 j
(cid:17) (3.10) (cid:16)rj n
41
≡
(modn),
r(n−1)/2 j
Vì, nếu đúng là (cid:17)
(cid:16)rj n
thì chúng ta sẽ có
(modn).
(baj)(n−1)/2 ≡
(cid:19)
(cid:18)baj n
Điều này có nghĩa là,
(modn),
≡
b(n−1)/2a(n−1)/2 j
(cid:17)
(cid:18) b n (cid:19) (cid:16)aj n
và kể từ (3.9), chúng ta sẽ có
b(n−1)/2 ≡
,
(cid:19)
(cid:18) b n
mâu thuẫn (3.8).
3.3 Giải một số bài toán khó trong số học phổ thông
Kể từ khi aj, j = 1, 2, ..., m, thỏa mãn đồng dư (2.2.11) trong khi rj, j = 1, 2, ..., m, không, như (2.2.12) cho thấy, chúng ta biết hai bộ số nguyên này không chia sẻ các phần tử chung. Do đó, nhìn vào hai tập hợp với nhau, chúng ta có tổng cộng 2m số nguyên dương khác biệt nhỏ hơn n và tương đối nguyên tố với n. Vì có các số nguyên φ(n) nhỏ hơn n tương đối nguyên tố so với n, nên chúng ta có thể kết luận rằng 2m ≤ φ(n), sao cho m ≤ φ(n)/2. Điều này chứng minh định lý.
Bài toán 3.3.1. Tìm tất cả số nguyên dương n sao cho 3n − 1 chia hết cho 2n − 1.
Giải. Rõ ràng n = 1 thỏa mãn. Xét n > 1 và giả sử 3n − 1 chia hết cho 2n − 1. Nếu n chẵn thì 2n − 1 chia hết cho 3 do đó 3n − 1 chia hết cho 3. Vô lý. Vậy n lẻ. Ta có bổ đề sau
Bổ đề 3.3.2. Nếu 3 là thặng dư toàn phương (modp) thì p = 12k + 1 hoặc p = 12k − 1.
Chứng minh. Theo luật tương hỗ
= (−1)(3−1)(p−1)/4 = (−1)(p−1)/2
(cid:17)
(cid:18)3 p (cid:19) (cid:16)p 3
Vì 3 là thặng dư toàn phương (modp) nên
42
= 1
(cid:19)
(cid:18)3 p
Do đó
= (−1)(p−1)/2
(cid:17)
(cid:16)p 3 Nếu p = 4k + 1 → p ≡ 1(mod4) thì (p − 1)/2 lẻ. Do đó
= −1.
(cid:17)
(cid:16)p 3
Theo tiêu chuẩn Euler
= p(3−1)/2 = p(mod3)
(cid:17)
(cid:16)p 3
Vậy p ≡ −1(mod3). Do p ≡ −1(mod4) ta suy ra p ≡ −1(mod12) tức là p = 12k − 1. Bổ đề được chứng minh.
Bổ đề 3.3.3. Gọi p là một ước nguyên tố bất kỳ của 2n−1. Khi đó p = 12k+1 hoặc p = 12k − 1.
Chứng minh. Vì 3n − 1 chia hết cho 2n − 1 nên p là một ước nguyên tố của 3n − 1. Vậy 3n ≡ 1(modp). Suy ra 3n+1 ≡ 3(modp). Vì n + 1 chẵn nên 3 là thặng dư toàn phương (mod p). Theo bổ đề 3.3.1 p = 12k + 1 hoặc p = 12k − 1. Trở lại bài toán. Theo bổ đề 3.3.2 mọi ước nguyên tố của 2n − 1 có dạng p = 12k + 1 hoặc p = 12k − 1. Do đó 2n − 1 cũng có dạng p = 12k + 1 hoặc p = 12k − 1.
Nếu 2n − 1 = 12k − 1. Suy ra 2n = 12k. Đây là điều mâu thuẫn vì vế phải
chia hết cho 3 vế trái chia hết cho 3 .
Nếu 2n − 1 = 12k + 1. Suy ra 2n = 12k + 2 = 2(6k + 1). Do n > 1 nên
vế phải chia hết cho 4. Ta có mâu thuẫn.
Kết luận: Vậy n = 1 là giá trị duy nhất để 3n − 1 chia hết cho 2n − 1.
Bài toán 3.3.4. Cho hai số nguyên dương m, n. Chứng minh rằng nếu n lẻ, m = 2a với a lẻ và m là ước của 3n + 1 thì (m + 3)n + 1 chia hết cho 3m.
Giải. Ta có (m + 3)n + 1 ≡ 3n + 1 ≡ 0(modm). Vậy (m + 3)n + 1 chia
hết cho m.
Tiếp theo ta chứng minh (m + 3)n + 1 chia hết cho 3.
43
Bổ đề 3.3.5. Nếu p là số nguyên tố lẻ và −3 là thặng dư toàn phương ( mod p) thì p ≡ 1(mod3).
Chứng minh. Vì −3 là thặng dư toàn phương (modp) nên
= 1.
(cid:19)
(cid:18)−3 p
Suy ra
=
= 1
(cid:19) (cid:19)
→
=
(cid:17) (cid:17) (3.11) (cid:18)−1 p (cid:18)−1 p (cid:19) (cid:18)3 p (cid:19) (cid:18)3 p (cid:18)−3 p (cid:19) (cid:16)p 3 (cid:16)p 3
Theo định luật tương hỗ và tiêu chuẩn Euler ta có
= (−1)(3−1)(p−1)/4 = (−1)(p−1)/2 =
(cid:19) (cid:17)
(cid:18)3 p (cid:19) (cid:16)p 3 (cid:18)−1 p
Do đó vế trái của (3.11) là
=
= 1
(cid:19) (cid:19)
(cid:18)−1 p (cid:19) (cid:18)−1 p (cid:18)1 p
Theo tiêu chuẩn Euler, vế phải của (3.11) là
≡ p(3−1)/2 = p
(cid:17)
(cid:16)p 3
Vậy p ≡ 1(mod3). Bổ đề được chứng minh.
3n ≡ −1(modp) → 3n+1 ≡ −3(modp)
Trở lại bài toán. Gọi p là ước nguyên tố bất kỳ của a. Vì a lẻ nên p lẻ. Ta có m = 2a là ước của 3n + 1 nên a là ước của 3n + 1, do đó p là ước của 3n + 1. Vậy
(m + 3)n + 1 ≡ mn + 1 ≡ 2n + 1 ≡ (−1)n + 1 ≡ 0(mod3).
Vì n + 1 chẵn nên −3 là thặng dư toàn phương (modp). Theo bổ đề p ≡ 1(mod3). Vì mọi ước nguyên tố p của a thỏa mãn p ≡ 1(mod3) nên a ≡ 1(mod3). Suy ra m = 2a ≡ 2(mod3). Thành thử
44
Như vậy ta đã chứng minh (m + 3)n + 1 chia hết cho m và chia hết cho 3. Do m là ước của 3n + 1 nên (m, 3) = 1. Thành thử (m + 3)n + 1 chia hết cho 3m.
Bài toán đã được chứng minh.
Bài toán 3.3.6. Cho p là số nguyên tố lẻ và p ≡ 1( mod 3). Chứng minh rằng tồn tại số nguyên dương k sao cho k2 + k + 1 chia hết cho p.
Giải. Theo tiêu chuẩn Euler ta có
= p(3−1)/2 = p
(cid:17)
(cid:16)p 3
= 1
(cid:17)
Theo giả thiết p ≡ 1(mod3). Vậy (cid:16)p 3
Do đó, theo định luật tương hỗ và tiêu chuẩn Euler
=
(cid:19) (cid:17)
(cid:18)3 p (cid:18)3 p
=
(cid:19) (cid:16)p 3 = (−1)(3−1)(p−1)/4 = (−1)(p−1)/2 (cid:19)
→
(cid:19) (cid:19)
=
=
(cid:18)−1 p (cid:19)
= (cid:19) (cid:18)−1 p
= 1
(cid:18)−1 p (cid:18)−3 p (cid:18)−1 p (cid:19) (cid:18)3 p (cid:19) (cid:18)1 p
a2 + 3 = (2k + 1)2 + 3 = 4(k2 + k + 1) ≡ 0(modp) → k2 + k + 1 ≡ 0(modp)
Vậy −3 là thặng dư toàn phương (mod p). Do đó tồn tại số nguyên a sao cho a2 ≡ −3(modp) → a2 + 3 ≡ 0(modp). Ta có thể giả thiết a lẻ vì nếu a chẵn ta đặt b = a + p ≡ a(modp) thì b lẻ và b2 + 3 ≡ 0(modp). Đặt a = 2k + 1 . Khi đó
tức là k2 + k + 1 chia hết cho p.
Bài toán đã được chứng minh.
5m = 4p1p2..pk + 1
Bài toán 3.3.7. Giả sử m là số nguyên dương lẻ sao cho 5m có dạng
ở đó p1..pk là các số nguyên tố lẻ phân biệt. (Chẳng hạn 53 = 4(31) + 1) Chứng minh rằng 2(p1 − 1)...(pk − 1) + 1 không thể là lũy thừa của 5.
45
Giải. Chứng minh bằng phản chứng. Giả sử tồn tại n sao cho
2(p1 − 1)...(pk − 1) + 1 = 5n
(3.12)
Ta có với mỗi i = 1, 2, ..., k
5m = 4p1p2..pk + 1 → 5m − 1 = 4p1p2..pk
→ 5m ≡ 1(modpi) → 5m+1 ≡ 5(modpi)
(3.13)
= 1. Theo định luật tương hỗ
Vì m + 1 chẵn nên suy ra 5 là thặng dư toàn phương của pi. Suy ra (cid:19)
(cid:18) 5 pi
= (−1)(5−1)(pi−1)/4 = (−1)(pi−1) = 1
(cid:17)
(cid:19) (cid:16)pi 5 (cid:18) 5 pi
= 1. Theo tiêu chuẩn Euler
(cid:17) Vậy (cid:16)pi 5
= p2 i
≡ p(5−1)/2 i
(cid:17)
→ p2
i ≡ 1(mod5) → pi ≡ ±1(mod5)
(cid:16)pi 5
5m − 1 = 4p1p2..pk ≡ (−1)k+1(mod5) → (−1) ≡ (−1)k+1(mod5).
Từ (3.12) suy ra pi ≡ −1(mod5) với mỗi i = 1, 2, ..., k. Vậy từ (3)
5n − 1 = 2(p1 − 1)...(pk − 1) ≡ 2(−2)k = 2(4l) ≡ 2(−1)l = ±2(mod5)
Vậy k chẵn. Đặt k = 2l. Từ (3.12) ta có
5. Vậy 2(p1 − 1)...(pk − 1) + 1 không thể là lũy thừa của 5.
Suy ra 5n ≡ 1 ± 2( mod 5). Ta có mâu thuẫn vì vế phải không chia hết cho
Bài toán đã được chứng minh.
46
Kết luận
• Hệ thống lại một số kiến thức cơ bản về đồng dư và phương trình đồng
Luận văn đã trình bày được một số vấn đề sau:
• Trình bày một số kết quả thặng dư toàn phương cùng với các ký hiệu
dư.
• Đưa ra một số ví dụ minh họa cho kết quả lý thuyết cũng như sử dụng
Ledendre và ký hiệu Jacobi.
thặng dư toàn phương để giải một số bài toán trong số học phổ thông.
47
Tài liệu tham khảo
A Tiếng Việt
[1] Đặng Hùng Thắng (2010), Bài giảng số học, Nhà xuất bản Giáo dục.
[2] Tạp chí Toán học và tuổi trẻ (2010 - 2017), Nhà xuất bản Giáo dục.
B Tiếng Anh
[3] K.H.Rosen (1995), Elementary number theory and applications, Wiley,
NewYork.
[4] D.E.Flath (1989), Introduction to number theory, Springer-Verlag,
NewYork.
[5] M.Schroeder (1986), Number theory in sciences, Springer-Verlag, Berlin.
