ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
——————–o0o——————–

ĐỖ THỊ THOA

ỨNG DỤNG CỦA LUẬT THUẬN NGHỊCH VÀ
THẶNG DƯ BẬC HAI

THÁI NGUYÊN - 2019


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
——————–o0o——————–

ĐỖ THỊ THOA

ỨNG DỤNG CỦA LUẬT THUẬN NGHỊCH VÀ
THẶNG DƯ BẬC HAI

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

PGS. TS. NGUYỄN VĂN HOÀNG

THÁI NGUYÊN - 2019

10

Thặng dư bậc hai và ứng dụng . . . . . . . . . . . . . . . . . . . . 10
2.1.1

Phương trình đồng dư bậc hai . . . . . . . . . . . . . . . . 10

2.1.2

Thặng dư bậc hai . . . . . . . . . . . . . . . . . . . . . . . . 12

2.1.3

Tiêu chuẩn Euler và ký hiệu Legendre . . . . . . . . . . . . 16

2.1.4

Bổ đề Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.1.5

Một số ứng dụng khác . . . . . . . . . . . . . . . . . . . . . 27

Luật thuận nghịch bậc hai và ứng dụng . . . . . . . . . . . . . . . 32
2.2.1

Luật thuận nghịch bậc hai . . . . . . . . . . . . . . . . . . . 32

2.2.2


mục đích là hệ thống lại mảng kiến thức liên quan đến luật thuận nghịch và
thặng dư bậc hai, từ đó trình bày một số ví dụ ứng dụng hay của chúng nhằm
cung cấp một tài liệu tốt để dạy và học cho giáo viên và học sinh phổ thông
trung học.
Luận văn ngoài phần mở đầu, kết luận thì nội dung chính gồm 2 chương
trình bày lại một cách hệ thống về luật thuận nghịch và thặng dư bậc hai cùng
một số ứng dụng của chúng, với bố cục cụ thể như sau:
Chương 1. Kiến thức chuẩn bị. trình bày phát biểu và chứng minh định


2

lý Fermat nhỏ, định lý Euler. Trình bày khái niệm và cách giải phương trình
đồng dư tuyến tính, hệ phương trình đồng dư tuyến tính (định lý thặng dư
Trung Hoa).
Chương 2. Ứng dụng của luật thuận nghịch và thặng dư bậc hai.
Chương 2 trình bày định nghĩa và các tính chất của phương trình đồng dư bậc
hai, thặng dư bậc hai, cách tính bằng định nghĩa, cách tính thông qua ký hiệu
Legendre, cách tính thông qua luật thuận nghịch bậc hai. Sau đó ứng dụng
thặng dư bậc hai và luật thuận nghịch bậc hai để tính toán và giải một số bài
toán chứng minh, tìm căn nguyên thủy, kiểm tra tính nguyên tố.
Luận văn được hoàn thành tại trường Đại học Khoa học, Đại học Thái
Nguyên. Lời đầu tiên tác giả xin được bày tỏ lòng biết ơn sâu sắc tới thầy giáo
PGS.TS. Nguyễn Văn Hoàng. Thầy đã dành nhiều thời gian hướng dẫn cũng
như giải đáp các thắc mắc của tôi trong suốt quá trình làm luận văn. Tôi xin
bày tỏ lòng biết ơn sâu sắc tới thầy.
Tác giả 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.
Cảm ơn sự giúp đỡ của bạn bè, người thân và các đồng nghiệp trong thời


ia với

mọi i = 1, 2, . . . , p − 1 (vì nếu ngược lại, tồn tại 1 ≤ i ≤ p − 1 để p | ia, kéo theo
p | a hoặc p | i; nhưng vì p

a, nên ta có p | i điều này mâu thuẫn). Cũng chú

ý rằng không có hai số nào trong p − 1 số nguyên a, 2a, 3a, . . . , (p − 1)a đồng dư
modulo p (vì nếu ngược lại, thì tồn tại nghịch đảo a của a modulo p; nên từ
ia ≡ ja (mod p) với i = j thì iaa ≡ jaa (mod p), từ đó i ≡ j (mod p), điều này

là không thể). Do đó tập các số dư trong phép chia cho p của các số nguyên
a, 2a, 3a, . . . , (p − 1)a phải là {1, 2, 3, . . . , p − 1}. Khi đó,
(a)(2a)(3a) · · · (p − 1)a ≡ (1)(2)(3) · · · (p − 1)

(mod p)


