CHUYÊN ĐỀ SỐ HỌC
BÀI TẬP CỦNG CỐ MỘT SỐ NỘI DUNG CƠ BẢN CỦA
LÝ THUYẾT ĐỒNG DƯ
I. Bài tập sử dụng Định lý Thặng dư Trung Hoa
Bài 1 Cho A là một tập con khác rỗng của Z +. Chứng minh rằng tồn tại số nguyên dương
n sao cho tập hợp nA = { nx / x ∈ A} chứa toàn lũy thừa của một số tự nhiên với số mũ
lớn hơn 1.
 Lời giải: Đặt A = {a1, a2,...., ak} và p1, p2,..., pk là k số nguyên tố phân biệt. Theo
định lý Thặng dư Trung Hoa, với mọi i = 1,2,..,k tồn tại số nguyên dương mi thỏa mãn
mi ≡ -1 ( mod pi) ; mi ≡ 0 ( mod pj) ( i ≠ j, j = 1,2,....,k)
Khi đó:
m1 + 1  p1

m2  p1

.......

mk  p1

m1  p2

m2 + 1  p2

.......

mk  p2

m2  pk

.......



 ĐPCM.
Bài 2 Với mọi tập số nguyên {a1, a2, a3...., an } tồn tại số nguyên dương b để tập
{ ba1, ba2, ba3...., ban } bao gồm những lũy thừa đúng của một số nguyên.
 Lời giải:


Đặt p1, p2, p3,....., pn là các số nguyên tố có mặt trong phép phân tích a 1, a2,...., an
thành thừa số nguyên tố. Ta có: ai = p1bi1. p2bi2.....pkbik.
Ta biết rằng nếu một số nguyên được phân tích thành thừa số nguyên tố
p1c1 .... p m c m là một lũy thừa bậc q khi và chỉ khi c1, c2,...., cn chia hết cho q.

Đặt b = p1d1 . p2 d 2 . p3d 3 ..... p k d k . Ta sẽ chứng minh có thể tìm được d1, d2,...., dk
mà b thỏa mãn điều kiện đề bài.
Để có ba1 là lũy thừa bậc q1 của một số nguyên thì b11 + d1, b12 + d2,..., b1k + dk
chia hết cho q1. Tương tự với ba2, ba3,...., ban, ta có:
+ b21 + d1, b22 + d2,..., b2k + dk chia hết cho q2
.......
+ bn1 + d1, bn2 + d2,..., bnk + dk chia hết cho qn.
Từ đó phải xác định d1, d2,...., dk thoản mãn d1 ≡ - bi1 (mod qi); i = 1,2,..,n.
Tương tự với d2, d3,..., dk. Ta chọn q1, q2,...., qn là những số nguyên tố phân biệt.
Áp dụng định lý Thặng dư Trung Hoa, tồn tại d1, d2,..., dk. Từ đó tồn tại b (ĐPCM).
Bài 3 Chứng minh rằng với mọi số nguyên n, tồn tại một tập số nguyên n phần tử để
tổng các phần tử các tập con không rỗng của nó là một lũy thừa.
 Lời giải:
Ta xét tập số nguyên S = { x1, x2,...., xn }, tập S có 2n – 1 tập con không rỗng của S.
Đặt:

S1, S2, S3,...., S 2 n −1


n|tn và tn là chính phương nên n2|tn ⇒ n|t.
t ≥ n>

Từ đó:

n
4

Hơn nữa, đặt: a2 = kn + 1 thì a2 ≡ 1 (mod n). Kết hợp n nguyên tố nên a ≡ ± 1(mod n)
Nhưng vì a > 1 nên a ≥ n – 1 ( với n – 1 là số nhỏ nhất đồng dư với 1 mod n). Dẫn đến:
kn + 1 ≥ (n – 1)2 ⇒ k ≥ n – 2 ⇒ k >

n
n
, vì n > 3 nên n – 2 >
4
3

2. Điều kiện đủ:
• Nếu n chỉ có một ước số nguyên tố duy nhất, đặt n = p α với p ≥ 3 do n lẻ. nếu α
chẵn, ta lấy t = 1


