ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
---------------------

ĐẶNG THU HƯỜNG

ĐỊNH LÝ, BÀI TOÁN VỀ LÝ THUYẾT
CHIA HẾT VÀ ĐỒNG DƯ

LUẬN VĂN THẠC SĨ KHOA HỌC

Hà Nội – Năm 2017


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
---------------------

ĐẶNG THU HƯỜNG

ĐỊNH LÝ, BÀI TOÁN VỀ LÝ THUYẾT
CHIA HẾT VÀ ĐỒNG DƯ

Chuyên ngành: Phương pháp toán sơ cấp
Mã số: 60 46 01 13

LUẬN VĂN THẠC SĨ KHOA HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS. TS Vũ Đỗ Long

Hà Nội – Năm 2017


MỤC LỤC
MỞ ĐẦU .........................................................................................................................
Chương 1. Các khái niệm và định lý về phép tính đồng dư .......................................

1.1Khái niệm đồng dư ...............................................................

1.2Định lý thặng dư Trung Hoa ...............................................

1.3Định nghĩa hàm Euler và công thức hàm Euler ...............

1.4Định lý Euler và định lý Wilson .........................................
Chương 2. Các bài toán về phép tính đồng dư và chia hết ......................................

2.1Bài toán chia hết với biểu thức số học ...............................

2.1.1Chứng minh quan hệ chia hế

2.1.2Tìm số dư của một phép chia

2.1.3Tìm điều kiện để xảy ra quan

2.1.4Tồn tại hay không tồn tại sự

2.2Bài toán số học có sử dụng định lý Dirichlet ....................

2.2.1Nguyên lý Dirichlet ..............


2.2.2Ứng dụng nguyên lý Dirichle

2.3Bài toán chia hết với dãy số ................................................
Chương 3. Các bài toán khác về chia hết ...................................................................

3.1Các bài toán về chữ số ........................................................

3.2Bình phương và lập phương của số nguyên .....................

3.3Một số bài toán trong các kỳ thi học sinh giỏi ..................
KẾT LUẬN ................................................................................................................
TÀI LIỆU THAM KHẢO ...........................................................................................

1


MỞ ĐẦU

Bộ môn số học là một trong những môn học thú vị, hấp dẫn nhất của toán học, bởi
nó rất gần gũi trong cuộc sống của chúng ta. Ngay từ lớp 6 các em học sinh đã được
tiếp cận và học. Bài toán chia hết là một trong những bài toán khó và lý thú của số học
thường xuất hiện trong các kì thi học sinh giỏi quốc gia và quốc tế.
Thực tế ở nước ta học sinh được học rất ít về số học nên các em không đủ kiến
thức cần thiết để tiếp cận với nội dung này. Với mong muốn giúp học sinh có khả năng
tự học, có thể lãnh hội được kiến thức cơ bản cần thiết và vận dụng kiến thức đó vào
giải dạng bài toán chia hết, tôi muốn giới thiệu đến quý thầy cô giáo, các em học sinh
chuyên đề “Định lý, bài toán về lý thuyết chia hết và đồng dư”. Bài viết được trình
bày ngắn gọn dễ hiểu, dễ tiếp cận, bao gồm ba chương cùng với phần mở đầu, kết luận
và tài liệu tham khảo. Cụ thể trong mỗi chương được trình bày như sau:
Chương 1: Các khái niệm, định lý về đồng dư

Chương 2: Các bài toán về phép tính đồng dư, chia hết
Chương 3: Các bài toán khác về chia hết
Chương 1: Nhắc lại các khái niệm cơ bản liên quan đến đồng dư, chia hết. Phần
sau trình bày các định lý liên quan đến đồng dư, chia hết sẽ sử dụng trong luận văn.
Chương 2: Tổng hợp các bài toán về phép tính đồng dư, chia hết bao gồm bài toán
chia hết với biểu thức số học, bài toán số học có sử dụng nguyên lý Dirichlet và chia
hết với dãy số.

2