4

hay tương đương với
ap−1 (p − 1)! ≡ (p − 1)!

(mod p).

Mặt khác ta thấy (p − 1)! và p là hai số nguyên tố cùng nhau, nên từ đồng dư
bên trên cho ta thấy ap−1 ≡ 1 (mod p), điều phải chứng minh.
Ví dụ 1.1.2. Với a = 3, p = 5 suy ra 34 = 81 ≡ 1 (mod 5). Tương tự, ta tính
được 910 ≡ 1 (mod 11).


5

hay tương đương với
aφ(m) r1 r2 · · · rφ(m) ≡ r1 r2 · · · rφ(m)

(mod m).

Bây giờ, m | (aφ(m) r1 r2 · · · rφ(m) − r1 r2 · · · rφ(m) ) kéo theo m | (r1 r2 · · · rφ(m) ) ×
(aφ(m) − 1). Chú ý vì (ri , m) = 1 với i = 1, 2, . . . , φ(m) nên (r1 r2 . . . rφ(m) , m) = 1.

Do đó ta suy ra m | (aφ(m) − 1) và do đó aφ(m) ≡ 1 (mod m), điều phải chứng
minh.
Định lý Euler là tổng quát hóa của định lý nhỏ Fermat vì nếu n = p là số
nguyên tố thì φ(p) = p − 1. Định lý này có thể được sử dụng để dễ dàng giản ước
với những modulo m rất lớn.
Ví dụ 1.1.4. Ví dụ tìm chữ số tận cùng của số 7222 .
Giải. Chú ý rằng 7 và 10 là nguyên tố cùng nhau và φ(10) = 4. Bởi vậy 74 ≡ 1
(mod 10). Và ta có
7222 ≡ 74.55+2 72 ≡ 155 72 ≡ 49 ≡ 9

(mod 10).

Vậy 7222 có chữ số tận cùng là 9.

1.2

Sơ lược về phương trình đồng dư

Định nghĩa 1.2.1. Phương trình đồng dư đại số bậc n là một đồng dư thức có

hạng chia hết cho 9 ta được
6t + 3 ≡ 0

(mod 9)

⇔ 2t + 1 ≡ 0

(mod 3)

⇔t≡1

(mod 3)

⇔ t = 3k + 1.

Vậy phương trình có nghiệm là x = 3(3k + 1) + 1 hay x ≡ 4 (mod 9).
Định nghĩa 1.2.5. Phương trình đồng dư ax ≡ b (mod m) được gọi là phương
trình đồng dư tuyến tính với a, b, m là các số nguyên đã biết. Khi đó x ≡ x0
(mod m) là một nghiệm của phương trình khi và chỉ khi ax0 ≡ b (mod m).

Định lý 1.2.6 ([6]). Phương trình đồng dư tuyến tính ax ≡ b (mod m) có nghiệm
khi và chỉ khi d | b, trong đó d = (a, m). Nếu d | b thì phương trình có d nghiệm.
Hệ quả 1.2.7 ([6]). Phương trình đồng dư tuyến tính ax ≡ b (mod m) có nghiệm
duy nhất khi và chỉ khi (a, m) = 1.
Hệ quả 1.2.8 ([6]). Cho phương trình đồng dư tuyến tính ax ≡ b (mod m) và
gọi d = (a, m). Nếu d | b thì d nghiệm modulo m của phương trình là
(x0 +

mt
)

(mod 11).

(1.3)

Từ (1.2) và (1.3) và theo tính chất bắc cầu ta có 6x ≡ 2 (mod 11). Do (2, 11) =1
nên giản ước hai vế cho 2 ta được 3x ≡ 1 (mod 11) hay 3x = 11t + 1. Lấy t = 1
suy ra x = 4. Do (3, 11) = 1 nên phương trình có nghiệm duy nhất là x ≡ 4
(mod 11).

Định lý 1.2.11 (Định lý thặng dư Trung Hoa, [5]). Cho m1 , m2 , . . . , mn là các số
nguyên dương đôi một nguyên tố cùng nhau và cho b1 , b2 , . . . , bn là các số nguyên
bất kỳ. Khi đó hệ phương trình đồng dư tuyến tính

x ≡ b1 (mod m1 )



x ≡ b2 (mod m2 )
·········



x ≡ bn (mod mn )

