Chuyên đề Bài toán chia hết trong số học

 CHUYÊN ĐỀ
BÀI TOÁN CHIA HẾT TRONG SỐ HỌC
 1 1.2.2. Nếu a | b và a | c thì a | mb  nc với m,n nguyên.
1.2.3. Nếu a | b và a | b  c thì a | c .
1.2.4. Với mọi số nguyên a khác 0 thì a | a .
1.2.5. Nếu a | b và b | c thì a | c .
1.2.6. Nếu a | b và b | a thì a  b .
 b
1.2.7. Nếu a | b và b  0 thì | b.
 a
1.3.Thuật chia Euclide. Cho a và b là những số nguyên, b  0 . Khi đó tồn tại duy 
nhất cặp số nguyên (q,r) sao cho a  bq  r, 0  r  b .
Ta gọi q là thương, r là phần dư. Như vậy, a chia hết cho b khi và chỉ khi phần dư 
trong thuật chia Euclide bằng 0. Ta cũng thường gọi thuật chia Euclide là phép 
chia Euclide.
II. Số nguyên tố và hợp số
2.1. Định nghĩa. Số nguyên n 1 gọi là số nguyên tố nếu nó chỉ có hai ước 
nguyên dương là 1 và chính nó. Số nguyên n 1 không là nguyên tố được gọi là 
hợp số.
2.2. Tính chất cơ bản.
2.2.1. Mỗi số nguyên dương lớn hơn 1 đều có ước nguyên tố.
2.2.2. Ước nguyên dương nhỏ nhất khác 1 của n là số nguyên tố và ước đó không 
vượt quá n .
2.2.3. Có vô hạn số nguyên tố (số nguyên tố lớn nhất đã tìm ra là 232582657 1, nó 
được tìm ra năm 2006 và nó có 9808358 chữ số).
2.2.4. (Phân tích một số theo các thừa số nguyên tố). Mỗi số nguyên dương n 1 
 1 2 k
được phân tích duy nhất thành tích các thừa số nguyên tố: n  p1 .p2 ...pk , với pi 
 
nguyên tố và i ¢ .
III. Ước chung lớn nhất, bội chung nhỏ nhất (The greatest common divisor and 
the least common multiple).
 3 4.2.1. Nếu a  b (modn) thì b  a (modn) .
4.2.2. Nếu a  b (modn) và b  c (modn) thì a  c (modn).
4.2.3. Nếu a  b (modn) và c  d (modn) thì a  c  b  d (modn) .
4.2.4. Nếu a  b (modn) và c  d (modn) thì ac  bd (modn) .
4.2.5. Nếu a  b (modn) thì với mỗi k nguyên ta có ka  kb (modn).
4.2.6. Nếu ai  bi (modn),i 1,2,...,k thì a1a2...ak  b1b2...bk (modn) . 
Đặc biệt nếu a  b (modn) thì với mỗi k nguyên dương ta có ak  bk (modn) .
4.2.7. Nếu ab  ac (modn) và (a,m) 1 thì b  c (modn) .
4.2.8. Nếu a  b (modmi ),i 1,2,...,k  a  b mod m1,...,mk . 
Đặc biệt nếu m1,m2 ,...,mk nguyên tố sánh đôi thì 
a  b (modmi ),i 1,2,...,k  a  b mod m1m2...mk  .
4.3. Định lý Fermat. Giả sử p nguyên tố, a là số nguyên sao cho (a, p) 1. 
Khi đó a p1 1 (mod p) .
 Có thể đưa ra một chứng minh đơn giản cho định lý này như sau:
Xét p 1 số a,2a,...,( p 1)a . Ta chứng minh rằng không tồn tại 2 số đồng dư với 
nhau trong phép chia cho p. Thật vậy, giả sử tồn tại ka  a (mod p) với 
k,1,2,...p 1  a(k  ) p  k   p (mâu thuẫn).
Vậy khi chia p 1 số trên cho p ta nhận được p 1 số dư khác nhau là 
1,2,..., p 1. Suy ra a.2a.....( p 1)a 1.2....( p 1) (mod p) 
  ( p 1)!.a p1  ( p 1)! (mod p) .
Vì (( p 1)!, p) 1 suy ra a p1 1 (mod p) .
Hệ quả. Nếu p nguyên tố thì a p  a (mod p).
B. MỘT SỐ PHƯƠNG PHÁP CƠ BẢN CHỨNG MINH BÀI TOÁN CHIA 
HẾT
1. Phương pháp dùng phép chia có dư.
 5 Thật vậy, ta có 3p  2 p 1 3p  3  2 p  2 p .
 3p  2 p 1 3p 1  2 p 2 .