Chương 3: Giới thiệu một số bài toán chia hết trong các kỳ thi học sinh giỏi, đặc
biệt đã vận dụng lý thuyết đồng dư để giải một số bài toán trong kỳ thi HSG Quốc gia
từ 1962-2012.
Để hoàn thành luận văn này, trước nhất tôi xin được bày tỏ lòng biết ơn chân
thành và kính trọng sâu sắc tới PGS.TS.Vũ Đỗ Long, trường Đại học Khoa học Tự
nhiên Hà nội, người thầy đã tận tình hướng dẫn, giúp đỡ trong suốt quá trình hoàn
thành bản luận văn này. Qua đây tôi cũng xin được gửi lời cảm ơn chân thành các thầy
cô đã đọc, đánh giá và cho những ý kiến quý báu để luận văn được phong phú và hoàn
thiện hơn. Tác giả cũng xin chân thành cảm ơn Ban giám hiệu, phòng Sau Đại học,
khoa Toán-Cơ -Tin học trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà nội
đã tạo điều kiện thuận lợi cho tác giả trong suốt quá trình học tập tại trường. Tuy đã có
nhiều cố gắng nhưng do thời gian và khả năng có hạn nên các vấn đề trong luận văn
vẫn chưa được trình bày sâu sắc và không thể tránh khỏi sai sót trong trình bày, mong
được sự góp ý của các thày cô và các bạn. Tác giả xin chân thành cảm ơn!
Hà Nội, ngày 26 tháng 11 năm 2016

Học viên

Đặng Thu Hường


3


Chương 1
Các khái niệm và định lý về phép tính đồng dư
1.1

Khái niệm đồng dư

Định nghĩa 1.1.1. Cho a, b, m là các số nguyên, m ≠ 0. Số a được gọi là đồng dư với b
theo môđun m nếu m là ước của (b – a).
Nếu a đồng dư với b theo môđun m thì viết a ≡ b(mod m). Ngược lại, nếu a không
đồng dư với b theo môđun m thì ta viết a ≡/ b(mod m).
Ví dụ: 2 ≡ 5(mod 3) vì 3| (5 – 2).
Nếu a ≡ b(mod m) thì b gọi là một thặng dư của a theo môđun m.
Nếu 0 ≤ b ≤ m −1 thì b gọi là một thặng dư bé nhất của a theo môđun m.
Mệnh đề 1.1.2. Cho a, b, c, m là những số nguyên m ≠ 0. Khi đó, ta có
(i)

a ≡ a (mod m),

(ii)

Nếu a ≡ b(modm) thì b ≡ a(mod m),

(iii)

Nếu a ≡ b(mod m) và b ≡ c(mod m) thì a ≡ c(mod m).


Chứng minh. Mệnh đề (i), (ii) là hiển nhiên, ta chứng minh mệnh đề (iii).
Thật vậy, ta có a ≡ b (mod m), b ≡ c (mod m) suy ra m|(b – a) và m|(c – b). Do đó m|
(b − a + c – b), hay m|(c – a). Vậy a ≡ c(mod m).

4


Tiếp theo, ký hiệu a là tâp hợp tất cả các số nguyên đồng dư với a theo môđun m,
a = { n ∈ | n ≡ a (mod m) }. Nói cách khác, a là tập hợp các số nguyên có dạng {a +

km}.
Từ đó, ta có định nghĩa sau.
Định nghĩa 1.1.3. Một tập gồm các phần tử dạng a ={ a + km, k ∈ }gọi là một lớp đồng
dư của a theo môđun m.
Ví dụ với m = 2, ta có lớp 0 là tập các số nguyên chẵn, lớp 1 là tập các số nguyên
lẻ.
Mệnh đề 1.1.4. Cho a, b, m là những số nguyên m ≠ 0 . Khi đó, ta có:
(i)

a = b khi và chỉ khi a ≡ b (mod m),

(ii)

Có đúng m lớp đồng dư phân biệt theo môđun m.

Chứng minh. (i) Giả sử a = b , ta xét a ∈ a = b . Do đó, a ≡ b (mod m). Ngược lại, nếu a
≡ b (mod m) thì a ∈b . Ngoài ra, nếu c ≡ a (mod m).thì c ≡ b (mod m). Điều này chứng tỏ
rằng a ⊆ b . Hơn nữa, từ a ≡ b (mod m) ta suy ra b ≡ a (mod m), hay b ⊆ a . Từ đó suy ra a =
b.