có nghiệm duy nhất modulo m1 m2 · · · mn .
Chứng minh. Đầu tiên ta xây dựng một số nguyên thỏa mãn hệ đã cho. Đặt
M = m1 m2 · · · mn . Với mỗi i = 1, 2, . . . , n đặt Mi = M/mi . Bây giờ với mỗi
i = 1, 2, . . . , n ta có (Mi , mi ) = 1. Do đó theo Hệ quả 1.2.7, phương trình Mi x ≡ 1
(mod mi ) có một nghiệm xi (mod mi ). Đặt
x = b1 M1 x1 + b2 M2 x2 + · · · + bn Mn xn .

M = 3 · 4 · 5 = 60
M
60
M1 =
=
= 20
m1
3
M
60
M2 =
=
= 15
m2
4
M
60
M1 =
=
= 12
m3
5

Ta giải các phương trình đồng dư Mi xi ≡ 1 (mod mi ), i = 1, 2, 3. M1 x1 ≡ 1
(mod m1 ) trở thành 20x1 ≡ 1 (mod 3), hay 2x1 ≡ 1 (mod 3), từ đó x1 ≡ 2 (mod 3).
M2 x2 ≡ 1 (mod m2 ) trở thành 15x2 ≡ 1 (mod 4), hay 3x2 ≡ 1 (mod 4), từ đó
x2 ≡ 3 (mod 4). Cuối cùng, M3 x3 ≡ 1 (mod m3 ) trở thành 12x3 ≡ 1 (mod 5), hay
2x3 ≡ 1 (mod 5), từ đó x3 ≡ 3 (mod 5). Do đó, ta đặt
x1 = 2,


2.1

Thặng dư bậc hai và ứng dụng

Thặng dư bậc hai đóng vai trò rất quan trọng trong lý thuyết số. Chẳng hạn,
thuật toán phân tích số nguyên ra thừa số nguyên tố. Ngoài ra thặng dư bậc
hai cũng ứng dụng lớn trong mật mã cũng như trong các giao thức mã hóa....
Ở đây ta xét ứng dụng liên quan đến giải phương trình đồng dư bậc hai trong
lý thuyết và thực hành.

2.1.1

Phương trình đồng dư bậc hai

Xét phương trình đồng dư bậc hai theo modulo nguyên tố (theo tài liệu [5]).
Ax2 + Bx + C ≡ 0

(mod p),

(2.1)

trong đó p nguyên tố lẻ và A, B, C ∈ Z với p A. (Nếu p | A thì quay về phương
trình tuyến tính). Vì p nguyên tố lẻ và p A, nên p 4A. Ta nhân hai vế của


11

phương trình với 4A ta được
4A(Ax2 + Bx + C) ≡ 0


(6x − 4)2 ≡ (16 − 84)

(mod 13)

Tức là

(6x − 4)2 ≡ 10

(mod 13)

Đặt y = 6x − 4. Khi đó y 2 ≡ 10 (mod 13). Phương trình đồng dư này có chính xác
hai nghiệm y ≡ 6 (mod 13) và y ≡ 7 (mod 13). Do đó, các nghiệm của phương
trình được cho bởi các phương trình bậc nhất. Ta có 6x − 4 ≡ 6 (mod 13) và 6x −
4 ≡ 7 (mod 13), chúng có hai nghiệm là x ≡ 6 (mod 13) và x ≡ 4 (mod 13).


12

Chú ý rằng ví dụ trên có chính xác hai nghiệm. Nhưng ví dụ tiếp theo chỉ ra
rằng không phải mọi phương trình đồng dư bậc hai đều có nghiệm.
Ví dụ 2.1.2. Giải phương trình đồng dư bậc hai 3x2 + 7x + 5 ≡ 0 (mod 13).
Giải. Ta có
3x2 + 7x + 5 ≡ 0

(mod 13)

⇔ 36x2 + 84x + 60 ≡ 0
⇔ (6x + 7)2 ≡ (49 − 60)
⇔ (6x + 7)2 ≡ −11
⇔ (6x + 7)2 ≡ 2

Ví dụ 2.1.4. Tìm các thặng dư bậc hai và thặng dư không bậc hai của p = 6.


13

Giải. Ta có
12 ≡ 1

(mod 6)

22 ≡ 4

(mod 6)

33 ≡ 3

(mod 6)

42 ≡ 4 ≡ 22

(mod 6)

52 ≡ 1

(mod 6).