Do p lẻ nên 3p  2 p 1 (1) p 1 0 (mod3)  3p  2 p 13
Khó khăn nhất của bài toán là chứng minh 3p  2 p 17 . Để giải quyết bước này ta 
xét hai dạng của p là p  6k 1 và p  6k  5.
Ta có 3p  2 p 1 36k 1  26k 1 1 3.93k  2.82k 1 3.23k  2 1 0 (mod7) 
Tương tự với p  6k  5. Vậy bài toán được chứng minh.
Bài tập tương tự:
Bài 1. Chứng minh rằng a3  a chia hết cho 6 với mọi số nguyên a.
Bài 2. Chứng minh rằng a(a6 1) chia hết cho 7 với mọi số nguyên a.
Bài 3. Chứng minh rằng ab(a2  b2 )(4a2  b2 ) chia hết cho 5 với mọi số nguyên 
a,b.
  x3  3x  2 
Bài 4. Tìm số phần tử của tập S  x¢ | ¢  .
  2x 1 
2. Phương pháp sử dụng đồng dư
 Nội dung của phương pháp này đơn giản chỉ là dùng các tính chất và phép 
biến đổi đồng dư để chứng minh tính chia hết hoặc tìm số dư trong một phép chia 
nào đó. 
 n
Ví dụ 1. Chứng mình rằng với mọi số nguyên dương n thì 58  23 chia hết cho 
24.
 n n1 n1 n
Lời giải. Ta có: 58  58.8  254.8 1mod24, suy ra 58  2324 (đpcm).
Ví dụ 2. Chứng mình rằng với mọi số tự nhiên n thì 122n1 11n2 chia hết cho 
133.
 7 Giả sử mệnh đề đã đúng với n, tức là xn 1720  xn  20an  3, ta chứng minh 
mệnh đề đúng với n 1. Thật vậy, ta có
 5an 5a
 xn 20an 3 3 4 n
xn1  7  7  7 .7   20m  320n 1  3 (mod20)  xn1 1720 .
Vậy xn 1720 với mọi n nguyên dương, n  2.
Ví dụ 3. Chứng minh rằng với mọi n nguyên dương thì 23n 13n .
Lời giải. Với n 1 mệnh đề hiển nhiên đúng
Giả sử mệnh đề đúng với n, tức là 23n 13n  23n  k.3n 1.
 n1 3
Ta có 23  k.3n 1  k 3.33n  k 2.32n1  k.3n1 1 3n1.t 1; t ¢  .
Như vậy, 23n1 13n1 (đpcm).
Nhận xét 1: Từ bài toán ta suy ra kết quả sau:
Tồn tại vô hạn số nguyên dương n sao cho 2n 1n . Rõ ràng cách hỏi này rất khó 
vì để làm được nó chúng ta phải đoán nhận ra một dạng tổng quát nào đó của n, 
trong bài toán này thì chỉ cần chọn n  3k là được. Đây vẫn là dạng bài khó đặc 
biệt là với học sinh THCS.
Tuy nhiên nếu đưa thêm điều kiện n nguyên tố thì có thể tìm được n thỏa mãn đề 
bài. Thật vậy, theo định lý Fecmat, 2n  2n, suy ra 3n  n  3. 
Vậy chỉ có n  3 là số nguyên tố duy nhất thỏa mãn tính chất 2n 1n .
Nhận xét 2: Ta có thể đưa ra một bài toán mà cách hỏi có bản chất khác hẳn như 
sau: Chứng minh rằng phương trình 2x 1 xy có vô hạn nghiệm nguyên dương.
 k
  23 1
Rõ rằng một họ nghiệm của phương trình này là x; y  3k ; (k ¥ ).
    k 
  3 
Bài tập tương tự: 
Bài 1. Chứng minh rằng với mọi số tự nhiên n: 
a) 25n3  5n.3n2 chia hết cho 17.
b) 52n1  2n4  2n1 chia hết cho 23.
c) 20  21  22  ...  25n1 chia hết cho 31.
 9 Lại có 33 1 (mod13)  369 1 (mod13)  370  3 (mod13) .
Như vậy, 270  370  0 (mod13) (đpcm).
Ví dụ 4. Cho p nguyên tố và a là số nguyên. Chứng minh rằng nếu p | a p 1 thì 
p2 | a p 1.
Lời giải. Ta có p | a p 1 suy ra (a, p) 1 a p1 1 (mod p) .
Suy ra a p1 1(a 1) p  (a p 1)  a(a p2 1) p  a p2 1 p .
Tương tự a p3 1 p;...;a 1 p . Do đó ak 1 (mod p) k 1, p 1.
Do đó a p 1 (a 1)a p1  a p2  ...  a 1 p2 (đpcm).
 9 p 1
Ví dụ 5. Cho p nguyên tố lẻ, đặt m  .
 8
a) Chứng minh rằng m là hợp số lẻ và m không chia hết cho 3.
b) Chứng minh rằng m 12 p .
c) Chứng minh rằng 3m1 1 (modm) .
 3p 1 3p 1
Lời giải. a) Ta có m  . , suy ra m là hợp số.
 4 2
Mặt khác m  9 p1  p p2  ...  9 1, suy ra m lẻ và m chia 3 dư 1.
b) Theo định lý Fecmat thì 9 p  9 p mà 9 p  98  9 p  98p .
 9 p  9
Vậy m 1 chia hết cho p.
 8
 9 p 1