(ii) Để chứng minh phần này, ta chứng minh tập {0, 1, ..., m −1} là m lớp đồng dư phân
biệt theo môđun m. Thật vậy, giả sử tồn tại 0 ≤ k < l < m sao cho k = l . Khi đó, theo (i)
ta có k ≡ l (mod m) hay m | (l − k) . Điều này mâu thuẫn với giả thiết 0 < l – k < m. Do
đó, k ≠ l . Ngoài ra, với mỗi a ∈ luôn tồn tại cặp số nguyên q, r sao cho a = qm + r , 0 ≤
r < m , suy ra a ≡ r (mod m) hay a = r .

5


Định nghĩa 1.1.5. Tập gồm m phần tử A = { a1, a2, …, am} gọi là một hệ thặng dư đầy
đủ theo mô đun m nếu B = {a1 , a2 ,..., am} là tập gồm m lớp đồng dư phân biệt theo mô
đun m.
Từ định nghĩa ta thấy rằng, hệ thặng dư đầy đủ theo mô đun m là không duy nhất.
Ví dụ các tập {0, 1, 2, 3}, {4, 9, 14, −1}, {0, 1, −2, −1} là những hệ thặng dư đầy đủ
theo mô đun 4.
Mệnh đề 1.1.6. Nếu a ≡ c (mod m), b ≡ d (mod m) thì a + b ≡ c + d (mod m) và ab ≡ cd
(mod m).
Chứng minh. Ta có (a + b) – (c + d) = (a – c) + (b – d).
Vì a – c ⋮ m, b – d ⋮ m, suy ra [(a + b) – (c + d)] ⋮ m hay a + b ≡ c + d (mod m)

+ Ta có ab – cd = (ab – bc) + (bc – cd) = b(a – c) + c(b – d)
Vì a – c ⋮ m, b – d ⋮ m, suy ra ab – cd ⋮ m hay ab ≡ cd (mod m).

Mệnh đề 1.1.7. Cho a, b, c, m là các số nguyên, m > 0, ac ≡ bc (mod m) và d = (c, m).
Khi đó ta có
a ≡ b (mod

m
d ).


Chứng minh. Giả sử ac ≡ bc (mod m). Ta có m|(bc – ac), suy ra tồn tại số nguyên k sao
cho c(b – a) = km. Khi đó, chia hai vế cho d ta được

Ngoài ra, theo giả thiết ta có d = (c, m), suy ra

hay a ≡ b (mod

m

d ).

6


Mệnh đề 1.1.8. Cho a, b, m1, …, mk là các số nguyên, m1, m2, …, mk > 0, a ≡ b (mod
m1), a ≡ b (mod m2),…, a ≡ b (mod mk). Khi đó, ta có
a ≡ b (mod[m1 , m2 ,..., mk ] )

trong đó [m1 , m2 ,..., mk ] là bội chung nhỏ nhất của m1, m2, …, mk.
Chứng minh. Suy ra trực tiếp từ định nghĩa.
Mệnh đề 1.1.9. Nếu a ≡ b (mod n) thì an ≡ bn (mod n2 ) .
Chứng minh. Từ a ≡ b (mod n).suy ra a = b + nq. Do đó, theo công thức khai triển nhị
thức ta có
n

n

n

a – b = (b + nq) – b

=

n

n

n
n
b n −1qn +
b n −2 q 2 n 2 + ... +
q n nn
 

1   2  n


=








 n
 n

n 2 b n −1q +   b n −2 q 2 + ... +  q n nn 





2

n







2

Từ đó suy ra a n ≡ bn (mod n ).
2

Điều ngược lại không đúng, ví dụ như 34 ≡14 (mod 4 ) nhưng 3 ≡/1 (mod 4).

Mệnh đề 1.1.10. Nếu a, b là các số nguyên và p là số nguyên tố thì


a + b ) p ≡ a p + b p (mod p)

Chứng minh. Theo công thức khai triển nhị thức ta có:

(a + b )

7



Do đó, để chứng minh mệnh đề ta chỉ cần minh
có
p
 

k

 

suy ra

Từ đó,
1.2

Định lý thặng dư Trung Hoa

