Bài giảng Toán rời rạc - Bài tập chia và đồng dư

Trường đại học Cần Thơ
Khoa Công nghệ thông tin và truyền thông
Bộ môn Khoa học máy tính
BÀI TẬP CHIA & ĐỒNG DƯ
1
Bài tập 0
 CM rằng với mọi số nguyên n, dư của phép chia n2 cho 4 chỉ 
có thể là 0 hoặc 1.
n là chẵn => n = 2k => n2 = 4k2 chia hết cho 4 (dư 0)
n là lẻ => n = 2k + 1 => n2 = 4k2 + 4k +1 chia cho 4 dư 1 
2
Bài tập 1
 Tìm tất cả các nghiệm nguyên của PT: x2 – y2 = 2014
x2, y2 chia cho 4 dư 0 hoặc 1 => x2 - y2 chia cho 4 dư 0, 1, -1 (hay 3)
tuy nhiên 2014 chia cho 4 dư 2
=> PT vô nghiệm
3
Bài tập 2
 CM rằng với mọi số nguyên dương n, dư của phép chia n3
cho 7 chỉ có thể là 0, 1 hoặc 6
n = 7k => n3 = 73k3  0(mod 7)
n = 7k + 1 => n3 = (7k +1)3  1(mod 7)
4
n = 7k + 2 => n3 = (7k +2)3  1(mod 7)
n = 7k + 3 => n3 = (7k +3)3  6(mod 7)
n = 7k + 4 => n3 = (7k +4)3  1(mod 7)
n = 7k + 5 => n3 = (7k +5)3  6(mod 7)
n = 7k + 6 => n3 = (7k +6)3  6(mod 7)
Bài tập 3
 Tìm tất cả các nghiệm nguyên của PT: x3 + y3 = 2013
x3, y3 chia cho 7 dư 0, 1 hoặc 6 
=> x3 + y3 chia cho 7 dư 0, 1, 2, 5, 6
tuy nhiên 2013 chia cho 7 dư 4
5
=> PT vô nghiệm
Bài tập 4
 Trong các nghiệm nguyên không âm của PT: 3x + 5y = 2012, 
tìm nghiệm sao cho x + y nhỏ nhất
Từ PT => x = 670 - y – 2(y - 1)/3 là nguyên 
=> 2(y-1)/3 = k phải là số nguyên 
6
=> 2(y-1) = 3k => k = 2t, y = 3t + 1 => x = 669 - 5t 
Do x  0 => 669 – 5t  0 => t  133.8
Hơn nữa, x + y = 670 – 2t nhỏ nhất khi t là nguyên lớn nhất nhưng 
nhỏ hơn 133.8 => t = 133 
=> x = 4, y = 400 
Bài tập 5
 Tìm các nghiệm nguyên của PT: x + y + xy = 9
Từ PT => x + y + xy + 1 = 10 => (x+1)(y+1) = 10
(x+1) là ước của 10 => (x+1) = 1, 2, 5, 10
(x+1) = 1 => x = 0, y = 9 hoặc x = -2, y = -11 
7
(x+1) = 2 => x = 1, y = 4 hoặc x = -3, y = -6 
(x+1) = 5 => x = 4, y = 1 hoặc x = -6, y = -3
(x+1) = 10 => x = 9, y = 0 hoặc x = -11, y = -2 
Bài tập 6
 Tìm các nghiệm nguyên của PT: 2x2 + 4x = 19 – 3y2
Từ PT => 2x2 + 4x + 2 = 19 – 3y2 + 2 => 2(x+1)2 = 3(7 – y2)
7 – y2  0 và chia hết cho 2 => y lẻ và y2  7 => y = 1
=> (x+1)2 = 9 => x = 2 hoặc x = -4
8
PT có 4 cặp nghiệm
Bài tập 7
 Tìm các nghiệm nguyên của PT: 5x + 1 = 2y
5  1 (mod 4) => 5x  1 (mod 4) => 5x + 1 2 (mod 4)
=> 2y  2 (mod 4) => y = 1
=> 5x = 1 => x = 0
9
Bài tập 8
 Biết p, p + k, p + 2k là các số nguyên tố lớn hơn 3, CM rằng k 
chia hết cho 6
p, p + k, p + 2k là các số nguyên tố lớn hơn 3 => p, p + k, p + 2k phải
là số lẻ không chia hết cho 3
10
Do p, p+k cùng lẻ => (p+k) – p = k chia hết cho 2
3 số dư của phép chia p, p + k, p + 2k cho 3 là các số 1 hoặc 2 => có 2 số
dư bằng nhau => có 3 trường hợp xãy ra:
p + k ≡ p(mod 3) => k = (p + k) – p ≡0(mod 3) => k chia hết cho 3
p + 2k ≡ p(mod 3) => 2k = (p + 2k) – p ≡0(mod 3) => k chia hết 3
p + 2k ≡ (p + k)(mod 3) => k = (p + 2k) – (p + k) ≡ 0(mod 3) => k chia hết cho 3 
=> k chia hết cho 2 vừa chia hết cho 3 => k chia hết cho 6
Bài tập 9
 Có tồn tại số nguyên tố p sao cho p+2, p+4, p+8, p+16 cũng là 