Theo đó, 6 có chính xác 3 thặng dư bậc hai là 1, 3, 4. Và nó có 2 thặng dư không
bậc hai là 2, 5.
Ví dụ 2.1.5. Tìm các thặng dư bậc hai và thặng dư không bậc hai của p = 13.
Giải. Ta nhận thấy rằng

• chúng lập thành một phân hoạch của tập hợp các thặng dư dương của 13

(xem Hình 2.1)

Hình 2.1: Tập các thặng dư dương của 13


14

Tiếp theo ta sẽ chỉ ra không chỉ riêng số 13 là có cùng con số thặng dư bậc hai
và con số thặng dư không bậc hai. Trước hết ta cần bổ đề sau đây.
Bổ đề 2.1.6. ([5, Lemma 11.1]) Cho p là số nguyên tố lẻ và a là số nguyên sao
cho p a. Khi đó phương trình đồng dư bậc hai
x2 ≡ a (mod p)

(2.4)

hoặc là vô nghiệm hoặc là có đúng hai nghiệm.
Chứng minh. Giả sử α là một nghiệm của phương trình (2.4), ta có α2 ≡ a
(mod p). Đặt β = p − α. Khi đó β 2 = (p − α)2 ≡ (−α)2 ≡ α2 ≡ a (mod p). Do đó
β cũng là một nghiệm của phương trình đã cho. Ngoài ra, ta thấy α và β không