Tương tự với hệ phương trình bậc nhất, ta có thể đặt bài toán cho hệ phương trình đồng
dư như sau:
Cho a1, a2, …, an; b1, b2, …, bn; m1, m2, …, mn là các số nguyên, mi > 0 với mọi i
= 1, 2, …, n. Khi nào hệ phương trình sau có nghiệm
a1 x + b1 ≡ 0 (mod m1 )
a2 x + b2 ≡ 0(mod m2 )



...

an x + bn ≡ 0(mod mn )


Trước tiên, ta xét trường hợp m1, m2, …, mn đôi một nguyên tố cùng nhau. Để
hệ phương trình này có nghiệm, trước hết mỗi phương trình đồng dư tuyến tính


8


ai x + bi ≡ 0 (mod mi) trong hệ phải có nghiệm. Vì vậy ta có thể đưa hệ phương trình
trên về dạng sau đây
x ≡ r1 (mod m1 )


x ≡ r2 (mod m2 )



...

x ≡ rn (mod mn )

Trong đó x ≡ ri (mod mi ) là nghiệm của phương trình ai x + bi ≡ 0 (mod mi). Định
lý sau đây là định lý quan trọng
Định lý 1.2.1. Cho m1, m2, …, mn là các số nguyên dương đôi một nguyên tố cùng nhau,
r1 , r2 ,..., rn là các số nguyên bất kì. Khi đó hệ phương trình đồng dư trên luôn có

nghiệm.
Nếu x0 và x1 là hai nghiệm thỏa mãn hệ phương trình trên thì x0 ≡ x1 (mod m) với
m = m1m2 ...mn . Tức là hệ phương trình đồng dư trên luôn có nghiệm duy nhất modulo


m.
Chứng minh.

Đặt si =

m

, do giả thiết m1, m2, …, mn là các số nguyên dương đôi một mi

nguyên tố cùng nhau nên ta có (si, mi) = 1với mọi i = 1, 2, …, n.
Do đó với mỗi i tồn tại một số nguyên si thảo mãn si si ≡1 (mod mi).
Đặt
x0 = s1 s1r1 + s2 s2 r2 + ... + sn s2n rn .
Vì sj chia hết cho mi nếu j ≠ i nên x0 ≡ si si ri ≡ ri (mod mi) với mọi 1 ≤ i ≤ n . Tức là
hệ phương trình đồng dư đã cho có nghiệm.

9


Giả sử x1 là một nghiệm khác của hệ phương trình đồng dư trên. Khi đó ta có
x1 − x0 ≡ 0 (mod mi) hay x1 − x0 mi với mọi 1 = 1, 2, …, n. Do m1 , m2 ,..., mn là các số đôi
một nguyên tố cùng nhau nên từ đó suy ra x1 − x0 m1m2 ...mn . Định lý được chứng minh.

Trong trường hợp m1 , m2 ,..., mn là các số nguyên dương tùy ý, điều kiện để hệ
phương trình đồng dư có nghiệm là bất cứ hai phương trình đồng dư tuyến tính
nào trong hệ cũng có nghiệm chung. Ta có định lý sau
Định lý 1.2.2. Cho m1 , m2 ,..., mn là các số nguyên dương r1 , r2 ,..., rn là các số nguyên
bất kì. Khi đó điều kiện cần và đủ để hệ phương trình đồng dư trên có nghiệm là
ri ≡ rj (mod (mi , mj )), ∀1 ≤ i < j ≤ n.


Nếu x0 và x1 là hai nghiệm thỏa mãn hệ phương trình trên thì x0 ≡ x1 (mod m) với
m = [m1 , m2 ,..., mn ]. Tức là hệ phương trình đồng dư trên có nghiệm thì nghiệm đó là
duy nhất modulo m.

Chứng minh. Trước hết, giả sử hệ phương trình đã cho có nghiệm x0. Đặt (mi , mj )=
d, ta có
x0 − ri ≡ 0 (mod mi) x0 − rj ≡ 0 (mod mj)
Nên x0 − ri ≡ x0 − rj ≡ 0 (mod d) hay ri ≡ rj (mod (mi , mj )). Do i, j được chọn tùy
ý nên
ri ≡ rj (mod (mi , mj )), ∀1 ≤ i < j ≤ n.

