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à p 1, p2,..., p k 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 p i) ; mi 0 ( mod p j) ( i j, j = 1,2,....,k)
Khi đó:
m1 + 1 p1
m2 p1
.......
mk p1
m1 p2
m2 + 1 p2
.......
mk p2
m2 pk
.......
mk + 1 pk
.....
m1 pk
Đến đây, ta đặt:
n = a1m1 . a2 m2 . a3m3 ...... a k mk
Ta có:
mk
m1 1
m2
p
m
1
m
m
m
na1 = a1 1 . a 2 2 . a3 3 ...... a k k = ( a1 p a2 p ..... ak p ) 1
1
1
1
m
m 1
m
k p
1
2
na2 = a1m1 . a 2 m2 1 . a3m3 ...... a k mk = ( a1 p a2 p ..... ak p ) 2
2
2
2
......
mk 1
m1
m2
p
m
m
m
1
m
1
2
3
k
a
a
a
a
a
a
a
nak = 1 . 2 . 3 ...... k
= ( 1 p 2 p ..... k p ) k
k
k
k
ĐPCM.
Bài 2 Với mọi tập số nguyên {a 1, 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 a1, 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 .... pmcm là một lũy thừa bậc q khi và chỉ khi c 1, c 2,...., c n chia hết cho q.
Đặt b = p1d1 . p 2 d 2 . p3d 3 ..... p k d k . Ta sẽ chứng minh có thể tìm được d 1, d2,...., dk
mà b thỏa mãn điều kiện đề bài.
Để có ba1 là lũy thừa bậc q 1 của một số nguyên thì b 11 + d1, b12 + d2,..., b1k + dk
chia hết cho q 1. Tương tự với ba2, ba3,...., ban, ta có:
+ b21 + d1, b22 + d2,..., b2k + dk chia hết cho q 2
.......
+ bn1 + d1, bn2 + d2,..., bnk + dk chia hết cho q n.
Từ đó phải xác định d 1, d2,...., dk thoản mãn d 1 - bi1 (mod q i); i = 1,2,..,n.
Tương tự với d 2, d3,..., dk. Ta chọn q 1, 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 d 1, 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:
S 1, S2, S3,...., S n
2 1
Là tổng các phần tử của các tập này. Áp dụng bài tập 7, tồn tại số nguyên b thỏa mãn:
{ bS1, bS2, bS3,...., bS n }
2 1
Bao gồm toàn các lũy thừa. Từ đó ta chọn tập: F = { bx1, bx2, bx3,...., bxn } thì tập F
thỏa mãn điều kiện đề bài.
Bài 4 Cho m là một số nguyên dương. Tìm số lượng nghiệm của phương trình
x2 x ( mod m).
Lời giải: Giải sử m = p1a1 . p 2 a 2 . p3a3 ...... pk ak .
Ta có: x2 x ( mod m). Từ đó x2 x ( mod pi ai ) với i = 1,2,3,..,k. ( pi ai , p a j ) = 1
j
với i j, i,j {1,2,..,n} hay x(x-1) 0 ( mod pi ai ) với i {1,2,..,n}. Vậy phương trình
x(x-1) 0 ( mod pi ai ) có 2 nghiệm là x 0 ( mod pi ai ) và x 1 ( mod pi ai ).
Áp dụng định lý Thặng dư Trung Hoa, hệ x ri ( mod pi ai ), i {1,2,..,n} với
ri {0,1} chỉ có 1 nghiệm mod m nhưng lại có 2k cách chọn hệ. Vì vậy, phương trình có
2k nghiệm.
Bài 5 Cho n là số nguyên dương lẻ và n > 3. Gọi k, t là các số nguyên dương nhỏ
nhất sao cho kn + 1 và tn đều là số chính phương. Chứng minh n là số nguyên tố khi và
chỉ khi:
min {k,t} >
n
4
Lời giải:
1. Điều kiện cần: Giả sử n là số nguyên tố, khi đó:
n|tn và tn là chính phương nên n2|tn n|t.
Từ đó:
t n>
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
,
4
vì n > 3 nên n – 2 >
n
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
n
4
thì tn = p là số chính phương, mâu thuẫn với giải thiết. Nếu lẻ,
3, ta lấy: t = p <
n
p
= thì tn = p 1 , + 1 chẵn nên tn là số chính phương với
4
4
chẵn, ta lấy t = 1 <
t<
n
,
4
mâu thuẫn. Vậy = 1 hay n là số nguyên tố.
Nếu n có ít nhất 2 ước nguyên tố phân biệt. Khi đó ta có thể viết n dưới dạng
n = p .m, trong đó p là một số nguyên tố lẻ, m là số nguyên dương lẻ, (m,p) = 1. Theo
định lý Thặng dư Trung Hoa, tồn tại số nguyên s sao cho:
s 1 ( mod p )
s -1 (mod m)
n
2
Từ đó: n|s 2 – 1. Hơn nữa ta có thể chọn s sao cho: s .
Vì s không đồng dư với 1 mod m nên s 1 và s không đồng dư với -1 mod p nên
s -1. Dẫn đến s 2 -1, từ đây lấy: k =
s 2 1
thì k là số nguyên dương, hơn nữa
n
n2
n
s 2 1
s2
kn + 1 = s 2 là số chính phương và k =
<
4 = .
4
n
n
n
Mâu thuẫn với điều kiện: min {k,t} >
n
.
4
Vậy trường hợp này không thể xảy ra.
Vậy n là số nguyên tố.
II. Bài tập Phương trình đồng dư
Bài 6 : Cho p là số nguyên tố lẻ và k | p – 1. Khi đó phương trình xk – 1 = 0 (mod p) có
đúng k nghiệm phân biệt.
Lời giải:
Vì k | p – 1 nên dễ thấy xp-1 – 1 = (xk – 1)Q(x). Trong đó Q(x) là đa thức hệ số nguyên với
deg Q = p – 1 – k.
Gọi A S 1, 2,..., p 1; B S tương ứng là nghiệm của 2 phương trình :
x p1 1 (mod p) và Q( x) 0 (mod p )
Thì ta có A B S | A | | B | p 1 mà | A | k ; | B | p 1 k nên | A | | B | k .
Vậy xk – 1 = 0 (mod p) có đúng k nghiệm phân biệt.
Bài 7 : Chứng minh rằng nếu p là 1 số nguyên tố thì C pk 1 (1) k (mod p) 1 k p 1 .
Lời giải:
Xét đa thức f ( x) x 1 p1
x p 1
.
x 1
Dễ thấy bậc của f (x ) không quá p 2 .
(1)
Mặt khác theo định lí Fermat nhỏ thì:
x 1p1 1 (mod p)
x p x x 1
x x (mod p)
1 (mod p )
x 1
p
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.
Vậy C pk 1 (1) k (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 .
p
k 1
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
f ( x)
đều chia hết cho p (đpcm).
Bài 9: Cho n là số tự nhiên, p là số nguyên tố, n p. Chứng minh rằng
n
Cnp (mod p) ,trong đó x
p
là kí hiệu phần nguyên của x.
Lời giải:
Xét dãy n, n 1,..., n p 1 . Dãy gồm p số tự nhiên liên tiếp nên có đúng một số của dãy
chia hết cho p, giả sử số đó là N.Ta có
N n
.
p p
Loại số N ra khỏi dãy và xét đồng dư modulo p, ta được dãy 1, 2,..., ( p 1) (mod p) (xếp
theo thứ tự nào đó). Gọi Q là tích các số của dãy ( sau khi loại bỏ N). Ta có
Q
n(n 1)...(n p 1)
( p 1)!
N
Suy ra
(mod p).
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
Vậy Cnp (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:
Từ giả thiết suy ra m n anm , n k bk n .
Ta có (m k ) n m n anm a k n k a k b m k m
k
k
m
n
Suy ra m k k m .
n
n
Vậy m k k m .
Bài 11: cho p là số nguyên tố lẻ. chứng minh rằng với mọi n
)(*) có đúng p-1 nghiệm phân biệt.
-1 0 (mod
1 phương trình
Lời giải:
Chứng minh bằng quy nạp theo n. với n=1 khẳng định đúng. Giả sử khẳng định đúng với
n. xét phương trình
-1
Giả sử {
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
Thỏa mãn: (p-1)
(mod p) vì (p-1)
{1,2,…,p}
không chia hết cho p
Đặt
Ta có:
-1 +(p-1)
Ta có :
Do vậy
là nghiệm của (*).
(mod
)
Đảo lại: Nếu
=>
(mod
) => i=j.
Vậy phương trình có ít nhất 9 nghiệm.
Giả sừ b là nghiệm bất kì của (*). Khi đó b cũng là nghiệm của (1). Vậy tồn tại
b=
. Ta có
(p-1) t
Vậy t
1=
chia hết cho p
(mod p) => t =
b
, t để
(mod
+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.
2.CMR nếu
. Số nguyên dương
được gọi là số xấu
.
thì
là số đẹp khi và chỉ khi khi
là số xấu.
Lời giải:
Ta chứng minh
Giả sử
là số xấu lớn nhất.
là số đẹp, hay phương trình
⇒
có nghiệm nguyên dương
(do
⇒
(
Khi đó phương trình (1) tương đương với
Vậy điều gỉa sử sai, tức
Ta chứng minh mọi
vô lí.
là số xấu.
thì phương trình
có nghiệm nguyên dương.
Do
là HĐĐ mod
nên
suy ra tồn tại
sao cho
.
là số nguyên dương
Do
Vậy tồn tại
nguyên dương sao cho
Do đó,
là số xấu lớn nhất.
2, Giả sử là số đẹp, khi đó tồn tại
đều là số đẹp.
sao cho
.
Khi đó
Giả sử
là số đẹp, khi đó tồn tại
nguyên dương sao cho
mà
nguyên
Từ (2) và (3) ta có
dương nên
là số đẹp, mâu thuẫn với câu 1).
Vậy
là số xấu.
Ngược lại, đặt
Suy
. Do
ra
tồn
là HĐĐ
nên
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:
trong đó các hệ số
Ta có
có
dạng
Từ
nhất
gồm
suy ra tập
sao cho
không chia hết cho
là HĐĐ mod
, hơn nữa
thừa
số,
nên tồn tại duy
suy ra
Tương ứng với số
trong đó có hệ số
còn lại
đều chia hết cho
Giả
sử
Theo
Suy
PT
có
đồng thời
hệ số
nhưng không chia hết cho
nghiệm
nguyên
Khi
đó
thì
ra
không
mà
và
với
không chia hết cho
chia
hết
Vì
Vậy điều giả sử là sai, tức là PT
cho
nên
không có nghiệm nguyên, hay
nên
, mâu thuẫn
không có
nghiệm nguyên. (đpcm)
Bài 13: Cho dãy số
minh rằng dãy số
được xác định bởi
với
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ử
sử sai nên ta có đpcm.
là số cuối cùng trong dãy chia hết cho 7. Do giả
Bài 14: Cho các số nguyên không âm
tại bốn số nguyên phân biệt
Chứng minh rằng tồn
thỏa mãn
Lời giải:
Xét các tổng
có tất cả
Giả sử không tồn tại bốn số
tổng như vậy.
với
sao cho
là HĐĐ mod 5050. Từ đó
thì
là một số lẻ (1)
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
lúc đó
sao cho
bốn số phân biệt và bốn số
với
và
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:
x2 x (mod m).
Lời giải:
Giả sử m p1 p2 ... pk . Ta có: x2 x (mod m)
1
2
k
x2 x (mod pii ) i 1,2,..., k
Hay x( x 1) 0 (mod pi ) i 1,2,..., k
i
Vì ( x; x 1) 1 nên phương trình x( x 1) 0 (mod pi ) có 2 nghiệm mod pi là:
i
i
x 0 (mod pii ) hoặc x 1 (mod pii ).
Theo Định lý Thặng dư Trung hoa: Với mỗi bộ r1 , r2 ,..., rk thì phương trình:
x ri (mod pii ) i 1,2,..., k luôn có một nghiệm duy nhất mod m
Do mỗi phương trình x( x 1) 0 (mod pi ) đều có hai nghiệm mod pi nên phương trình
i
đã cho có 2 k nghiệm.
i
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
*
Vậy 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.
IV. Định lý Fermat nhỏ
Bài 17 Tìm tất cả các số tự nhiên m sao cho nếu m n 1 ( mod n) với n là số nguyên
dương tùy ý thì m 1( mod n).
Lời giải:
+) Giả sử m 2. Khi đó ta có:
m( m1) 1 (m 1)
2
( m1)2
1 ( mod (m 1) 2 )
Mặt khác m 1 không chia hết cho (m 1) 2 với m 2 .
Do đó mọi giá trị m 2 không thỏa mãn đề bài.
+) m 1 thỏa mãn.
+) m 2 ta có:
2n 1 ( mod n) n 1
Giả sử p là ước nguyên tố nhỏ nhất của n, khi đó:
2n 1 ( mod p)
=> p lẻ. Ta có (n; p 1) 1 . Khi đó a, b Z sao cho
an b( p 1) 1
Theo định lí Fermat nhỏ ta có:
21 2na.2b ( p1) 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
Bài 18 Cho p là số nguyên tố lẻ. Đặt m
9 p 1
. CMR: m là một hợp số lẻ, không chia hết
8
cho 3 và 3m1 1 ( mod m)
Lời giải:
Ta có:
9 p 1 3p 1 3p 1
m
.
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ố.
2
4
Mặt khác
m
9 p 1
9 p 1 9 p 2 ... 9 1 => m 1 ( mod 3) hay m không chia hết cho 3.
8
Ta thấy 9 k có tận cùng là 9 với k lẻ, có tận cùng là 1 nếu k chẵn
m 9 p 1 9 p 2 ... 9 1 (9 p 1 9 p 2 ) (9 p 3 9 p 4 ) .... (92 9) 1
Do p lẻ => m có tận cùng bằng 1=> m lẻ.
Theo định lí Fermat nhỏ: 9 p1 1 ( mod p) => 9 p 9Mp
mà 9 p 9M8, (8; p) 1
Do đó 9 p 9M8 p hay m 1
9p 9
Mp
8
Do m lẻ => m-1 chẵn => m 1M2 p => 3m1 1M32 p 1 => 3m1 1Mm ( do 32 p 1 8m )
hay 3m1 1 ( mod m)
Bài 19 Tìm các số nguyên tố p, q thỏa mãn 7 x 5x 7 y 5 y 7 p 5 p 7q 5q
chia hết cho pq.
Lời giải:
Bổ
đề: (quen
Cho 7 x 5x ⋮p,
thuộc)
7
y
5 y ⋮p với x nhỏ
nhất
thì y⋮x
Áp
dụng:
Ta
thấy p,q≠5,7
TH1: 7 p 5 p ⋮p theo Fermat nhỏ thì 7 p1 5 p1 ⋮p
7 p 5 p1.7 Mp
2.5 p1 Mp
2Mp
p2
7
2
52 7 q 5q
2
q
12 7 5q M
q
2.5 p1 Mp 2Mp p 2
M
q
12.2.5 p1 M
q
12.2M
q q 2;3
Khi ấy:
7
2
52 7 q 5q
2
q
12 7 5q M
q
M
q
12.2.5 p1 M
q
12.2M
q q 2;3
TH2:
Nếu 7q 5q ⋮q thì
7
p
5p
cm
⇒ 7 q 5q ⋮p
p
tương
như 7 p 5 p ⋮p
tự
q⇒ 7 p 5 p ⋮q
Nếu 7q 5q
vậy 7 p 5 p ⋮q và 7q 5q ⋮p
Như
Gọi 7k 5k ⋮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
Khi k=p⇒ 7 p 5 p ⋮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
là 7q1 5q1 ⋮q (theo
mãn
Fermat
nhỏ)
nên
vô
lý
Do đó trường hợp này có nghiệm giống TH1
Vậy (p,q)=(2,3),(3,2),(2,2).
Bài 20 Giả sử m, p là các số nguyên tố khác nhau. CMR nếu với số tự nhiên nào đó, p là
ước của số x m1 x m2 ... 1 thì ta có p 1 ( mod m)
Lời giải:
Giả sử p mk r , 1 r m 1 . Ta có:
x m 1 x m 2 ... 1 Mp
=> x m 1 ( mod p) (1) => x không chia hết cho p.
Ta chứng minh: x r 1 1 ( mod p) (2).
+) Nếu p m thì (2) đúng do Fermat
Giả sử p m . Nâng cả 2 vế của (1) lên lũy thừa k
x pr 1
p 1
m
ta được:
( mod p)
Theo Fermat nhỏ:
x p 1 1
( mod p)
=> x p r ( x r1 1) 0 ( mod p)
=> x r 1 1 ( mod p)
Cần chứng minh r 1 . Giả sử r 1 . Khi đó (m; r 1) 1 . Ta có:
( x m1 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)
- Xem thêm -