n2
n


Do đó phương trình f ( x) ≡ 0 (mod p) có p − 1 nghiệm mod p là 0, 1, 2, …, p – 2.

(2)

Từ (1) và (2) suy ra mọi hệ số của f (x) đều chia hết cho p.
k
k
Vậy C p−1 ≡ (−1) (mod p) ∀1 ≤ k ≤ p − 1 .

Bài 8 : Chứng minh rằng nếu p là 1 số nguyên tố thì :
C pk Mp, ∀k = 1, p − 1



Lời giải:
p −1

(

)

Đặt f ( x) = ∑ C pk x k = ( x + 1) − x p + 1 .
k =1

p

Theo định lý Fermat nhỏ : ( x + 1) ≡ x + 1 ≡ x p + 1(mo d p), ∀x ∈ ¢.
p

Do đó phương trình f ( x) ≡ 0 (mo d p) có p nghiệm. Mà deg f = p − 1 nên mọi hệ số của

NQ ≡ ( p − 1)! N (mod pN)

QN
N
≡ ( p − 1)! (mod p)
p
p

(1)

Vì (p, ( p − 1)!) = 1 nên ta được
NQ N
≡
(mod p)
p!
p

(2)

n

p
Vậy Cn ≡   (mod p).
 p

Bài 10 : Xét các số tự nhiên m, n, k thoả mãn m n n m , n k k n . Chứng minh rằng m k k m .


Lời giải:


Ta có:

(mod

) (1)

} là p-1 nghiệm của (1).
-1 =

. Với mỗi i tồn tại duy nhất

{1,2,…,p}


Thỏa mãn: (p-1)

(mod p) vì (p-1)

không chia hết cho p

Đặt
Ta có:

-1 +(p-1)

(mod

)

Ta có :

+pl => b=

)

vậy phương trình (*) có đúng p-1 nghiệm là

.

III. Hệ thặng dư
Bài 11: Cho a, b là các số nguyên Dương nguyên tố cùng nhau Số nguyên dương n được
gọi là số đẹp nếu tồn tại x,y sao cho
nếu không tồn tại

nguyên dương sao cho

CMR 1.

là số xấu lớn nhất.

. Số nguyên dương
.

được gọi là số xấu


2.CMR nếu

thì

là số đẹp khi và chỉ khi khi


là HĐĐ mod

suy ra tồn tại

sao cho

.
Do

là số nguyên dương
Vậy tồn tại
Do đó,

nguyên dương sao cho

đều là số đẹp.

là số xấu lớn nhất.

2, Giả sử là số đẹp, khi đó tồn tại

sao cho

.

Khi đó
Giả sử

là số đẹp, khi đó tồn tại

tại

sao

.
cho

Theo giả thiết k
là số xấu, suy ra

Do

. Khi đó ta có

và

nguyên dương nên n là số đẹp

Bài 12: Cho số nguyên dương n và số nguyên tố p lớn hơn n+1. Chứng minh rằng đa
thức

không có nghiệm nguyên.
 Lời giải:
Ta có

có

trong đó các hệ số

dạng

không chia hết cho

đồng thời

hệ số

đều chia hết cho nhưng không chia hết cho
sử

PT

có

nghiệm

nguyên

Khi

đó


Theo
Suy

thì
ra

mà



Chứng

chứa vô hạn số nguyên chia hết cho 7.

 Lời giải:
Giả sử chỉ có hữu hạn số trong dãy

chia hết cho 7 và

là số cuối cùng của

dãy chia hết cho 7. Từ công thức xác định của dãy ta có
Do

nên

Mặt khác

Do

nên tập

số
hơn

là HĐĐ mod 7, suy ra trong bảy
tồn tại một số chia hết cho 7 mà số này lại lớn

. Điều này mâu thuẫn với giả sử

Mặt khác

là một số chẵn (2)

Ta thấy (1) và (2) mâu thuẫn. Vậy tồn tại hai tổng
sao cho
bốn số phân biệt và bốn số

và

với

lúc đó
thỏa mãn

phải là
.

Bài 15: 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)
1

2

k

α

