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

Nội dung text: Bài giảng Toán rời rạc - Bài tập chia & đồng dư

1. 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
2. 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
3. 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
4. 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) 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) 4
5. 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 => PT vô nghiệm 5
6. 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 => 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 6
7. 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 (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 7
8. 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 PT có 4 cặp nghiệm 8
9. 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
10. 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 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 10
11. 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) => 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ố 11
12. 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 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ố 12
13. 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 => 13a+8b và 5a+3b là nguyên tố cùng nhau 13
14. 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) 20132015 ≡ -7(mod 13) ≡ 6(mod 13) Dư của phép chia 20132015 + 20142013 cho 13 là 5 14
15. 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) 20132014 ≡ 10(mod 13) Dư của phép chia 20132014 + 20142015 cho 13 là 9 15
16. 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) 20152016  92016(mod 17)  98x252(mod 17) = 1(mod 17) Dư của phép chia 20142015 + 20152016 cho 17 là 16 16
17. 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) Dư của phép chia 20142013 + 20152014 cho 11 là 6 17
18. 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) 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 18
19. 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) 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 19
20. 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) Dư của phép chia 20132014 + 20142015 cho 4 là 1 20
21. 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