các số nguyên tố?
p + 2 là nguyên tố => p  2 và p  3
Đặt p = 3 + k, do p là số nguyên tố nên k phải chẵn => k = 2t (t  0)
11
=> p = 3 + 2t, p+2 = 3 + 2(t+1), p+4 = 3 + 2(t+2)
3 số nguyên liên tiếp t, t+1, t+2 phải có số chia hết cho 3
Nếu t  0 => 1 trong 3 số p, p+2, p+4 phải có số chia hết cho 3 
=> 1 trong 3 số p, p+2, p+4 không phải số nguyên tố
Nếu t = 0 => p = 3, p+2 = 5, p+4 = 7, p+8 = 11, p+16 = 19 
là các số nguyên tố
Bài tập 10
 Bộ 3 số nguyên dương lẻ liên tiếp 3, 5 và 7 đồng thời cũng là 
các số nguyên tố. Tìm tất cả các bộ số như vậy
Xét bộ 3 số nguyên dương lẻ liên tiếp p, p+2, p+4 là các số nguyên tố
với p  3
12
Nếu p chia hết cho 3 hơn nữa p là nguyên tố => p = 3, p+2 = 5, p+4 = 7
cùng là số nguyên tố
Nếu p chia cho 3 dư 1 => p = 3t + 1 => p+2 = 3t + 3 chia hết cho 3
p+2 không là số nguyên tố
Nếu p chia cho 3 dư 2 => p = 3t + 2 => p+4 = 3t + 6 chia hết cho 3
p+4 không là số nguyên tố
Bài tập 11
 CM rằng nếu a, b là nguyên tố cùng nhau thì (5a+3b) và
(13a+8b) cũng là nguyên tố cùng nhau.
Theo Euclid, (13a+8b, 5a+3b) = (5a+3b, 3a+2b) = (3a+2b, 2a+b) 
= (2a+b, a+b) = (a+b, a) = (a, b) = 1
13
=> 13a+8b và 5a+3b là nguyên tố cùng nhau
Bài tập 12
 Tìm số dư của phép chia 20132015 + 20142013 cho 13
2014 ≡ -1(mod 13)  20142013 ≡ -1(mod 13)
2013 ≡ -2(mod 13)  20132015 ≡ (-2)2015(mod 13) ≡ -22015(mod 13)
212 ≡ 1(mod 13)  22015 = 212*167+11 ≡ 211(mod 13) ≡ 7(mod 13)
14
 20132015 ≡ -7(mod 13) ≡ 6(mod 13)
Dư của phép chia 20132015 + 20142013 cho 13 là 5
Bài tập 13
 Tìm số dư của phép chia 20132014 + 20142015 cho 13
2014 ≡ -1(mod 13)  20142015 ≡ -1(mod 13)
2013 ≡ -2(mod 13)  20132014 ≡ (-2)2014(mod 13) ≡ 22014(mod 13)
212 ≡ 1(mod 13)  22014 = 212*167+10 ≡ 210(mod 13) ≡ 10(mod 13)
15
 20132014 ≡ 10(mod 13)
Dư của phép chia 20132014 + 20142015 cho 13 là 9
Bài tập 14
 Tìm dư của phép chia 20142015 + 20152016 cho 17
2014  8(mod 17)  20148  88(mod 17)  1(mod 17)
20142015  82015(mod 17)  88x251+7(mod 17)  15(mod 17)
2015  9(mod 17)  20158  98(mod 17)  1(mod 17)
16
20152016  92016(mod 17)  98x252(mod 17) = 1(mod 17)
Dư của phép chia 20142015 + 20152016 cho 17 là 16
Bài tập 15
 Tìm số dư của phép chia 20142013 + 20152014 cho 11
2014 ≡ 1(mod 11)  20142013 ≡ 1(mod 11)
2015 ≡ 2(mod 11)  201510 ≡ 1(mod 11)  20152014 = 201510*201+4
≡ 210*201+4(mod 11) ≡ 5(mod 11)
17
Dư của phép chia 20142013 + 20152014 cho 11 là 6
Bài tập 16
 Tìm dư của phép chia 20122013 + 20142015 cho 7
2012 = 3 (mod 7)  20123  27 (mod 7)  -1 (mod 7) 
 20122013 = 20123*671  (-1)671 (mod 7)  -1 (mod 7)
2014  -2 (mod 7)  20142  4 (mod 7), 20143  -8 (mod 7)  -1 (mod 7)
18
20142015 = 20143*671+2  (-1 mod 7)(4 mod 7)  -4 (mod 7)  3 (mod 7)
20122013 + 20142015 2 (mod 7)
20122013 + 20142015 chia 7 dư 2
Bài tập 17
 Tìm số dư của phép chia 20132014 + 20142015 cho 7
2013 ≡ 4(mod 7)  20136 ≡ 1(mod 7) 
 20132014 = 20136*335+4 ≡ 20134(mod 7) ≡ 44(mod 7) = 4(mod 7) 
2014 ≡ -2(mod 7)  201412 ≡ 1(mod 7) 
19
 20142015 = 201412*167+11 ≡ 201411(mod 7) ≡ (-2)11(mod 7) ≡ 
(-2)*45(mod 7) ≡ -4(mod 7)
 20132014 + 20142015 chia cho 7 dư 0
Bài tập 18
 Tìm số dư của phép chia 20132014 + 20142015 cho 4
2013 ≡ 1(mod 4)  20132014 ≡ 1(mod 4)
2014 ≡ 2(mod 4)  20142 ≡ 0(mod 4)  20142015 = 20142*1007+1
≡ 0(mod 4)
20
Dư của phép chia 20132014 + 20142015 cho 4 là 1
Bài tập 19
 CM rằng: 20112009 + 20092011 chia hết cho 4
2011 = 2012 – 1 = 4*503 – 1  20112009 = (4*503 – 1)2009 = 4p - 1
2009=2008+1=4*502 + 1  20082011 =(4*502 + 1)2011 = 4q + 1
Ta được: 20112009 + 20092011 chia hết cho 4
21