Bài 16: Chứng minh rằng : với mọi số nguyên dương n , tồn tại số tự nhiên n gồm n chữ
số đều lẻ và nó chia hết cho 5n.
 Lời giải:
Xét số Xn = a1 a2 a3… an =
dương

i

+

lẻ với mọi i=1,2,3,,,n và a nguyên

Ta sẽ chứng minh bài toán bằng quy nạp : với n=1 thì

a1 =5

Gỉa sử mệnh đề đứng với n . Cần chứng minh mệnh đề đúng với n+1
Xét 5 số sau đây:
a1 = 1a1 a2 a3… an =
a2=3a1 a2 a3… an =
a3= 5 a1 a2a3… an =
a4= 7a1 a2 a3… an =
a5= 9a1 a2 a3… an =
Do B=
là HĐĐ mod 5 nên : C=
cũng là HĐĐ mod 5 nên tồn tại một số trong hệ chia hết cho 5.
Trong 5 số a1,a2,a3,a4,a5 có duy nhất một số trong C chia hết cho 5(n+1) mà số này
gồm (n+1) chữ số lẻ .
Do đó mệnh đề đúng với n+1.điều giả sử đúng với mọi n


an + b( p − 1) = 1

Theo định lí Fermat nhỏ ta có:
21 = 2na.2b ( p−1) ≡ 1 (mod p) ( mâu thuẫn)

Mâu thuẫn này chứng tỏ rằng giả thiết m n ≡ 1 ( mod n) không bao giờ xảy ra.
Vậy ta có mệnh đề m n ≡ 1 ( mod n) => m ≡ 1 ( mod n) đúng khi và chỉ khi m=1 hoặc m=2
9 p −1
Bài 18 Cho p là số nguyên tố lẻ. Đặt m =
. CMR: m là một hợp số lẻ, không chia hết
8

cho 3 và 3m−1 ≡ 1 ( mod m)
 Lời giải:
Ta có:
m=

9 p −1 3p −1 3p +1
=
.
8
2
4

Dễ thấy

3p −1
3p +1
và
đều là số nguyên dương lớn hơn 1 nên m là hợp số.

p
q
q
Bài 19 Tìm các số nguyên tố p, q thỏa mãn ( 7 − 5 ) ( 7 − 5 ) ( 7 − 5 ) ( 7 − 5 )

chia hết cho pq.
 Lời giải:
Bổ

đề: (quen

x
x
Cho ( 7 − 5 ) ⋮p,

thuộc)

(7

y

− 5 y ) ⋮p với x nhỏ

nhất

thì y⋮x

Áp

dụng:

⇒ 12.2.5 p−1 Mq
⇒ 12.2Mq ⇒ q ∈ { 2;3}

Khi ấy:

(7

2

− 5 2 ) ( 7 q − 5q )

2
q
⇒ 12 ( 7 − 5q ) Mq

Mq

⇒ 12.2.5 p−1 Mq
⇒ 12.2Mq ⇒ q ∈ { 2;3}

TH2:

(7

p

− 5p ) ,

p


Như

k
k
Gọi ( 7 − 5 ) ⋮q với k đạt GTNN khi ấy theo bổ đề thì p⋮k nên mà p nguyên tố nên k=1,p

Khi k=1⇒2⋮q⇒q=2 và

dễ

tìm

ra p

p
p
Khi k=p⇒ ( 7 − 5 ) ⋮q với p là số nhỏ nhất thỏa đề, khi đó dẫn đến vô lý vì vẫn còn số nhỏ

hơn

thỏa

mãn

q −1
q −1
là ( 7 − 5 ) ⋮q (theo

Fermat


Cần chứng minh r = 1 . Giả sử r > 1 . Khi đó (m; r − 1) = 1 . Ta có:
( x m −1 − 1; x r −1 − 1) = x ( x ;r −1) − 1 = x − 1

Từ (1) và (2)=> x m − 1Mp, x r −1 − 1Mp
=> x − 1Mp => x ≡ 1 ( mod p)
=> P( x) ≡ m ( mod p) ( trái với giả thiết P( x)Mp )


Do đó r = 1 => p ≡ 1 ( mod m). ( đpcm)