là điều kiện cần để hệ phương trình có nghiệm.

10


Ngược lại, ta sẽ chứng minh bằng quy nạp theo n rằng nếu điều kiện trên được thỏa
mãn thì hệ phương trình luôn có duy nhất nghiệm modulo m = [m1 , m2 ,..., mn ].
Với trường hợp n = 2, đặt

(m1 , m2 ) = d

, m1 = dd1 , m2 = dd2

Suy ra (d1 , d2 ) =1 và ri ≡ rj ≡ r (mod d) . Đặt
r1 = r + k1d , r2 = r + k2d .
Ta có
x ≡ r (mod m )



1

x ≡ r2 (mod m2 )

x−r








Do (d1 , d2 ) =1 nên theo định lý thặng dư Trung Hoa tồn tại một số nguyên dương
x sao cho

x ≡ k1 (mod d1 ) , x ≡ k2 (mod d2 ) .
Từ chứng minh trên, x là nghiệm của hệ
x ≡ k1 (mod d1 )



11


khi và chỉ khi
từ định lý thặng dư Trung Hoa suy ra hệ phương trình có nghiệm duy nhất modulo m.
Giả sử định lý đúng đến n – 1. Ta sẽ chứng minh định lý đúng đến n. Đặt

′


′

′

m1 = [m1 , m2 ,..., mn−1 ] , m2 = mn , r2 = rn .

Vì
ri ≡ rj (mod( mi , mj )) với mọi 1 ≤ i < j ≤ n

nên theo giả thiết quy nạp, hệ phương trình


≡

x

ri



(mod mi ) i = 1,
2,..., n −1

′

′

Có duy nhất nghiệm x ≡ r1 (mod m1 ) . Mặt khác từ ri ≡ rj (mod( mi , mj )) với mọi


′

′

′

′

1 ≤ i < j ≤ n suy ra r1 ≡ r2 (mod( m1 , m2 )) . Theo chứng minh trên cho trường hợp n = 2 ta

có hệ phương trình



x ≡ r1 (mod m1′)





22

x ≡ r (mod m ′)



Có nghiệm duy nhất modulo m = m ′ , m ′ = [m , m ,..., m ]. Vậy định lý đúng với n.
12 n




 12

Định lý 1.2.3. Cho m1, m2 là hai số nguyên dương nguyên tố cùng nhau. Khi đó


( m1m2 ) = φ ( m1 )φ (m2 ). Nếu m có thể phân tích chính tắc thành tích các thừa

số nguyên tố m = p1α . p2α ... pkα thì
1

2

k


12




( m) = p1α

1

−1

. p2α

2


... pkα

−1

k

−1

( p1 − 1)( p2 − 1)...( pk −1) .

Chứng minh. Đặt m = m1m2 . Giả sử {a1 , a2 ,..., ak } là một hệ thặng dư thu gọn
modulo m1, {b1 , b2 ,..., bl }là một hệ thặng dư thu gọn modulo m2.
Gọi a là một số nguyên dương bất kỳ sao cho (a, m) = 1. Khi đó (a, m1 ) = ( a, m2 )
=1 nên tồn tại duy nhất ai, bj sao cho a ≡ ai (mod m1 ) và a ≡ b j (mod m2 ) . Như vậy

mỗi lớp thặng dư thu gọn modulo m đều ứng với mỗi cặp {ai, bj}.
Ngược lại với mỗi cặp {ai, bj} bất kì, theo định lý thặng dư Trung Hoa, tồn tại duy
nhất một lớp thặng dư a thỏa mãn a ≡ ai (mod m1 ) và a ≡ b j (mod m2 ) . Do
ai , m1 ) = (b j , m2 ) =1nên (a, m1 ) = ( a, m2 ) =1và (a, m) = 1. Do đó, mỗi cặp {ai,



bj} đều

ứng với một lớp thặng dư thu gọn modulo m. Từ đó suy ra có một tương ứng một –
một giữa các cặp {ai, bj} với các lớp thặng dư thu gọn modulo m, tức là


( m) = kl =φ ( m1 )φ(m2 ) .