đồng dư với nhau (vì nếu ngược lại β ≡ α (mod p) thì ta có p − α ≡ α (mod p),
tức là −α ≡ α (mod p), nên 2α ≡ 0 (mod p). Nhưng ta biết (2, p) = 1, do đó α ≡ 0
(mod p), điều này mâu thuẫn. Do đó α và p − α là hai đại diện cho hai nghiệm

của phương trình (2.4).
Giả sử phương trình (2.4) còn có nghiệm thứ ba là γ. Khi đó γ 2 ≡ α2 (mod p),
suy ra p | (γ 2 − α2 ). Kéo theo γ ≡ α (mod p) hoặc γ ≡ −α (mod p). Điều đó có
hệ quả là phương trình đồng dư không có nhiều hơn 2 nghiệm.


52 ≡ 122 ≡ 8

(mod 17)

62 ≡ 112 ≡ 2

(mod 17)

82 ≡ 92 ≡ 13

(mod 17).

72 ≡ 102 ≡ 15

(mod 17)

Tương tự q = 23 có (23 − 1)/2 = 11 thặng dư bậc hai và có 11 thặng dư không
bậc hai.
Ví dụ 2.1.9. Tìm số thặng dư bậc hai của số nguyên tố Fermat.
Giải. Hiện nay, chúng ta mới biết 5 số nguyên tố Fermat ứng với n = 0, 1, 2, 3
và 4. Theo đó, ta có:
0

• Số thặng dư bậc hai của f0 = 22 + 1 = 3 là
3−1
f0 − 1
=
= 1.
2

• Số thặng dư bậc hai của f4 = 22 + 1 = 65537 là
4

4

4
f4 − 1
22 + 1 − 1
22
=
=
= 22 −1 = 215 .
2
2
2


16

2.1.3

Tiêu chuẩn Euler và ký hiệu Legendre

Đến giờ ta vẫn chưa có câu trả lời cho câu hỏi “Khi nào thì phương trình
đồng dư x2 ≡ a (mod p) là giải được?” Mục này sẽ tìm hiểu câu trả lời này.
Định lý 2.1.10 (Tiêu chuẩn Euler, [5]). Cho p là số nguyên tố lẻ. Khi đó một
số nguyên dương a (với p

a) là một thặng dư bậc hai của p khi và chỉ khi


a(p−1)/2 ≡ 1 (mod p) nên suy ra a(p−1)/2 ≡ −1 (mod p). Do đó, nếu a là thặng dư

không bậc hai của p, thì ta phải có a(p−1)/2 ≡ −1 (mod p).
Ngược lại, cho a là số nguyên thỏa mãn p a và a(p−1)/2 ≡ −1 (mod p). Khi
đó a không thể là thặng dư bậc hai (vì nếu ngược lại, theo tiêu chuẩn Euler,
ta có a(p−1)/2 ≡ 1 (mod p); điều này kéo theo −1 ≡ 1 (mod p), tức là p = 2, mâu
thuẫn). Do đó, nếu a(p−1)/2 ≡ −1 (mod p), thì a phải là thặng dư không bậc hai.
Các lập luận trên đã chứng minh được kết quả sau.
Hệ quả 2.1.13 ([5]). Cho p là số nguyên tố lẻ. Khi đó một số nguyên dương a
(với p a) là thặng dư không bậc hai khi và chỉ khi a(p−1)/2 ≡ −1 (mod p).
Ví dụ 2.1.14. Cho số nguyên tố p = 1213. Ta tính được
5(1213−1)/2 ≡ 5606 ≡ (5101 )6 · 56
≡ (−252)6 · 1069 ≡ 497 · 1069 ≡ −1

(mod 1213).

Theo hệ quả trên, 5 là thặng dư không bậc hai của 1213.
Chú ý 2.1.15. Như vậy ta đã khẳng định được rằng với một số nguyên tố lẻ p
và một số nguyên dương a, ta thấy a là một thặng dư bậc hai của p nếu và chỉ
nếu a(p−1)/2 ≡ 1 (mod p); ta cũng thấy a là thặng dư không bậc hai của p nếu và
chỉ nếu a(p−1)/2 ≡ −1 (mod p).
Theo tiêu chuẩn Euler, phương trình đồng dư (2.4) giải được khi và chỉ khi
a(p−1)/2 ≡ 1 (mod p). Mặc dù Định lý 2.1.10 cho ta một công cụ kiểm tra tính

giải được của phương trình đồng dư, nhưng công cụ này không khả thi khi số
nguyên tố p thực sự lớn. Chẳng hạn, không dễ để áp dụng tiêu chuẩn xác định
tính giải được của phương trình x2 ≡ 3797 (mod 7297). Vì vậy, bây giờ ta cần
thêm công cụ khác để đơn giản hóa nhiệm vụ kiểm tra tính giải được của thặng
dư (2.4), đó là công cụ về “ký hiệu Legendre” sẽ được nghiên cứu tiếp theo sau
đây.

(mod 7297), ta cần phải tính kí hiệu Legendre (3797/7297). Nhưng bằng cách nào

để tính được nó? Ta không có đủ công cụ để làm việc với kí hiệu này, vì thế ta
biểu diễn ba tính chất cơ bản của kí hiệu Legendre trong định lý dưới đây.
Định lý 2.1.20 ([5]). Cho p là một số nguyên tố lẻ, và a, b là các số nguyên
bất kỳ thỏa mãn p ab. Khi đó
(1) Nếu a ≡ b (mod p) thì (a/p) = (b/p).
(2) (a/p)(b/p) = (ab/p).
(3) (a2 /p) = 1.
Chứng minh. (1) Giả sử a ≡ b (mod p) và phương trình x2 ≡ a (mod p) giải được;
tức là (a/p) = 1. Vì a ≡ b (mod p), nên phương trình x2 ≡ b (mod p) cũng giải
được. Do đó (b/p) = 1 = (a/p). Mặt khác, giả sử x2 ≡ a (mod p) không giải được,
tức là (a/p) = −1. Vì a ≡ b (mod p), nên x2 ≡ b (mod p) cũng không giải được.
Do đó (b/p) = −1 = (a/p). Vì vậy trong cả hai trường hợp ta có (a/p) = (b/p).


19

(2) Theo tiêu chuẩn Euler, ta có (ab/p) ≡ (ab)(p−1)/2 ≡ a(p−1)/2 b(p−1)/2 ≡ (a/p)(b/p)
(mod p). Một lần nữa, vì p lẻ và giá trị của ký hiệu Legendre chỉ là 1 hoặc là −1,

nên (ab/p) ≡ (a/p)(b/p) (mod p) khi và chỉ khi (ab/p) = (a/p)(b/p).
(3) Theo phần (2), ta có (a2 /p) = (a/p)(a/p). Nhưng vì (a/p) = ±1, nên ta có
(a2 /p) = 1 trong cả hai trường hợp. Điều này kết thúc chứng minh.

Chú ý 2.1.21. Tính chất (2) và (3) ở Định lý 2.1.20 giúp ta có thể tính toán
giá trị của ký hiệu Legendre (a2 b/p) với p ab miễn là ta biết giá trị của ký hiệu
Legendre (b/p). Thật vậy, ta có
(a2 b/p) = (a2 /p)(b/p)
= (b/p)


=

1
−1

nếu p có dạng 4k + 1
nếu p có dạng 4k + 3
nếu p ≡ 1 (mod 4)
nếu p ≡ −1 (mod 4).

Theo hệ quả trên, ta thấy −1 là thặng dư bậc hai của p khi và chỉ khi p ≡ 1
(mod 4); tức là x2 ≡ p − 1 (mod p) là giải được khi và chỉ khi p ≡ 1 (mod 4).


20

Chẳng hạn, x2 ≡ 12 (mod 13) là giải được, nhưng x2 ≡ 22 (mod 23) không giải
được (vì 23 ≡ 1 (mod 4)).
Hệ quả 2.1.22 có thể được dùng để tính toán các ký hiệu Legendre có dạng
(−a2 /p) như ta chỉ ra ở ví dụ sau.

Ví dụ 2.1.23. Hãy tính (−4/41) và (−9/83)?
Giải. Ta có
(−4/41) = (4/41)(−1/41) theo tính chất (2) của Định lý 2.1.20
= (−1/41) theo tính chất (3) của Định lý 2.1.20
= 1 theo Hệ quả 2.1.22,
(−9/83) = (9/83)(−1/83)
= (−1/83)
= −1 theo Hệ quả 2.1.22.

quả 2.1.24. Vì vậy,

n

n

(pei i /p)

(a/p) =
i=1

(pi /p)ei .

=
i=1

Kết quả này được áp dụng để tính (a/p) miễn là ta biết các giá trị (pi /p) với
mọi ước nguyên tố pi của a, như minh họa sau đây.
Ví dụ 2.1.27. Sử dụng kết quả (2/23) = 1 và (5/23) = −1, hay tính (5000/23).
Giải. Ta có 500 = 23 54 . Do đó từ Hệ quả 2.1.26, ta có (500/23) = (2/23)3 (5/23)4 =
13 .(−1)4 = 1.

Chú ý 2.1.28. Làm thế nào để tính được (2/23) = 1 và (5/23) = −1? Ta có thể
sử dụng tiêu chuẩn Euler để tính chúng, nhưng ta muốn tránh điều tẻ nhạt đó.
Thay vào đó, ta có thể tìm hiểu thêm các tính chất của kí hiệu Legendre trong
phần tiếp theo, nhằm giúp ta tính toán (a/p) được thuận lợi hơn. Để làm điều
này, mục tiếp theo ta giới thiệu và chứng minh một tiêu chuẩn của Gauss.

2.1.4


23.
Có k = 11 − ν = 11 − 5 = 6 thặng dư, từ r1 đến r6 , là nhỏ hơn p/2, cụ thể là
2, 4, 5, 7, 9 và 10; không có hai số nào là đồng dư modulo 23.

Ngoài ra, không có số nào đồng dư với 11, 8, 6, 3 hoặc 1 modulo 23. Do đó
các thặng dư 2, 4, 5, 7, 9, 10, 11, 8, 6, 3 và 1 là dương và ≤ (p − 1)/2. (Đủ để làm ta
ngạc nhiên, chúng là một hoán vị của các thặng dư từ 1 đến (p − 1)/2 modulo
p).

Bây giờ ta sẵn sàng để đi đến cột mốc tiếp trong tiến trình của ta, cột mốc
này được khám phá bởi Gauss năm 1808. Chứng minh của kết quả này hơi dài
và do đó ta cần kiên nhẫn theo dõi.
Định lý 2.1.31 (Bổ đề Gauss, [5]). Cho p là số nguyên tố lẻ và a là số nguyên sao
cho p a. Cho ν là số các thặng dư dương nhỏ nhất trong các số a, 2a, 3a, . . . (p−1)
2 a
mà lớn hơn p/2. Khi đó (a/p) = (−1)ν .
Chứng minh. Gọi r1 , r2 , . . . , rk là các thặng dư dương nhỏ nhất của các số nguyên
a, 2a, 3a, . . . , [(p − 1)/2]a modulo p mà chúng ≤ p/2, và s1 , s2 , . . . , sν là các thặng

dư trong số đó lớn hơn p/2. Khi đó k + ν = (p − 1)/2.
Xét các số nguyên r1 , r2 , . . . , rk , p − s1 , p − s2 , . . . , p − sν . Mỗi số trong chúng
đều là số dương và nhỏ hơn p/2. Ta cần chỉ ra rằng không có hai số nào trong
chúng đồng dư modulo p.
Đầu tiên, chú ý rằng không có hai số nào trong các số ri đồng dư (vì nếu
ri ≡ rj (mod p) thì ti a ≡ tj a (mod p) với ti , tj sao cho i < j và 1 ≤ ti , tj ≤ (p−1)/2.