Chuyên đề Đồng dư thức lớp 9 - PGD & ĐT Diên Khánh

Nội dung tài liệu: Chuyên đề Đồng dư thức lớp 9 - PGD & ĐT Diên Khánh

1. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên Chuyên đề ĐỒNG DƯ THỨC I/Định nghĩa : Xét hai số 22 và 7. Chia 22 cho 5 và chia 7 cho 5,ta đều được số dư là 2. Hai số 22 và 7 cho cùng số dư (2) khi chia cho 5, ta nói 22 đồng dư với 7 theo modun 5 ta viết: 22  7 (mod5) Tổng quát, cho m Z, m>0. Ta nói các số nguyên a, b đồng dư với nhau theo modun m nếu khi chia a và b cho m ta được cùng một số dư Kí hiệu: a ≡ b (mod m) (1) Nói cách khác, a đồng dư với b theo modun m nếu a và b biểu diễn được dưới dạng: a pm r b qm r (o r m) Từ đó suy ra: a ≡ b (mod m) m\(a-b) tồn tại t Z sao cho a=b+mt Hệ thức (1) được gọi là một đồng dư thức Ví dụ :Theo định ngĩa ta có 3-(-1) 4 3 ≡ - 1 (mod 4) (5-17)  6 5 ≡ 17 (mod 6) 18 6 18≡ 0 (mod 6) Nếu a - b không chia hết cho m, ta viết a  b (mod m) II/ Các tính chất cơ bản : a) Đồng dư thức có những tính chất sau đây, tương tự các tính chất của đẳng thức: Với mọi a,b,c,d,m Z và m >0 1) a ≡ a (mod m) a 2) a ≡ b (mod m) => b ≡ a (mod m) a  b mod m 3) a  c modm b  c mod m Do tính chất (1),(2) và (3),quan hệ đồng dư là một quan hệ tương đương trong Z, Chia Z ra thành m lớp, hai số nguyên trong cùng một lớp thì đồng dư với nhau (modm), hai số nguyên khác lớp thì không đồng dư với nhau (modm) 4) a  b mod m a c  b d modm c  d mod m 1
2. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên Hệ quả : a1  b1 mod m a 2  b2 mod m a) a1 a 2 a3 ... a n  b1 b2 b3 ... bn mod m ... a n  bn mod m b) a +c≡ b (mod m) =>a≡b-c (modm) c) a ≡ b (mod m) => a c ≡ b c (mod m) d) a ≡ b (mod m) => a +mt ≡ b (mod m) (t Z ) a  b mod m 5) a c  b d mod m c  d mod m Hệ quả : a1  b1 mod m a 2  b2 mod m a) a1.a 2.a3. ... .a n  b1.b2.b3. ... .bn mod m ... a n  bn mod m b) a ≡ b (mod m) => n. a ≡ n.b (mod m) (n Z) c) a ≡ b (mod m) => an ≡ bn (mod m) với mọi n N * d)Đặc biệt khi m=p là số nghuyên tố, a=a1.a 2 .Ta khẳng định sau: a1  0 modp a  0(mod) a 2  0 modp +Nhận xét : 1) * a ≡ 1 (mod 2) và b ≡ 1 (mod 2) => a + b ≡ 2 (mod 2) Mà 2 ≡ 0 (mod 2) => a + b ≡ 0 (mod 2) * a ≡ 1 (mod 2) và b ≡ 1 (mod 2) => a.b ≡ 1(mod 2) Điều này có nghĩa : Tổng của hai số lẻ là một số chẵn, tích của hai số lẻ là một số lẻ. 2)a ≡ 3 (mod 7) => a2 ≡ 9 (mod 7) ≡ 2 (mod 2) Điều này có nghĩa : Nếu một số chia 7 dư 3 thì bình phương số đó chia 7 dư 2. Chú ý : a)Không được chia hai vế của một đồng dư thức . Ví dụ : * 2 ≡ 12 (mod 10) nhưng 1 ≡ 6 (mod 10). b) a ≡ 0 (mod m) và b ≡ 0 (mod m), nhưng a.b có thể đồng dư với 0 theo(modm) . Ví dụ : 2 ≡ 0 (mod 10) và 5 ≡ 0 (mod 10), nhưng 2.5 = 10 ≡ 10 (mod 10). Như vậy để phép chia hoặc nhân hai vế của đồng thức đòi hỏi phải kèm theo một số điều kiện . 2
3. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên 6) Nếu a ≡ b (mod m) và d là ước chung của a, b sao cho (d, m) = 1 a b a : d ≡ b : d (mod m) ( ≡ (mod m) ) d d Ví dụ: 48 ≡ 18 (mod 10) =>16 ≡ 6 (mod 10) vì (3,10)=1 Nhưng: 48 ≡ 18 (mod 10) => 8 ≡ 3 (mod 10), mặc dù 6 ƯC(48,18) nhưng 6 không nguyên tố với 10 Các tính chất đã xét cho ta các phép biến đổi mà không không làm thay đổi modun của đồng dư thức, Sau đay ta nghiên cứ các phép biến đổi trong đó có sự thay đổi modun 7) Nếu a ≡ b (mod m) => a.c ≡ b.c (mod m.c) với c Z a b m 8) Nếu a ≡ b (mod m) và d Z và d ƯC( a,b,m)  (mod ) d d d 9)Nếu a ≡ b (mod m) a  b (mod d) ( d Z và d Ư(m)) a  b(modm1) 10) Nếu a b(modm) (m =m1,m2  ) a b(modm2 ) 11)Nếu a ≡ b (mod m) thì tập hợp các ước số chung của a, m trùng với tập hợp các ước số chung của b, m, Đặc biệt (a;m)= (b;m) III: Áp dụng : Dạng 1: Chứng minh chia hết Chú ý: (a n bn )  0 (mod (a b)) a b n N (a n bn )  0 mod (a b) Nếu n lẻ (a n bn )  0 (mod (a b)) Nếu n chẳn (a b ) (a b)n bn (moda) Nếu a>0 Bài 1 : Chứng minh rằng : 22225555 + 55552222 chia hết cho 7 Giải : Cách 1:Ta có: 22225555 + 55552222 = (22225555 45555 ) (55552222 42222 ) (45555 42222 )=A+B+C Mà A(2222 4) 7.318; B(5555-4)=7.783; C=4 2222 (43333 1) 42222 (641111 1)63 7.9 Vậy: A+B+C7 Cách 2: Ta có 2222  3(mod7) 22224  34  4(mod7) 22225  3.4  5(mod7) (1) Mà 5555 4(mod7) 55552  42  2(mod7) (2) 22225555 55552222 22225.1111 55552.1111 (3) 3
4. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên Từ (1) (2) và (3) 22225555 + 55552222  21111 51111 (5 2)M  0(mod7) Vậy: 22225555 + 55552222 7 Bài 2: Chứng minh: 3100 – 3 chia hết cho 13 Giải. Ta có: 33 = 27  1 (mod 13) => 3100 = 3.399  3.1 (mod 13) => 3100- 3  0 (mod 13). Vậy 3100-3 chia hết cho 13 Bài 3 : CMR các số A = 61000 - 1 và B = 61001 + 1 đều là bội số của 7 Giải : Ta có 6 ≡ - 1 (mod 7) => 61000 ≡ 1 (mod 7) => 61000 - 1  7 Vậy A là bội của 7 Từ 61000 ≡ 1 (mod 7) => 61001 ≡ 6 (mod 7) , mà 6 ≡ - 1 (mod 7) => 61001 ≡ -1 (mod 7) => 61001 + 1  7 Vậy B là bội của 7 Bài 4: Chứng minh rằng: 301293 1chia hết cho 13 Giải: Ta có: 3012 = 13 . 231 + 9 3 3 Do đó: 3012  9 mod13 3012  9 mod13 Mà 93 729 1 mod13 31 Nên 30123 1 mod13 30123 1 mod13 Hay 301293 1 mod13 Vậy 301293 1 1 1 mod13 301293 1  0 mod13 Hay 301293 1chia hết cho 13 Bài 5 : Chứng minh rằng A = 7.52n + 12.6n chia hết cho 19 Giải : Ta có A = A = 7.52n + 12.6n = A = 7.25n + 12.6n Vì 25 ≡ 6 (mod 19) => 25n ≡ 6n (mod 19) =>7.25n ≡ 7.6n (mod 19) => 7.25n + 12.6n ≡ 7.6n + 12.6n ≡ 19.6n ≡ 0 (mod 19) . Điều này chứng tỏ A chia hết cho 19. Bai 6 : Chứng minh rằng 22002 - 4 chia hết cho 31 Giải : Ta có 25 ≡ 1 (mod 31) , mà 2002 = 5.400 + 2 Nên 22002 = (25)400 .22 Vì 25 ≡ 1 (mod 31) => (25)400 ≡ 1400 (mod 31) => (25)400.22 ≡ 1.22 (mod 31) => 22002 ≡ 4 (mod 31) => 22002 - 4 chia hết cho 31 4
5. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên Bài 7: Chứng minh 62n + 1 + 5n + 2 chia hết cho 31 ;n N Giải: Ta có: 62  5 (mod 31) => 62n  5n (mod 31) Mặt khác: 6  - 52 (mod 31) Nên: 62n + 1  -5n + 2 (mod 31) Vậy 62n + 1 + 5n + 2 chia hết cho 31. Dạng 2 : Tìm số dư của phép chia Bài 1 : Tìm số dư trong phép chia 20042004 cho 11 Sử dụng dấu hiệu chia hết cho 11 : Một số được gọi là chia hết cho 11 khi và chỉ khi hiệu giữa các tổng chữ số ở hàng lẻ và tổng các chữ số hàng chẵn kể từ trái sang phải chia hết cho 11. Ví dụ : Xét xem số 5016 có chia hết cho 11 ? Ta có (5 + 1) - (0 + 6) = 0. Vì 0  11 = > 5016  11 Giải : Ta có 2002  11 => 2004 - 2  11 => 2004 ≡ 2 (mod 11) => 20042004 ≡ 22004 (mod 11) , mà 210 ≡ 1 (mod 11) (vì 1024 - 1  11) => 20042004 = 24.22000 = 24.(210)200 ≡ 24 ≡ 5 (mod 11) Vậy 20042004 chia 11 dư 5. Bài 2: Tìm số dư trong phép chia: 29455 – 3 chia cho 9 Giải: Ta có: 2945  2 (mod 9) => 29455 – 3  25 – 3 (mod 9) Mà 25 – 3  2 (mod 9) Vậy số dư của 29455 – 3 chia cho 9 là 2 Bài 3 : Tìm số dư khi chia A = 19442005 cho 7 Giải : Ta có : 1944 ≡ -2 (mod 7) => 19442005 ≡ (-2)2005 (mod 7) Mà (-2)3 ≡ - 1 (mod 7) => (-23)668 ≡ 1668 (mod 7) hay (-23)668 ≡ 1 (mod 7) => (-23)668.(-2) ≡ - 2 (mod 7) hay (-2)2005 ≡ - 2 (mod 7) Vậy 19442005 cho 7 dư 5. 5
6. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên 100 Bài 4: Tìm số dư khi chia 3 cho 7 Giải 16 Ta có: 3100 34.396 34. 36 4 4 Ta thấy: 3 81 7.11 4 3  4 mod 7 (1) 36 729 7.104 1 36 1 mod 7 16 16 (2) 36 16 mod 7 36 1 mod 7 16 Từ (1) và (2) 34. 36  4.1 mod 7 3100  4 mod 7 Vậy 3100 chia cho 7 dư 4. 32 * Cách 2: 3100 34.396 34. 33 4 + 3 81  4 mod 7 (1) 3 + 33 27  6 mod 7 mà 6  1 mod 7 3  1 mod 7 32 32 32 Do đó, 33  1 mod 7 33 1 mod 7 (2) 32 Từ (1) và (2) 34. 32  4.1 mod 7 3100  4 mod 7 Vậy 3100 chia cho 7 dư 4. Bài 5: Tìm số dư khi chia tổng 3100 3105 cho 13 Giải * Tìm số dư khi chia 3100 cho 13: là tìm số tự nhiên nhỏ hơn 13, đồng dư với 3100 theo modun 13 32 Ta có: 3100 34.396 34. 33 +) 34 81 13.6 3 34  3 mod13 (1) +) 33 27 13.2 1 33 1 mod13 3 32 32 3 32 3 1 mod13 3 1 mod13 (2) 4 3 32 100 Từ (1) và (2) 3 . 3  3.1 mod13 3  3 mod13 (1) 35 Mặt khác: 3105 33 35 105 Mà 33 27 1 mod13 33 135 mod13 Hay 3 1 mod13 (2) Từ (1) và (2) 3100 3105  3 1 mod13 3100 3105  4 mod13 100 105 Vậy tổng 3 3 chia cho 13 dư 4 6
7. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên Bài 6 : Tìm số dư trong phép chia 15325 - 1 cho 9 Giải : Ta có 1532 ≡ 2 (mod 9) => 15325 ≡ 25 (mod 9) , mà 25 ≡ 5 (mod 9) => 15325 ≡ 5 (mod 9) => 15325 - 1 ≡ 4(mod 9) Vậy 15325 - 1 chia cho 9 dư là 4. Bài 7: Tìm dư trong phép chia 32003 cho 13. Giải : Ta có 33 ≡ 1 (mod 13) mà 2003 = 3.667 + 2 => 32003 = (33)667. 32 33 ≡ 1 => (33)667 ≡ 1667 => (33)667. 32 ≡ 1.32 (mod 13) (33)667. 32 ≡ 9 => 32003 ≡ 9 (mod 13). Vậy 32003 chia cho 13 dư 9 . Bài 8 : Tìm dư trong phép chia 570 + 750 cho 12 Giải : Ta có 52 ≡ 1(mod 12) => (52)35 ≡ 1 (mod 12) hay 570 ≡ 1(mod 12) (1) 72 ≡ 1 (mod 12) => (72)25 ≡ 1(mod 12) hay 750 ≡ 1(mod 12) (2) Từ (1) và (2) => 570 + 750 chia cho 12 dư 2. Bài 9 : Tìm số dư của A = 776776 + 777777 + 778778 khi chia cho 3 và khi chia cho 5? Giải : +Ta có 776 ≡ - 1(mod 3) => 776776 ≡ (-1) 776 (mod 3) => 776776 ≡ 1 (mod 3) 777 ≡ 0 (mod 3) => 777777 ≡ 0 (mod 3) 778 ≡ 1 (mod 3) => 778778≡ 1 (mod 3) => 776776 + 777777 + 778778 khi chia cho 3 dư 2. +Ta có 776 ≡ 1 (mod 5) => 776776 ≡ 1 (mod 5) 777 ≡ - 3 (mod 5) => 777777 ≡ - 3777 (mod 5) 778 ≡ 3 (mod 5) => 778778 ≡ 3778 (mod 5) => 776776 + 777777 + 778778 ≡ 1 - 3777 + 3778 (mod 5) Hay 776776 + 777777 + 778778 ≡ 1 + 3.3777 - 3777 (mod 5) 776776 + 777777 + 778778 ≡ 1 + 3777(3 - 1) (mod 5) 776776 + 777777 + 778778 ≡ 1 + 2.3777 Mà 32 ≡ - 1(mod 5) => (32)388.3 ≡ 3 (mod 5) Vậy A = 776776 + 777777 + 778778 ≡ 1 + 2.3 ≡ 2 (mod 5) Nên A chia cho 5 dư 2. 7
8. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên Bài 10: Tìm số dư trong phép chia: (19971998 + 19981999 +19992000 )10 chia cho 111 Giải: Ta có: 1998  0 (mod 111 => 1997  -1 (mod 111) và 1999  1 (mod 111) Nên ta có: 19971998 + 19981999 +19992000  2 (mod 111) (19971998 + 19981999 +19992000 )10  210 (mod 111) Mặt khác ta có: 210 = 1024  25 (mod 111) Vậy (19971998 + 19981999 +19992000 )10 chia cho 111 có số dư là 25 Bài 11 : Tìm số dư của A = 32005 + 42005 khi chia cho 11 và khi chia cho 13 ? Giải : +Ta có : 35 ≡ 1 (mod 11) => (35)401 ≡ 1 (mod 11) Và 45 ≡ 1 (mod 11) => (45)401 ≡ 1 (mod 11) => A = 32005 + 42005 ≡ 2 (mod 11) => A chia cho 11 dư 2 +Ta có : 33 ≡ 1 (mod 13) => (33)668. 3 ≡ 1.3 (mod 13) => 32005 ≡ 3 (mod 13) Và 43 ≡ -1 (mod 13) =>(43)668 .4≡ 1.4 (mod 13) => 42005 ≡ 4 (mod 13) => A = 32005 + 42005 ≡ 7 (mod 13) => A chia cho 13 dư 7 . Bài 12 : Bạn Minh học sinh lớp 6 đã viết một số có hai chữ số mà tổng các chữ số của nó là 14. Bạn Minh đem số đó chia cho 8 thì được số dư là 4, nhưng khi chia cho 12 thì được số dư là 3. a)Chứng minh rằng bạn Minh đã làm sai ít nhất một phép tính chia. b)Nếu phép chia thứ nhất cho 8 là đúng thì phép chia thứ hai cho 12 có dư là bao nhiêu ? Hãy Tìm số bị chia. Giải : a)Gọi số đó là n = ab (0 b 9,0 a 9 ,(a;b) N ) a b 144 (1) n 12q 3 q N (2) n 8p 4 p N (3) Từ (1) và (2) => 8p + 4 = 12q + 3 (Mà 8p + 4 là số chẵn, còn 12q + 3 là số lẻ). Do vậy bạn Minh đã làm sai một phép chia. 8
9. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên a b 14 (1) b) n 8q 4 (2) Vì a + b = 14 => ab ≡ 2 (mod 3) => 4ab ≡ 8 (mod 12) (3) Từ (2) ab ≡ 0 (mod 4) => 3ab ≡ 0 (mod 12) (4) Từ (3) và (4) => ab ≡ 8 (mod 12) => n chia cho 12 dư 8 Do n = 8p + 4 là số chẵn mà n = ab => b {0; 2; 4; 6; 8} Nếu b = 0 => a = 14 (loại ) b = 2 => a = 12 (loại) b = 4 => a = 10 (loại) b = 6 => a = 8 b = 8 => a = 6 => Số cần tìm là 86 hoặc 68 => Số bị chia là 68. Bài 13: Biết rằng ngày 20 / 11/1994 là ngày chủ nhật. Tính xem: a) Ngày 20 / 11/2011 là ngày thứ mấy? b) Ngày 20 / 11/2014 là ngày thứ mấy? Giải a) Từ 20 / 11/1994 đến 20 / 11/2011 là 17 năm có 4 năm nhuận là 1996, 2000, 2004, 2008. Vậy Từ 20 / 11/1994 đến 20 / 11/2011 có: 365 . 17 + 4 (nhuận) = 6209 (ngày) Biết rằng cứ mõi tuần lễ có 7 ngày. Ta có: 6209 = 7 . 887 Hay 6209  0 mod 7 Như vậy, 6209 ngày gồm 887 tuần Do đó, nếu ngày 20 / 11/1994 là ngày chủ nhật thì 20 / 11/1996 cũng là ngàychủ nhật. b) Từ 20 / 11/1994 đến 20 / 11/2014 là 20 năm có 5 năm nhuận là 1996, 2000, 2004, 2008; 2012. Vậy Từ 20 / 11/1994 đến 20 / 11/2014 có: 365 . 20 + 5 (nhuận) = 7305 (ngày) Biết rằng cứ mõi tuần lễ có 7 ngày. Ta có: 7305 = 7 . 1043+4 Hay  4 mod 7 Như vậy, 7305ngày gồm 887 tuần và lẻ 4 ngày Do đó, nếu ngày 20 / 11/1994 là ngày chủ nhật thì 20 / 11/2014 là ngày thứ năm Gợi ý chung: Đới với các bài toán tìm số dư trong một phép chia,khi áp dụng đồng dư thức, ta tìm cách để đi đến a ≡ b (mod m), với b có b nhỏ nhất có thể được tốt nhất là b =1 từ đó tính an ≡ bn (mod m) được thuận lợi 9
10. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên Dạng 3 : Tìm chữ số tận cùng của một số a)Tìm một chữ số tận cùng của an : -Nếu a có chữ số tận cùng là 0; 1; 5 hoặc 6 thì an lần lượt có chữ số tận cùng lần lượt là 0; 1; 5 hoặc 6. -Nếu a có chữ số tận cùng là 2, 3 hoặc 7, ta vận dụng nhận xét sau với k Z 24k ≡ 6 (mod 10) 34k ≡ 1 (mod 10) 74k ≡ 1 (mod 10) Do đó để tìm chữ số tận cùng của an với a có chữ số tận cùng là 2; 3; 7 ta lấy n chia cho 4. Giả sử n = 4k + r với r {0; 1; 2; 3} Nếu a ≡ 2 (mod 10) thì an ≡ 2n = 24k + r ≡ 6.2r (mod 10) Nếu a ≡ 3 (mod 10) hoặc a ≡ 7 (mod 10) thì an ≡ a4k + r ≡ ar (mod 10) Ví dụ 1 : Tìm chữ số tận cùng của các số : a) 62009 , b) 92008 , c) 32009 , d) 22009 Giải : a) 62009 có chữ số tận cùng là 6 (vì 6 khi nâng lên luỹ thừa với số mũ tự nhiên khác 0 vẫn bằng chính số 6) b) 92008 = (92)1004 = 811004 = 1 có chữ số tận cùng là 1 91991 = 91990.9 = (92)995.9 = 81995.9 = ( 1).9 = 9 có chữ số tận cùng là 9 Nhận xét : Số có chữ số tận cùng là 9 khi nâng lên luỹ thừa với số mũ tự nhiên chẵn khác 0 nào thì chữ số tận cùng là 1, khi nâng lên luỹ thừa với số mũ tự nhiên lẻ thì có số tận cùng là 9. c) 32009 = (34)502.3 = 81502.3 = ( 1).3 = 3 có chữ số tận cùng là 3. d) 22009 = 22008.2 = (24)502.2 = 16502.2 = ( 6).2 = 2 có chữ số tận cùng là 2 Ví dụ 2 : Tìm chữ số tận cùng của các số sau : a) 421 , b) 3103 , c) 84n + 1 (n N) d) 1423 + 2323 + 7023 Giải : a) 430 = 42.15 = (42)15 = 1615 = 6 có chữ số tận cùng là 6 421 = 420 + 1 = (42)10.4 = 1610.4 = ( 6).4 = 4 có chữ số tận cùng là 4 Nhận xét : Số nào có số tận cùng là 4 thì khi nâng lên luỹ thừa với số mũ tự nhiên chẵn thì có số tận cùng là 6, khi nâng lên với số mũ tự nhiên lẻ có số tận cùng là 4) b) 3103 = 3102.3 = (32)51.3 = 951.3 = ( 9).3 = 7 có chữ số tận cùng là 7 c) 84n + 1 = 84n.8 = (23)4n.8 = 212n.8 = (24)3n.8 = 163n.8 = ( 6).8 = . 8 có chữ số tận cùng là 8 d) 1423 = 1422.14 = ( 6).14 = . 4 2323 = 2322.23 = (232)11.23 = ( 9).23 = 7 7023 = 0 Vậy : 1423 + 2323 + 7023 = 4 + 7 + 0 = 1 có chữ số tận cùng là 1 10
11. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên b)Tìm hai số tận cùng của số an : Giả sử a tận cùng là x: 0 x 9 x N Theo nhị thức Newton: a 20 (10k x)20 (10k)20 20(10k)19 x ... 20(10k)x19 x 20  x 20 (mod100) Vậy hai chữ số tận cùng của a 20 cũng chính là 2 chữ số tận cùng của x 20 Ta có nhận xét sau : 220 ≡ 76 (mod 100) 320 ≡ 01 (mod 100) 65 ≡ 76 (mod 100) 74 ≡ 01 (mod 100) Dùng qui nạp ta có: 76n ≡ 76 (mod 100) với n ≥ 1 5n ≡ 25 (mod 100) với n ≥ 2. Từ đó suy ra với mọi k 1 a20k ≡ 00 (mod 100) nếu a ≡ 0 (mod 10) a20k ≡ 01 (mod 100) nếu a ≡ 1; 3; 7; 9 (mod 10) a20k ≡ 25 (mod 100) nếu a ≡ 5 (mod 10) a20k ≡ 76 (mod 100) nếu a ≡ 2; 4; 6; 8 (mod 10) Vậy để tìm hai chữ số tận cùng của an, ta tìm dư trong phép chia n cho 20 Bài 1 : Tìm hai chữ số tân cùng của 22003 Giải : Ta có : 220 ≡ 76 (mod 100) => 220k ≡ 76 (mod 100) Do đó : 22003 = 23.(220)100 = 8.(220)100 = ( 76).8 = 08 Vậy 22003 có hai chữ số tận cùng là 08. Bài 2: Tìm hai chữ số tận cùng của a) 2999 b) 3999 Giải 999 1000 a) Ta thấy 2 2 : 2 (1) 100 mà 21000 = 210 100 Ta có: 210 1024  1 mod 25 210  1 100 mod 25 21000 1 mod 25 Hay 21000 chia cho 25 dư 1, do đó hai chữ số tận cùng của 21000 có thể là 01; 26; 51; 75, nhưng 21000 là bội của 4 nên hai chữ số tận cùng của nó phải là 76 (2) Từ (1) và (2) ta thấy số 76 chia 2 thì hai chữ số tận cùng là 38 (= 76:2) hoặc 88(=186:2) nhưng cũng do 2999 cũng là bội của 4 nên hai chữ số tận cùng của 2999 là 88. 11
12. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên b) 3999 31000 :3 Ta có: 34 = 81  19 mod100 38 192  61 mod100 310  61.9  49 mod100 3100  4910  01 mod100 1000 3  01 mod100 , nghĩa là hai chữ số tận cùng của 31000 là 01. Số 31000 là bội của 3 nên chữ số hang trăm của nó khi chia cho 3 phải dư 2( Chia tiếp thì số 201 chia hết cho 3, nếu số dư là 0 hay 1 thì số 001, 101 không chia hết cho 3) Vậy 3999 31000 :3 có hai chữ số tận cùng là 67 (= 201 : 3) Bài 3: Cho số A = 1944 2005 a) Tìm số dư trong phép chia A cho7 b)Tìm chữ số tận cùng của A c)Tìm hai chữ số tận cùng của A Giải a)Ta có 1944 2 mod7 A  ( 2)2005 . Lại có ( 2)3  1(mod7) ( 2)2005 ( 23 )668.( 2)  2(mod7) Vậy A chia 7 dư 5 b) Chữ số tận cùng của A cũng chính là số dư của A khi chia cho 10 Vì 10=5.2 nên tìm số dư của A khi chia cho 10 là tìm số dư của A khi chia cho 2 và 5. Dễ thấy A2. Ta tìm số dư của A khi chia cho 5. Ta có 1944  1(mod5) 19442005 ( 1)2005  1(mod5) A có dạng: 5k-1 (1) Vì A chẵn nên k lẻ hay k= 2m+1 (2) Từ ( 1) và (2) A 10m 4 . Vậy A tận cùng là 4 c)Tìm hai chữ số tận cùng của A cũng có nghĩa lã tìm số dư của A khi chia cho 100. Vì 100=4.25 nên để tìm số dư của A khi chia cho 100 ta tìm số dư của A khi chia cho 4 và 25 Dễ thấy A 4. Ta tìm số dư của A khi chia cho 25 Ta có: 1994  6(mod25) A  62005 (mod25) Lại có 65 7776 1(mod25) 62005 (65 )401 1(mod25) 4m 1 Nên A 1(mod25) hay A=25k-1. Vì A4 A : chắn .Vậy k có dạng: 4m 3 Nếu k=4m+1 A 25(4m 1) 1=100m+24 (chọn) Nếu k=4m+3 A 25(4m 3) 1 100m 74 (loại) Vậy A có hai chữ số tận cùng là 24 12
13. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên Dạng4: Số chính phương ĐỊNH NGHĨA: a Z gọi là số chính phương nếu a b2 ;b Z a Z gọi là số lập phương nếu a b3;b Z MỘT SỐ TÍNH CHẤT 1)a=2k a 2 0 (mod4) 2)a=2k 1 a 2 1(mod8) 3)a 0(mod3) a 2 0(mod9) 4 4)a  o(mod3) a 2 (mod3) 5)a 1(mod3) a3 1(mod9) 6)a 1(mod3) a3  1(mod9) 7)a 2 p(p P) a 2 p2 8)a 2 p;(p P) ap a nk 2 9)a.b = m 2 2 b nq a 2 10) : gọi là hai số chính phương liên tiếp .Giữa hai số này không có số 2 (a 1) chính phương nào Bài 1: Tìm k N để cho số 2k 24 27 là một số chính phương Giải Cách 1: Giả sử 2k 24 27 =a 2 (a N ) 2k a 2 144 (a 12)(a 12) a 12 2m Ta đặt (m;n N;m n;m n k) n a 12 2 2m 2n 24 2n (2m n 1) 8.3 vì 2m n 1: lẻ 2n (2m n 1) 23.3 2n 23 n 3 n 3 n 3 k m n 8 m n m n 2 2 1 3 2 2 m n 2 m 5 Thử lại :28 24 27 400 202 Cách 2: Ta đặt 2k 24 27 =a 2 2k 144 a 2 (1) Mà 2 1(mod3) 2k ( 1)k (mod3) vì 1440(mod3) 2k 144 ( 1)k (mod3) 13
14. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên Hay a 2 ( 1)k (mod3) vì a 2 1(mod3) k 2m(2) ; m N Từ (1) và (2) a 2 (2m )2 (a 2m )(a 2m )=144 a 4 a 2m 4 a 20 a 20 a 20 Vì (a 2m )4 m m m 4 2 4 a 2 36 2 2 m 4 k 8 Thử lại :28 24 27 400 202 BÀI 2: Tìm số tự nhiên n sao cho 23 n +1971 là số một chính phương Giải Giả sử 23 n +1971=a 2 ; a Z . Ta có 23  1(mod3) 23n ( 1)n (mod3) 23n ( 1)n (mod3) vì a 2  ( 1)n (mod3) (1) 1971  0(mod3) Lại có a 2 1(mod3) (2) . Từ (1) và (2) n 2k (k N* ) Do đó 23 2k 1971 a 2 (a 23k )(a 23k ) 1971 a 23k 1 2.23k 1970 k  k a 23 1971 a 23k 27 2a 100 a 50 k a 23 73 Với a= 50 n 2. Vậy 23 n +1971=a 2 n 2 Bài 3:Chứng minh rằng : n! +2003 không thể là số chính phương Giải: Dễ dàng kiểm tra n=0; n=1 ;n=2 n! + 2003 không thể là số chính phương Với n 3 n!0(mod3) và 2003 2(mod3) . Nên (n! + 2003) 2(mod3) n! +2003 không thể là số chính phương Vậy n N n! +2003 không thể là số chính phương Bài 4: Tìm n Z sao cho :n 2 2002 là một sô chính phương Nếu n 0(mod2) n 2  0(mod4) mà 20022(mod4) Nên n 2 2002 2(mod4) n 2 2002 không là số chính phương Nếu n 1(mod2) n 2 1(mod4) mà 20022(mod4) Nên n 2 2002 3(mod4) n 2 2002 không là số chính phương Vậy không có số nguyên nào mà để: n 2 2002 là một sô chính phương 14
15. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên Bài 5: Chứng minh rằng :Nếu (n+1) và (2n+1) đều là số chính phương thì n 24 n3 Ta có 24=3.8 (3;8)=1 n8 n 1  2(mod3) n 1(mod3) 2n 1 0(mod3) n 1 Nếu n 3 :không đồng n 2(mod3) n 1  0(mod3) 2n 1 2n 1  2(mod3) thời là số chính phương .Vậy n 3 (1) Đặt a 2 2n 1 a 2 2n 1 1(mod8) 2n8 n4 n 1 là số lẻ Mà n+1=b 2 n 1 b2 1(mod8) n8(2) Từ (1) và (2) n24 (3;8) 1 *Định lý Fermat Với p là số nguyên tố ta có :a p  a(modp) Đặc biệt nếu (a,p)=1 thì a p 1 1 modp CM Giả sử p P và (a,p)=1 Dư sô khi chia a; 2a; ;( p-1)a cho p sẽ đôi một khác nhau và là những số trong các số. 1; 2; 3; ... ; p – 1, Gọi r 1 ; r 2 ; r p 1 là những số dư tương ứng trong phép chia a; 2a; ;( p-1)a cho p a  r1 (modp) 2a r2 (modp) a.2a.3a. ... . p 1 a  r1.r2.r3...rp 1 mod p Ta có: ... (p 1)a r (modp) p 1 hay (p - 1)!ap - 1 ≡ (p - 1)! (mod p). => ap - 1 ≡ 1 (mod p) (Vì (p, (p - 1)!) = 1) Áp dụng: 1) Chứng minh rằng: a 6n a 6m 7 a7 (a Z,m;n N ) GIẢI Giả sử a  7 (a;7)=1 a 6  1 (mod7) Khi đó a 6n a 6m  2 (mod7) Vô lý. Vậy a7 Ngược lại. Nếu a7 a 6n a 6m 7 15
16. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên 2)Chứng minh rằng: (324 n 1 234 n 1 5)22 n N Giải 310 1(mod11) Theo định lý Fermat ta có: 10 2 1 mod11 Ta tìm dư trong phép chia 24n 1 và 34n 1 cho 10, tức là tìm chữ số tận cùng của chúng Ta có :24n 1 2.16n 2(mod10) 24n 1 10k 2(k N) 34n 1 3.81n  3(mod10) 34n 1 10h 3(h N) 4 n 1 4 n 1 Vậy: 32 23 5 310k 2 210h 3 5 32 23 5 0(mod11) Mặt khác : 324 n 1 234 n 1 52 n N mà (11;2)=1. Nên (324 n 1 234 n 1 5)22 n N Định lý Euler Cho m Z và (a;m)=1 1.Hàm Euler: Gọi (m) là các số bé hơn m và nguyên tố cùng nhau với m, (m) được gọi là hàm Euler 2.Công thức tính hàm Euler 1 2 k * m p1 p 2 ...pk Vớipi P; i N ;i 1;2;...;k 1 1 1 Ta có (m) =m(1 )(1 )...(1 ) p1 p2 pk 3.Chứng minh định lý Euler Với (a;m)=1 thì a ( m ) 1 (mod m) Giả sử N1;N2 ;...;N (m) (m); (Ni ;m) 1; i 1;2;...; (m) . Do (a;m)=1 (Nia;m) 1 Lấy Nia chia cho m,giả sử dư là r i ,ta có: Nia  ri (modm); i 1;2;...; (m); 0 ri m (1) Mặt khác (ri ;m) (Nia;m) 1 r i là một trong các số N 1;N2 ;...;N (m) Hơn nữa các r i khác nhau đôi một vì nếu córi rj (Ni N j )am (vô lý) (m) Vậy từ (1) N1.N2....N (m)a  r1.r2....r (m) (modm) (m) N1.N2....N (m)a  N1.N2....N (m) (modm) ( m ) a 1 (mod m) vì ( N 1.N2....N (m) ;m)=1 16
17. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên Áp dụng: Bài 1: Tìm số dư trong phép chia 109345 chia cho 14 Cách 1: Giải: Ta có: 109  -3 (mod 14) => 109345  (-3)345(mod 14) Ta lại có: ( -3; 14 ) = 1 1 1 Hơn nữa: (14) = 14.(1 )(1 ) 6 2 7 Nên: (-3)6  1 (mod 14) (theo định l ý Euler) => (-3)345  (-3)3 (mod 14) Mặt khác: (-3)3 = -27  1 (mod 14) Vậy số dư trong phép chia 109345 chia cho 14 là 1 Cách 2: Ta có 109 11(mod14) 109345 11345 (mod14) 1 1 14 7.2 (m) 14(1 )(1 ) 6 7 2) Theo định lý Euler :116  1 (mod14). Hơn nữa 345=6.57+3 Nên 11345 116.57 3 113 1(mod14) Vậy dư trong phép chia 109345 cho 14 là 1 Bài 2: Tìm số dư trong phép chia 111111 cho 30 Giải 1 1 1 30=2.3.5 (30) 30(1 )(1 )(1 ) 8 2 3 5 Theo định lý Euler :118 1 mod30 Ta có : 11 3(mod8) 1111  311 mod 8 , lại có 32 1(mod8) 311 (32 )5.33 mod8 1111 8k 3 k Z Vậy 111111 118k 3 113 11 (mod 30) Do đó số dư trong phép chia 111111 cho 30 là 11 17
18. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên 34 n 1 Bài tập 3: Chứng minh 2 311 với n N Giải: 1 1 Ta có: (11) = 10; (10) = 10(1 )(1 ) = 4. 2 5 Áp dụng ĐL Euler ta có: (3; 10) = 1 => 3 (10)  1 (mod 10) 34  1 (mod 10) => 34n + 1  3 (mod 10) Đặt 34n + 1 = 10.k + 3 với k N. 4n 1 Khi đó ta có: 23 3 210.k 1 3 Áp dụng định lý Euler ta có: (2; 11) = 1 Nên 2 (11)  1 (mod 11) 210  1 (mod 11) => 210.k +3  23 (mod 11) 34n 1 => 210.k +3 + 3  23 +3 (mod 11) 2 3  0 (mod 11) 4n 1 Vậy 23 311 Bài tập 4: Tìm 2 chữ số tận cùng của 20092010 Giải: Ta có: 20092010  92010 (mod 100) Áp dụng định lý Euler ta có: (9; 100) =1 (100) 1 1 Nên: 9  1 (mod 100). Mà (100) = 100.(1 )(1 ) 40 2 5 Hay: 940  1 (mod 100) => 92010  910 (mod 100) Mà 910 = 3486784401  1 (mod 100). Vậy 2 chữ số tận cùng của 20092010 là 01. 18
19. Phòng GD Diên khánh –Trần nhân Tông –Lê quang Thiên 9 Bài tập 5: Tìm 2 chữ số tận cùng của 99 Giải: Áp dụng định lý Euler ta có: (9; 100) = 1; (100) = 40; => 940  1 (mod 100). (*) Mặt khác ta có: 92  1 (mod 40) => 99  9 (mod 40). 9 ( ) Đặt 9 = 40.k + 9 với k N ** 9 Từ (*) và (**) suy ra: 99  99 (mod 100) Mà: 99 = 387420489  89 (mod 100) 9 Vậy 2 chữ số tận cùng của 99 là 89 Bài tập 6: Tìm 3 chữ số tận cùng của 21954 Giải: Ta thấy (2; 1000) = 2 nên chưa thể áp dụng trực tiếp định lý Euler được. Ta có: (21954; 1000) = 8. Ta xét 21951 chia cho 125 Áp dụng định lý Euler ta có: (2; 125) = 1 (125) 1 Nên: 2  1 (mod 125). Mà (125) = 125(1 ) 25 5 Hay: 225  1 (mod 125) => 21951  2 (mod 125) => 21951. 23  2.23 (mod 125.23) 21954  16 (mod 1000) Vậy 3 chữ số tận cùng của 21954 là 016 19