Hiển nhiên nếu p là một số nguyên tố thì φ( pα ) = pα −1( p −1) . Từ đó ta có
φ ( m) = ∏ φ ( piα i ) =∏φ( piα i −1 )( pi −1) .

Ví dụ 1.1. Cho p là một số nguyên tố, α1 < α 2 < ... <αn là một dãy các số
nguyên dương. Chứng minh rằng hệ phương trình đồng dư
x ≡ ri (mod pαi )

i =1, 2,..., n

có nghiệm khi và chỉ khi ri ≡ rk (mod pα ) với mọi i = 1, 2, …, k.
i


13


Giả sử m là một số nguyên dương

Lời giải.

Khi đó ta có m − r

…, n.

k

k, suy ra
r ≡ m ≡ r (mod pαi ) với mọi i = 1, 2, …, k.
i


Ngược lại, giả sử r ≡ r (mod pα ) với mọi i = 1, 2, …, k. Đặt m = r
i

ik

m ≡ r ≡ r (mod pα ) với mọi i = 1, 2, …, n
i

n

Suy ra m là một nghiệm của hệ phương trình đã cho, tức là hệ phương trình đã cho
có nghiệm. Điều phải chứng minh.
Ví dụ 1.2. Cho m là một số nguyên dương. Tìm số nghiệm của phương trình
x 2 ≡ x (mod m)

Lời giải. Giả sử m = p1α p2α ...pkα . Ta có x 2 ≡ x (mod m) khi và chỉ khi
1

2

k

x 2 ≡ x (mod pi

α

i

) với mọi i = 1, 2, … , k.


hay
x ( x − 1) ≡ 0 (mod pi

α

i

) với mọi i = 1, 2, … , k.

Vì (x, x – 1) = 1 nên phương trình x ( x − 1) ≡ 0 (mod piα ) có hai nghiệm modulo
i

piαi là x ≡ 0 (mod piαi ) hoặc x ≡1 (mod piαi ).

Theo đinh lý Thặng dư Trung Hoa, với mỗi bộ r1 , r2 ,..., rk , hệ phương trình
x ≡ ri (mod piαi )

i =1, 2,..., k

14


luôn có một nghiệm duy nhất modulo m. Do mỗi phương trình x ( x − 1) ≡ 0(mod piα )
i

đều có hai nghiệm modulo piα nên phương trình đã cho có 2k nghiệm theo modulo m.
i

1.3 Định nghĩa hàm Euler và công thức hàm Euler
Định nghĩa 1.3.1. Hàm Euler φ( n) là hàm số học có giá trị tại n bằng số các số không

vượt quá n và nguyên tố cùng nhau với n.
Ví dụ 1.3. Từ định nghĩa ta có φ(1) =1,φ(2) =1,φ(3) = 2 ,φ(4) = 2 ,φ(5) = 4 ,φ(6) = 2 ,


(7) = 6 ,φ(8) = 4 ,φ(9) = 6,φ(10) = 4 .

Từ định nghĩa trên đây, ta có hệ quả trực tiếp: Số p là số nguyên tố khi và chỉ khi


( p ) = p −1.

Định nghĩa 1.3.2. Hệ thặng dư thu gọn modulo n là tập φ( n) số nguyên sao cho mỗi
phần tử của tập nguyên tố cùng nhau với n, và không có 2 phần tử nào đồng dư với
nhau modulo n.
Nói cách khác từ hệ thặng dư đầy đủ modulo n, để lập hệ thặng dư thu gọn, ta chỉ
giữ lại những giá trị nào nguyên tố cùng nhau với n.
Ví dụ 1.4. Các số 1, 2, 3, 4, 5, 6 lập thành một hệ thặng dư thu gọn modulo 7. Đối
với modulo 8, ta có thể lấy 1, 3, 5, 7.
Định lý 1.3.3. Nếu r1 , r2 ,..., rφ ( n) là một hệ thặng dư thu gọn modulo n, và a là số nguyên
dương, (a, n) = 1, thì tập ar1 , ar2 ,..., arφ ( n) cũng là hệ thặng dư thu gọn modulo n.