c) Ta có 3m1 132 p 1  3m1 1m (đpcm).
 8
Ví dụ 6. Chứng minh rằng với mọi số nguyên tố p, tồn tại vô số nguyên dương n 
thoả mãn 2n  n p.
Lời giải. Nếu p  2 thì mọi n chẵn đều thoả mãn điều kiện đề bài.
Nếu p  2, khi đó theo định lý Fermat, ta có: 2m p1 1mod p, m¥ * .
 11 Với a,b nguyên , ta có an  bn a  b n¥ , n lẻ.
Tính chất này rất hiển nhiên nhưng được sử dụng nhiều trong những bài toán chia 
hết có lũy thừa của một số nguyên.
Từ tính chất này cho ta một tính chất về đa thức nguyên như sau:
 Cho đa thức P(x) có các hệ số nguyên. Khi đó P(a)  P(b) luôn chia hết 
cho a  b với mọi a,b nguyên phân biệt. Ta thử đưa ra một ví dụ áp dụng tính chất 
này.
Bài toán 1.1. Tồn tại hay không đa thức P(x) hệ số nguyên sao cho P(1)  2014 ; 
P(3)  2015?
Hint. Nếu tồn tại đa thức P(x) thỏa mãn đề bài thì P(3)  P(1) 1 phải chia hết 
cho 3 1 2 , đây là điều vô lý. Vậy không tồn tại P(x) thỏa mãn.
Bài toán 1.2. Cho đa thức P(x) hệ số nguyên. Chứng minh rằng không tồn tại ba 
số nguyên phân biệt a,b,c thỏa mãn P(a)  b;P(b)  c;P(c)  a .
Bài toán 1.3. Cho m nguyên dương sao cho 2m 1 là số nguyên tố. Chứng minh 
rằng m là số nguyên tố.
Hint. Giả sử m là một hợp số, suy ra m  pq ( p,q¥ *)
Ta có 2m 1 2 pq 12 p 1 và 2 p 11 nên 2m 1 là hợp số, trái giả thiết.
Nhấn mạnh: Tính chất rất quan trọng: Nếu m,n nguyên dương thỏa mãn mn thì 
am 1an 1.
Bài toán 2. Cho n là số nguyên dương lớn hơn 1 thỏa mãn 3n 1n. Chứng minh 
rằng n chẵn.
Phân tích bài toán. Để chứng minh một số n là chẵn ta chỉ cần chứng minh ước 
nguyên tố nhỏ nhất của n chính là 2. Khi đưa thêm yếu tố số nguyên tố vào đây ta 
có thêm nhiều công cụ để giải quyết bài toán. Đặc biệt là từ giả thiết sẽ có quan hệ 
đồng dư 3n 1 (mod p), cùng với việc áp dụng định lý Fecmat ta sẽ có thêm nhiều 
 13 p1
Bài toán 2.2. Cho p nguyên tố, a là số nguyên, 1 a  p 1. Đặt A  ak . Gọi q 
 k0
là ước nguyên tố bất kì của A. Chứng minh rằng q 1 chia hết cho p.
Bài toán 2.3. Cho n nguyên, n 1 thỏa mãn 3n 1n3 . Chứng minh rằng n chẵn và 
n không chia hết cho 4. 
Bài toán 2.4. Cho a là số tự nhiên, n nguyên lớn hơn 1 thỏa mãn an 1n2 . 
a) Chứng minh rằng n lẻ.
b) Chứng minh rằng a 1 không là lũy thừa của 2.
Hướng dẫn. a) Nếu n chẵn thì an là số chính phương, suy ra 
an  0,1 (mod4)  an 11,2 (mod4). Nhưng n2  0 (mod4) , nên đây là điều 
mẫu thuẫn.
b) Gọi p là ước nguyên tố nhỏ nhất của n, vì n lẻ nên p lẻ.
Ta có an  1 (mod p)  an 1 (mod p) . Gọi h là số nguyên dương nhỏ nhất 
sao cho ah 1 (mod p). 
Khi đó h | p 1; h | n . Từ đó chứng minh được h 1 (tương tự các bài toán trên)
Suy ra a 1 p . Vậy a 1 có ước nguyên tố lẻ, tức là a 1 không thể là lũy thừa 
của 2 (đpcm).
Bài toán 2.5. Tìm tất cả n nguyên dương sao cho 2n 1n .
Bài toán 2.6. Cho p là số nguyên tố lẻ, q,r là những số nguyên tố thỏa mãn ương 
sao cho qr 1 p . Chứng minh rằng hoặc p 12r hoặc q2 1 p .
Bài toán 3 (HSG lớp 9 Vĩnh Phúc 2009). Tìm tất cả các số nguyên dương n sao 
cho với mọi số a lẻ mà a2  n thì a | n .
Lời giải. Ta sẽ khai thác giả thiết là với mọi a lẻ thỏa mãn a2  n đều có tính chất 
a | n để chặn được a. Muốn vậy ta gọi a là số nguyên dương lẻ lớn nhất thỏa mãn 
a2  n, khi đó n  (a  2)2 .
 15