Chứng minh. Hệ ar1 , ar2 ,..., arφ ( n) gồm φ( n) số nguyên.
Từ ( a, n) = ( rj , n) =1 dễ dàng suy ra (arj , n) =1, vậy mỗi số của hệ nguyên tố
cùng nhau với n.
15


Nếu có 1 ≤ i < j ≤ φ( n) để ari ≡ arj (mod n) thì n | a ( ri − rj ) . Do đó (n, a) = 1 ta
suy ra n | ( ri − rj ) hay ri ≡ rj (mod n), điều này vô lý với giả thiết ri ≡ rj (mod n)
Định lý 1.3.4. Hàm Euler là hàm nhân tính.

Chứng minh. Giả sử m, n là hai số dương nguyên tố cùng nhau. Ta cần chứng tỏ rằng
 ( mn) = φ ( m)φ( n) .

Ta sắp xếp tất cả các số nguyên dương không vượt quá mn thành bảng sau
1
2
...
R
...
M
Giả sử r là số nguyên dương không vượt quá m, và (r, m) = d > 1. Khi đó trong
hàng thứ r không có số nguyên nào nguyên tố cùng nhau với mn. Vì thế để tính


( mn) , ta chỉ cần quan tâm các số trong hàng thứ r với (r , m) =1. Các số trong

hàng

này đều nguyên tố cùng nhau với m. Mặt khác dễ thấy rằng các số trong hàng này lập
thành một hệ thặng dư đầy đủ modulo n. Do đó có đúng φ( n) số trong hàng nguyên tố
cùng nhau với n, tức là trong hàng đó φ( n) số nguyên tố cùng nhau với mn. Cả thảy có


( n) hàng như vậy, định lý đã được chứng

minh. Nhờ tính chất này ta có công thức hàm Euler
Định lý 1.3.5. Giả sử n = p1a1 p2a2 ...pkak là phân tích của n thừa số nguyên tố. Khi đó ta có

16




φ( n ) = n  1


Chứng minh. Do hàm Euler là hàm nhân tính nên ta chỉ cần chứng minh rằng với mọi
số nguyên tố p thì
(

p k ) = p k − pk −1 .
k

Thật vậy, các số nguyên dương không vượt quá p và không nguyên tố cùng nhau
k-1

với p phải có dạng sp với s nguyên dương nào đó. Có đúng p
k

số như vậy. Do đó,

k

số các số không vượt quá p và nguyên tố cùng nhau với p đúng bằng p k − pk −1 .
Định lý 1.3.6. Giả sử n là một số nguyên dương. Khi đó

∑φ( d ) = n ,
d|n

trong đó tổng được lấy theo mọi ước của n.
Chứng minh. Ta phân tích các số nguyên từ 1 đến n thành từng nhóm Cd sao cho


m ∈C khi và chỉ khi (m, n) = d, tức là khi và chỉ khi
d

n
d

của Cd
n
d


, tức là bằng φ 

với

và nguyên tố cùng nhau


17


n

Khi đó d chạy qua mọi ước của n thì d cũng chạy qua mọi ước của n, định lý
được chứng minh.
Nhận xét. Các tính chất của hàm Euler được sử dụng để tính đồng dư của những lũy
n

thừa rất lớn. Chẳng hạn, ta cần tính a mod k , trong đó n là một số nguyên lớn. Giả

sử ta có
k

= p1a p2a ...psa .
1

2

s

Khi đó a

φ ( p ai )



( pia ) thì a N ≡ a (mod k). Do đó, viết n = Nq + r với r < N, ta được

i

≡1 (mod
i

a n ≡ ar (mod k).

Ví dụ 1.3.2. Để tính 2

1000000

mod 77, ta thực hiện như sau. Ta có


77 = 11. 7, φ(7) = 6 , φ(11) =10 .

Bội chung nhỏ nhất của 6 và 10 là 30, do đó
230 ≡ 1(mod 77).

Ví dụ 1.5. Với mỗi số nguyên dương n kí hiệu f(n) là tổng của các số nguyên dương
bé hơn n và nguyên tố cùng nhau với n.
a) Chứng minh rằng f ( n) =

nφ( n)
2

b) Chứng minh rằng nếu f ( m) = f ( n) thì m = n.

Lời giải

18