tai le

<span class='text_page_counter'>(1)</span>SỐ NGUYÊN - PHÉP CHIA HẾT. 1. Định nghĩa Tập các số nguyên bao gồm các số tự nhiên và các số đối của chúng và được ký hiệu là Z.. Z  0, 1, 2,.... Số nguyên lớn hơn 0 gọi số nguyên dương. Số nguyên nhỏ hơn 0 gọi là số nguyên âm. 2. Tính chất 2.1 Không có số nguyên lớn nhất và nhỏ nhất. Số nguyên dương nhỏ nhất là 1. 2.2 Một tập con hữu hạn bất kỳ của Z luôn có phần tử lớn nhất và phần tử nhỏ nhất. 2.3 Không có số nguyên nào nằm giữa hai số nguyên liên tiếp 2.4 Nguyên lý qui nạp: Cho A là tập hợp con của Z. Nếu k  A và n  A  n + 1  A , n ≥ k thì mọi số nguyên lớn hơn hay bằng k đều thuộc A. 2.5 Nếu a, b  Z , a < b thì a + 1  b 2.6. a  R, n  Z : n  a. 3. Phép chia hết 3.1. Định nghĩa Cho a, b là hai số nguyên bất kỳ, b khác 0. Nếu tồn tại số nguyên q sao cho a = bq thì ta nói a chia hết cho b hay a là bội của b (a  b) hay b là ước của a (b|a) 3.2. Định lý (thuật toán chia) Cho a, b là hai số nguyên bất kỳ, b khác 0. Khi đó, tồn tại duy nhất các số nguyên q, r sao cho a = bq + r với 0  r < |b|. 3.3. Các tính chất của phép chia hết 3.3.1. Nếu a  b thì am  b với mọi số nguyên m. 3.3.2. Nếu a  b và b  c thì a  c 3.3.3. Nếu a  c và b  c thì ax  by c x, y  Z ( ax + by gọi là tổ hợp tuyến tính của a, b) 3.3.4. Nếu a  b thì |a| ≥ |b| 3.3.5. Nếu a  b và b  a thì |a| = |b| 3.3.6. a  b  am  bm, m Z* BÀI TẬP Bài 1. Cho a, b, n là các số nguyên, n > 0, a  b. Chứng minh a/ an – bn  (a – b) b/ (an + bn)  (a + b) với n lẻ c/ (an – bn)  ( a + b) với n chẵn Bài 2. Chứng minh rằng với mọi số nguyên n a/ 33n + 3 – 26n – 27  169 b/ n2 – 3n + 5 không chia hết cho 121 Bài 3..

<span class='text_page_counter'>(2)</span> a/ Cho f(x) là một đa thức tùy ý với hệ số nguyên. Chứng minh rằng f(a) – f(b)  (a – b) với mọi số nguyên a, b. b/ Chứng minh không tồn tại đa thức p(x) với hệ số nguyên thỏa p(3) = 10, p(7) = 24 2k. k 1. Bài 4. Chứng minh rằng ( a  1)2 với k nguyên, a lẻ. Bài 5. Chứng minh rằng (n + 1)(n + 2) …(2n)  2n với mọi số nguyên dương n Bài 6. Chứng minh rằng tồn tại vô số nguyên dương n thỏa mãn 2n + 1  n. Bài 7. Giả sử x, y, z là những số tự nhiên thỏa x2 + y2 = z2. Chứng minh xyz  60 Bài 8. Cho x,y,z là các số nguyên thỏa (x – y)(y – z)(z – x) = x + y + z. Chứng minh x + y + z chia hết cho 27. Bài 9. Chứng minh rằng nếu a2 + b2 - ab  7 thì 8a3 – 6b3  7 Bài 10.Chứng minh rằng nếu 2 + a và 35 – b chia hết cho 11 thì a + b chia hết 11..

<span class='text_page_counter'>(3)</span> ƯỚC SỐ CHUNG LỚN NHẤT, BỘI SỐ CHUNG NHỎ NHẤT. 1. Ước chung lớn nhất 1.1. Định nghĩa Số nguyên dương d được gọi là ước chung lớn nhất của các số nguyên a 1, a2, …, an nếu d là ước chung của a1, a2, …, an và nếu e là một ước chung khác của chúng thì e là ước của d. Ký hiệu: d = UCLN(a1,a2,…,an) hay d = (a1,a2,…,an) Ví dụ: (-20, 30, 50) = 10; (15, 20, 18) = 1 Các số nguyên a1, a2, …, an gọi là nguyên tố cùng nhau nếu (a1, a2, …, an) = 1 Các số nguyên a1,a2,…,an gọi là nguyên tố sánh đôi nếu hai số bất kỳ trong chúng nguyên tố cùng nhau. Chú ý: Các số nguyên tố sánh đôi thì nguyên tố cùng nhau nhưng ngược lại không đúng. 1.2. Thuật toán Euclid 1.2.1. Bổ đề Nếu a = bq + r thì (a,b) = (b,r) Chứng minh: Ta có (a,b) |a và (a,b)| b  (a,b)| r  (a,b)|(b,r) (1) Mặt khác (b,r)|b và (b,r)|r  (b,r)|a  (b,r)|(a,b) (2) Từ (1) và (2)  (a,b) = (b,r) 1.2.2. Tìm ước chung lớn nhất của hai số nguyên a và b Đầu tiên ta chia a cho b được dư r 1 (0  r1 <|b|), chia b cho r1 được dư r2 (0  r2 <r1), cứ tiếp tục như thế ta được dãy |b|, r1, r2, … giảm dần về 0. Giả sử rn+1 = 0. Thuật toán sẽ kết thúc sau một số hữu hạn bước. a = bq + r1 (0  r 1 < |b|) b = r1q1 + r2 (0  r2 < r1) r1 = r2q2 + r3 (0  r3 < r2) …. rn-2 = rn-1qn-1 + rn (0  rn < rn-1) rn-1 = rnqn Theo định lý trên ta có (a,b) = (b,r1) = (r1,r2) =…=(rn-1,rn) = rn. Ví dụ: Tìm ước chung lớn nhất của hai số a = 555 và b = 407 555 = 407.1 + 148 407 = 148.2 + 111 148 = 111.1 + 37 111 = 37. 3 Vậy (555,407) = 37 1.3. Tính chất 1.3.1. (a,b) = (b,a). a b  ,  1 1.3.2. d = (a,b)   d d  1.3.3. k(a,b) = (ka,kb) 1.3.4. Nếu (a,b) = 1 và b|ac thì b|c 1.3.5. Nếu (a,b) = 1 và (a,c) = 1 thì (a,bc) = 1.

<span class='text_page_counter'>(4)</span> 1.3.6. (a,b,c) = ((a,b),c) = (a,(b,c)) 1.3.7. (a,b) = (a, b + ka), k 1.4. Định lý Cho a, b là các số nguyên và d là ước số chung lớn nhất của a và b. Khi đó tồn tại các số nguyên x’, y’ sao cho d = ax’ + by’ Chứng minh Đặt A = {ax + by /x,y Z} . Gọi l là số dương nhỏ nhất của A. Do l > 0 nên tồn tại q, r sao cho a = lq + r ( 0  r < l) Giả sử r > 0. Khi đó r = a – lq = a – (ax’ + by’)q = a(1 – x’q) + b( – y’q)  A mâu thuẩn với l là số dương nhỏ nhất trong A.  r = 0 hay a  l Tương tự ta cũng có b  l  d  l ( do d = (a,b)) Mặt khác l = ax’ + by’  l  d . Từ đây suy ra l = d. 1.5. Hệ quả 1.5.1. a, b là hai số nguyên tố cùng nhau khi và chỉ khi tồn tại hai số nguyên m, n sao cho am + bn = 1 1.5.2. d là ước chung lớn nhất của a và b khi và chỉ khi d là tổ hợp tuyến tính dương nhỏ nhất của a và b. 1.5.3. Nếu d = (a1,a2,…,an) thì tồn tại các số x1,x2,..,xn sao cho d = a1x1 + a2x2 + … + anxn 2. Bội chung nhỏ nhất 2.1. Định nghĩa Số nguyên dương b được gọi là bội chung nhỏ nhất của n số nguyên a 1,a2,…,an khác 0 nếu m là bội chung của a1,a2,…,an và nếu e là một bội chung khác của chúng thì e là bội của b. Ký hiệu b = [a1,a2,…,an] Ví dụ: [7, -14, 4] = 28 2.2.Tính chất 2.2.1. k[a,b] = [ka,kb] 2.2.2. [a,b,c] = [[a,b],c] 2.2.3 [a,b].(a,b) = ab Chứng minh tính chất 2.2.3. Đặt d = (a,b)  a = a1d, b = b1d với (a1,b1) = 1 Ta có [a1,b1]  a1  [a1,b1] = m.a1 b1|[a1,b1] = ma1  b1|m Do (a1,b1) = 1  [a1,b1]  a1b1 mà a1b1  [a1,b1] nên [a1,b1] = a1b1 [a,b].(a,b) = [a1d, b1d] d = [a1,b1]d2 = a1b1d2 = ab 2.2.4. Hệ quả a  b, a  c  a  [b,c] a  b, a  c, (b,c) = 1  a  bc BÀI TẬP 15n  1 Bài 1. Chứng minh phân số 33n  2 tối giản 21n 17 Bài 2. Chứng minh phân số 14 n  3 không là số nguyên.

<span class='text_page_counter'>(5)</span> Bài 3. Chứng minh rằng không tồn tại số tự nhiên n sao cho 2010n – 1 chia hết cho 1010n – 1 S  n  N / M 2 n  ( M  1) 2  Bài 4. Cho M là một số nguyên dương và tập hợp . Chứng minh rằng tất cả các tích có dạng ab với a, b  S đều phân biệt. Bài 5. Chứng minh rằng một số có số lẻ ước số khác nhau khi chỉ khi nó là bình phương đúng. Bài 6. Chứng minh rằng nếu (a,b) = 1 thì (a + b,a2 + b2) là 1 hoặc 2. Bài 7. Giả sử m, n là 2 số tự nhiên thỏa (m,n) + [m,n] = m + n. Chứng minh rằng (m,n) bằng m hoặc n. Bài 8. Tìm (2n + 1,9n + 4), (2n – 1 , 9n + 4), (36n + 3, 90n + 6) Bài 9. Tìm x, y nguyên dương thỏa x + y = 150, (x,y) = 30 Bài 10.Tìm x, y nguyên dương thỏa (x,y) = 5!, [x,y] = 50! và x  y..

<span class='text_page_counter'>(6)</span> SỐ NGUYÊN TỐ. 1. Định nghĩa Số nguyên p > 1 được gọi là số nguyên tố nếu p chỉ có hai ước dương là 1 và chính nó. Số nguyên lớn hơn 1 không phải là số nguyên tố được gọi là hợp số. Từ định nghĩa dễ thấy rằng nếu p là số nguyên tố và a là một số nguyên bất kỳ thì hoặc a p hoặc (a, p) = 1 2. Định lý Cho hai số nguyên a, b và số nguyên tố p. Khi đó nếu p|ab thì p|a hoặc p|b. Chứng minh Nếu. p |a. thì (a,p) = 1 suy ra p|b.. 3.Định lý Mọi hợp số phải có ước nguyên tố nhỏ hơn hay bằng căn bậc hai của nó. Chứng minh Giả sử n = a. b (1 < a, b < n ). n thì n = ab > n (vô lý) như vậy phải có một thừa số không vượt n hay có ước nguyên tố không vượt quá n .. Nếu cả a và b đều lớn hơn quá. 3.1.Hệ quả Nếu số nguyên n > 1 không có ước nguyên tố nào nhỏ hơn hay bằng n thì n là số nguyên tố. Ví dụ: 211 là số nguyên tố vì tất cả các số nguyên tố nhỏ hơn 211 là 2, 3, 5, 7, 11, 13 đều không là ước của 211. 4. Định lý cơ bản của số học Mọi số nguyên n > 1 đều biểu diễn được dưới dạng tích của các số nguyên tố. Phân tích này là duy nhất nếu không tính thứ tự của các thừa số. Chứng minh Ta chứng minh tồn tại biểu diễn bằng qui nạp. Với n = 2, n =3, n = 4 = 2.2, n = 5, n =6 = 2.3 đều biểu diễn dưới dạng tích các số nguyên tố. Giả sử khẳng định đúng đến n – 1, tức mọi số nguyên không vượt quá n – 1 đều biểu diễn được dưới dạng tích các số nguyên tố. Xét số nguyên n. Nếu n nguyên tố ta có ngay điều chứng minh. Nếu n là hợp số thì n = n 1.n2 (1 < n1, n2 < n), từ giả thiết qui nạp ta có n 1, n2 đều biểu diễn được dưới dạng tích các số nguyên tố, như vậy n cũng biểu diễn được dưới dạng tích các số nguyên tố. Ta chứng minh cách biểu diễn trên là duy nhất. Giả sử n có hai cách biểu diễn khác nhau n = p1p2…pr = q1q2…qs (các số nguyên tố pi khác các số nguyên tố qj ). Khi đó p1| q1q2…qs  p1| qj  p1 = qj (mâu thuẩn) k. p. i i.  p11 p22 ... pkk ,  i  0. Như vậy mọi số nguyên n > 1 đều có biểu diễn n = i 1 trong đó pi (i =1,2,…k) là những số nguyên tố đôi một khác nhau. Ta nói n có dạng phân tích chính tắc. 4.1. Hệ quả.

<span class='text_page_counter'>(7)</span> 4.1.1. Nếu n có dạng phân tích chính tắc. n  p11 p22 ... pkk thì số tất cả các ước số dương của n là. (1  1)( 2  1)...( k  1) k. k. n  pii m  pii i 1 i 1 4.1.2. Nếu , , i , i 0 thì m  n  i i (i 1, 2,..., k ) k. (m,n) =. i 1. k. [m,n] =. min( i ,i ) i. p. max( i ,i ) i. p i 1. 5. Định lý: Tập hợp các số nguyên tố là vô hạn Chứng minh Giả sử chỉ có n số nguyên tố p1, p2, …, pn. Xét số N = 1 + p1p2…pn. N > 1 nên tồn tại một số nguyên tố p là ước của N. Rõ ràng p khác với p1, p2,.., pn (vô lý). Vậy có vô hạn số nguyên tố. 6. Hệ thống ghi số 6.1. Định lý Cho số nguyên dương d > 1. Khi đó mọi số tự nhiên N đều có thể biểu diễn được một cách duy nhất dưới dạng N = d 0 + d1b + d2b2 + …. + dnbn (1), trong đó các số nguyên dương d i thỏa mãn 0  di  b – 1. Chứng minh Ta chứng minh bằng qui nạp theo N. Với N = 1, ta có biểu diễn duy nhất 1 = 1 Giả sử biểu diễn nói trên có được và duy nhất cho mọi số 1, 2, …, N – 1 Xét số N. Gọi d0 là số sao cho N – d0  b. Đặt N1 = (N – d0)/b. Vì N1 < N, theo gt qui nạp N1 được biểu diễn duy nhất dưới dạng N  d0 d1  d 2b  d3b 2  ...  d nb n  1 b N1 = Như vậy N = d0 + d1b + d2b2 + … + dnbn Nếu có một cách biểu diễn khác như thế cho N tức là: N = d0 + d1b + d2b2 + … + dnbn = a0 + a1b + a2b2 + … + anbn. Khi đó d0 = a0 = r ( là số dư khi chia N cho b). N  d0 d1  d 2b  d3b 2  ...  d nb n  1 a1  a2b  a3b 2  ...  anb n 1 b  N1 = và theo tính chất duy nhất trong giả thiết qui nạp, ta có điều phải chứng minh. 6.2. Định nghĩa Giả sử g là số tự nhiên lớn hớn 1 và M = {0,1,2,…, g – 1} là tập hợp gồn g ký hiệu các số tự nhiên đầu tiên. Ta nói số tự nhiên s được viết trong hệ g- phân ( hoặc hệ thống ghi cơ số g) nếu trong s = angn + an-1gn-1 + …. + a1g + a0 trong đó n là một số nguyên dương và a i  M, an  0. Ký hiệu: s = an an 1....a1a0 (g) có thể bỏ (g) nếu không nhầm lẫn. 6.3. Hệ nhị phân Hệ thống ghi số này sử dụng hai chữ số 0, 1..

<span class='text_page_counter'>(8)</span> Một số tự nhiên k trong hệ nhị phân được viết k = an an 1....a1a0 với ai , i = 0,1,2,..,n là một trong các chữ số 0,1 và an  0 có nghĩa là k = an2n + an-12n-1 + …+ a1.2 + a0 6.3.1. Định lý Cho số tự nhiên N. Gọi n là số các chữ số (0,1) của N khi viết trong hệ nhị phân, ta có n = [log2N] + 1 Chứng minh Ta có N = 2n – 1 + an-22n -2 + … + a12 + a0 , ai {0,1}  2n > N ≥ 2 n -1  n > log2N ≥ n – 1 hay [log2N] = n – 1 suy ra đpcm. 7. Phần nguyên 7.1. Định nghĩa Phần nguyên, ký hiệu [x], của số thực x là số nguyên lớn nhất không vượt quá x. Phần phân của x , ký hiệu {x}, là x – [x]. 7.2. Tính chất 7.2.1. x = [x] + {x} 7.2.2. x = [x]  x  Z 7.2.3. x = {x}  0  x < 1 7.2.4. x – 1 < [x]  x 7.2.5. Nếu k  Z thì [x + k] = [x] + k, {x + k} = {x} + k 7.2.6. [x + y] – [x] – [y] bằng 0 hoặc 1 7.2.7. [x + y] ≥ [x] + [y] , {x + y}  {x} + {y} 7.3. Định lý.     * Nếu  là số thực dương và n  N thì  n  là số tất cả các số nguyên dương là bội của n nhưng không vượt qua . * Nếu a, b là hai số không âm thì [2a] + [2b] ≥ [a] + [b] + [a + b] 8. Định lý Trong sự phân tích số n! ra thừa số nguyên tố n! =. p11 p22 ... pkk , i  0.  n  n   n   i     2   ...   k   ....  pi   p i   pi  thì số mũ i của pi nào đó sẽ là Chứng minh.  n   n   k    k 1   .... 0 p p k Tổng trên là hữu hạn vì khi k đủ lớn thì n < pi khi đó  i   i  Giả sử p là một ước của n!.  n.    n p p  p p Ta có n! = 1.2…p.(p+1)…2p…3p….   …n =  n   với m =  p  và (p,q) =1.  n m  p  !q  p .m!q  .

<span class='text_page_counter'>(9)</span> m!  p.  m  p  . Tương tự  n  p  .  m  p  !q '   với (p,q’) = 1.  m  p  .  n  n .  n   p 2  !qq '   Suy ra với (p,qq’) = 1  n  n   n       2   ...   k   ...  p  p  p  Cứ tiếp tục như thế ta thu được số mũ của p : n!  p. p.  p    p2   m     ! qq '  p  p  . Ví dụ: Số mũ của 5 trong phân tích 100! ra thừa số nguyên tố là.  100   100   100   5   2  3  ... 20  4  0 24  5   5   5  Từ đó 100! Có tận cùng 24 chữ số 0. BÀI TẬP Bài 1. Tìm tất cả số nguyên tố vừa là tổng của 2 số nguyên tố, vừa là hiệu của 2 số nguyên tố. Bài 2. Chứng minh rằng mọi số tự nhiên n luôn tồn tại n số tự nhiên liên tiếp không là số nguyên tố. Bài 3. Chứng minh rằng không tồn tại n để 6n + 5 biểu diễn dưới dạng tổng của 2 số nguyên tố Bài 4. Tìm tất cả các số tự nhiên n lẻ để n, n + 10, n + 14 là số nguyên tố. Bài 5. Tìm tất cả các số nguyên tố p sao cho 2p2 + 1 là số nguyên tố. a a2  b2  2 2 Bài 6. Cho a, b, c là các số nguyên khác 0, a  c thỏa mãn c c  b Chứng minh rằng a2 + b2 + c2 không thể là số nguyên tố. Bài 7. Tìm tất cả các số nguyên tố p sao cho p2 + 11 có đúng 6 ước số nguyên dương. Bài 8. Tìm tất cả các số nguyên tố p sao cho hệ phương trình p + 1 = 2x 2, p2 + 1 = 2y2 có nghiệm nguyên. Bài 9. Chứng minh rằng nếu p và 8p2 + 1 lẻ là số nguyên tố thì 8p2 + 2p + 1 là số nguyên tố. Bài 10.Tìm tất cả các số tự nhiên n sao cho n + 1, n + 3, n + 7, n + 9, n + 13 và n + 15 đều là số nguyên tố Bài 11.Cho 4 số tự nhiên thỏa tính chất: Bình phương của tổng hai số bất kỳ chia hết cho tích hai số còn lại. Chứng minh rằng có ít nhất ba trong bốn số đó phải bằng nhau..

<span class='text_page_counter'>(10)</span> ĐỒNG DƯ 1. Định nghĩa Cho a, b, m là các số nguyên, m  0. Nếu a – b chia hết cho m thì a được gọi là đồng dư với b modulo m, ký hiệu a  b mod m. 2. Tính chất Cho a, b, c, d là các số nguyên Nếu a  b mod m thì b  a mod m Nếu a  b mod m và b  c mod m thì a  c mod m Nếu a  b mod m và c  d mod m thì a + c  b + d mod m Nếu a  b mod m và c  d mod m thì ac  bd mod m Nếu a  b mod m, k nguyên dương thì ak  bk mod m Nếu a  b mod m và d| m thì a  b mod d Nếu a  b mod m thì ac  bc mod cm với mọi c khác 0. Nếu ab  ac mod m và (a,m) = 1 thì b  c mod m a  b mod mi ( i =1,2,…,n)  a  b mod [m1,m2,…,mn] 3. Định lý Fermat nhỏ Giả sử p nguyên tố, (a, p) = 1. Khi đó ap–1  1 mod p Chứng minh Xét p – 1 số a, 2a, 3a, …, (p – 1)a. Ta chứng minh rằng không tồn tại 2 số đồng dư trong phép chi a cho p. Giả sử ka  la mod p với k, l {1,2,…,p – 1} và k  l  a(k – l)  p  k – l  p  k = l (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 từ 1, 2,…, p – 1. Suy ra a. 2a. …(p – 1)a  1.2….(p – 1) mod p  (p – 1)!. ap–1  (p – 1)! mod p Vì ((p – 1)!,p) = 1 nên ap–1  1 mod p. Từ định lý ta có ap  a mod p (với p nguyên tố, (a,p) =1) 4. Hệ thặng dư đầy đủ * Tập hợp x1, x2, …, xn gọi là một hệ thặng dư đầy đủ modulo m nếu với mỗi số nguyên y tồn tại duy nhất một xi sao cho y  xi mod m. Tập {1,2,…, m – 1, m} là một hệ thặng dư đầy đủ modulo m * Mọi hệ thặng dư đầy đủ modulo m đều có đúng m phần tử * Một tập gồm m phần tử là một hệ thặng dư đầy đủ modulo m nếu và chỉ nếu hai phần tử khác nhau bất kỳ của nó không đồng dư với nhau modulo m. * Cho số nguyên a và m > 0. Tập hợp tất cả các số nguyên x thỏa mãn x  a mod m được. a  a  mt / t  Z. gọi là một lớp đồng dư modulo m, ký hiệu . Có m lớp đồng dư phân biệt modulo m, thu được bằng cách lấy lần lượt a = 1,2,…,m. * Một tập hợp {r1,r2,…,rn} được gọi là một hệ thặng dư thu gọn modulo m nếu (r i,m) = 1, ri  rj i  j, 1  i, j  n và với mọi số nguyên x nguyên tố cùng nhau với m thì tồn tại r i sao cho ri  x mod m. Số các phần tử của hệ thặng dư thu gọn modulo m được xác định bởi hàm Euler (m) là số các số nguyên dương không vượt quá m và nguyên tố cùng nhau với m. 5. Hàm phi - Euler 5.1. Định nghĩa.

<span class='text_page_counter'>(11)</span> Hàm  có các tính chất sau: 5.1.1. (mn) (m)(n) với (m,n) = 1 n n n 1 5.1.2. Nếu p nguyên tố, (p) p  1, (p ) p  p (n  1) , 1 2 k 5.1.3. Nếu m p1 p 2 ...p k , p là các số nguyên tố thì i.  1  1   1  (m) m  1    1   ...  1    p1   p2   p k  2. Ví dụ: (2) 1 , (3) 2 , (4) 2  2 2 ,. (20) 20(1 . 1 1 )(1  ) 8 2 5. 5.2. Định lý Cho (a,m) = 1 và r1, r2,…., rn là một hệ thặng dư thu gọn (đầy đủ) modulo m. Khi đó ar 1, ar2, …, arn cũng là một hệ thặng dư thu gọn (đầy đủ) modulo m. Chứng minh Vì (a,m) = 1 nên nếu (r i,m) = 1 thì (ari, m) = 1. Ta chứng minh các phần tử của tập {ar 1,ar2, …,arn} đôi một phân biệt modulo m. Thật vậy, nếu ar i = arj mod m thì do (a,m) = 1 nên r i  rj mod m (vô lý). Theo 4.4 ta có đpcm. 5.3. Định lý Euler  (m) 1 mod m. Giả sử m là số nguyên dương và (a,m) = 1. Khi đó a Chứng minh. Giả sử r1, r2, …,. r(m). là hệ thặng dư thu gọn gồm các số nguyên dương không vượt quá m và. nguyên tố cùng nhau với m. Theo định lý trên ta suy ra ar 1, ar2, …,. ar(m). gọn modulo m. Như vậy các đồng dư dương bé nhất của ar 1, ar2,..,. ar(m). r(m) a. xếp theo một thứ tự nào đó. Vì thế ta có. là một hệ thặng dư thu. phải là các số r1, r2, …,. ar1.ar2 ....ar(m) r1r2 ...r (m) mod m. hay.  (m). r1r2 ...r(m) r1r2 ...r(m) mod m (r1r2 ...r(m) , m) 1 a (m) 1mod m. Vì nên Ví dụ. Tìm dư khi chia số 112010 cho số 24.. Giải  (24). Ta có (11,24) = 1  11. 8. 1mod 24  11 1mod 24. 112010 118.2512 112 1 mod 24. 6. Phương trình đồng dư tuyến tính 6.1. Định nghĩa Phương trình dạng ax  b mod m được gọi là phương trình đồng dư tuyến tính với a, b, m là các số đã biết. x0 là một nghiệm của phương trình khi và chỉ khi ax0  b mod m. Nếu x0 là nghiệm thì các phần tử thuộc lớp x 0 cũng là nghiệm. 6.2. Định nghĩa Giả sử a, m là các số nguyên, m > 1. Nghiệm của phương trình ax  1 mod m được gọi là nghịch đảo của a modulo m. 6.3. Định lý Nghịch đảo của a modulo m là duy nhất  (a,m) = 1..

<span class='text_page_counter'>(12)</span> Chứng minh Gọi a’ là nghịch đảo của a modulo m  aa’  1 mod m  aa’ + mb = 1  (a,m) = 1 Đảo lại nếu (a,m) = 1  tồn tại a’, m’ sao cho aa’ + mm’ = 1  aa’  1 mod m  a’ là nghịch đảo của a modulo m. a’ là duy nhất bởi vì nếu có a’’ sao cho aa’’  1 mod m thì aa’  aa’’ mod m , mà (a,m) = 1  a’  a’’ mod m. 6.4. Hệ quả Nếu p nguyên tố thì mỗi phần tử của tập hợp {1,2,..., p – 1} đều có nghịch đảo duy nhất modul p. 6.5. Định lý Nếu (a,m) = 1 thì phương trình ax  b mod m có nghiệm duy nhất theo modulo m. Chứng minh Ta có {1,2,…,m} là một hệ thặng dư đầy đủ modulo m và (a,m) =1 nên {a,2a, …,ma} cũng là một hệ thặng dư đầy đủ modulo m  có đúng một phần tử của hệ này đồng dư với b mod m . Suy ra đpcm. 6.6. Định lý tồn tại nghiệm phương trình đồng dư tuyến tính Giả sử (a,m) = d. Khi đó phương trình ax  b mod m (1) có nghiệm khi và chỉ khi d| b Hơn nữa, khi d | b thì (1) có d nghiệm phân biệt modulo m, đó là m m m t, t  , t  2 ,..., t  (d  1) d d d (2) a b m x  mod d d trong đó t là nghiệm duy nhất của phương trình d (3) Chứng minh Nếu phương trình có nghiệm là x0  ax0 = b + mt  d| b a b m a m x  mod do ( , ) 1 d d d d Đảo lại, nếu d | b thì phương trình d có nghiệm t duy nhất  phương trình ax  b mod m cũng có nghiệm t. Mỗi nghiệm của (3) là nghiệm của (1) và ngược lại. Dễ thấy rằng (2) là d nghiệm của (3) nên (2) cũng là d nghiệm của (1). Ngoài ra hai nghiệm của m m t  r t  s mod m (1 r,s d  1) d d (2) là phân biệt theo modulo m. Thật vậy nếu . m m r s mod m  r s mod d d  d  r – s  d  r = s. Tiếp tục, ta chứng minh (1) không còn nghiệm nào khác ngoài (2). Giả sử y là nghiệm của (1)  ay  b mod m  ay  at mod m  y  t mod m  y  t mod m/d m m k. r. mod m d d  y = t + km/d . Ta có k  r mod d với 0  r < d. Do đó  y  t + rm/d mod m  y thuộc (2). Ví dụ. Giải phương trình 12x  7 mod 23 Giải Do (12,23) = 1 nên phương trình luôn có nghiệm duy nhất. Ta tìm một số nguyên k sao cho 7 + 23k chia hết cho 12. Chọn k = 7  12x  7.24 mod 23  x  14 mod 23 7. Mệnh đề Giả sử p là số nguyên tố. Số nguyên a là nghịch đảo modulo p của chính nó khi và chỉ khi a  1 mod p hoặc a  – 1 mod p Chứng minh.

<span class='text_page_counter'>(13)</span> Nếu a  1 mod p hoặc a  – 1 mod p thì a2  1 mod p nên a là nghịch đảo modulo p của chính nó. Ngược lại, giả sử a là nghịch đảo modulo của chính nó, tức là a2  1 mod p  a2 – 1  p  a + 1  p hoặc a – 1  p hay a  – 1 mod p hoặc a  1 mod p. 8. Định lý Wilson 8.1. Định lí 1 Với số nguyên tố p, ta có (p – 1)!  – 1 mod p. Chứng minh Khi p = 2, ta có (p – 1)! = 1  –1 mod 2 Giả sử p là số nguyên tố lớn hơn 2, khi đó mỗi số nguyên a với 1  a  p – 1 tồn tại nghịch đảo a’ với 1  a’  p – 1 sao cho aa’  1 mod p. Theo mệnh đề trên chỉ có 2 số 1 và p – 1 là nghịch đảo modulo p của chính nó. Như vậy, ta có thể nhóm các số 2, 3,…, p – 2 thành (p – 3)/2 cặp mà tích của chúng đồng dư 1 modulo p. 2.3. …(p – 3)(p – 2)  1 mod p  (p – 1)!  1(p – 1)  –1 mod p. Mệnh đề đảo của định lý Wilson cũng đúng. 8.2. Định lý 2 Giả sử p là số nguyên dương sao cho ( p – 1)!  – 1 mod p thì p là số nguyên tố. 9. Định lý đồng dư Trung Hoa Giả sử m1, m2, …, mr là các số nguyên tố cùng nhau đôi một. Khi đó hệ phương trình đồng dư tuyến tính x  a1 mod m1 x  a2 mod m2 …. x  ar mod mr có nghiệm duy nhất modulo m = m1m2…mr. Ví dụ. Giải hệ phương trình x  2 mod 5, x  3 mod 7, x  5 mod 3 Giải x  2 mod 5  x  17 mod 5 x  3 mod 7  x  17 mod 7  x  17 mod 35 x  5 mod 3  x  5 + 3.4 mod 3  x  17 mod 3  x  17 mod 105 BÀI TẬP Bài 1. Chứng minh nếu a là số nguyên chẵn thì a2  0 mod 4, nếu a là số nguyên lẻ thì a2  1 mod 4. Bài 2. Chứng minh rằng nếu a lẻ thì a2  1 mod 8. Bài 3. Chứng minh rằng n7 – n  42 với n nguyên dương. Bài 4. Chứng minh rằng nếu a + b + c  30 thì a5 + b5 + c5  30 (a,b,c  Z) 3n Bài 5. Chứng minh rằng 5  7 12 với n nguyên dương Bài 6. Giả sử n là số tự nhiên không chia hết cho 17. Chứng minh rằng hoặc n8 – 1  17 hoặc n8 + 1 chia hết 17 Bài 7. Tìm tất cả các số nguyên n sao cho n.2n + 1 chia hết cho 3. Bài 8. Với số nguyên n nào ta có 12 + 22 + …+ (n – 1)2  0 mod n. Bài 9. Tìm dư trong phép chia.

<span class='text_page_counter'>(14)</span> 19. 54. 2345 1000000 34 237 : 37 : 310 :135 a. 23 :17 b. 46 c. 239 d. 2 Bài 10.Giải hệ a) x  1 mod 2, x  2 mod 3, x  3 mod 5. b) x  2 mod 11, x  3 mod 12, x  4 mod 13, x  5 mod 17, x  6 mod 19. c) x  5 mod 6, x  3 mod 10, x  8 mod 15. Bài 11.Chứng minh định lý đảo của định lý Wilson. q 1. p 1. Bài 12.Chứng minh rằng nếu p, q là các số nguyên tố khác nhau thì p  q  1 mod pq. Bài 13.Chứng minh nếu p nguyên tố và ap  bp mod p thì ap  bp mod p2 Bài 14.Chứng minh rằng nếu p là số nguyên tố lẻ thì 12.32…(p– 4)2(p –2)2  (–1)(p+1)/2 mod p Bài 15.Chứng minh rằng nếu p nguyên tố thì (p – 2)! – 1  p nhưng nếu p > 5 thì (p –2)! – 1 không phải là một lũy thừa của p. Bài 16.Giả sử hàm số f: N* N* thỏa mãn điều kiện f(mf(n)) = n2f(m) m,n N* a) Chứng minh rằng f(2009) hoặc là số nguyên tố hoặc là bình phương của một số nguyên tố. b) Hãy xây dựng một hàm f thỏa mãn điều kiện trên..

<span class='text_page_counter'>(15)</span> BÀI TOÁN CHIA HẾT TRÊN TẬP SỐ NGUYÊN. Chứng minh bài toán chia hết trên tập số nguyên Z là một bài toán cơ bản trong chương trình số học. Song các bài toán chứng minh chia hết rất phong phú đa dạng. Đê thấy được cách giải quyết các bài toán đó cần phải được trang bị các phương pháp chứng minh cơ bản. Để thực hiện được điều đó, tôi xin đề xuất một phương pháp chứng minh chia hết trên tập số nguyên Z. 1. Phương pháp quy nạp toán học Bài toán 1.1. Chứng tỏ rằng trong hai số tự nhiên liên tiếp có một số chia hết cho 2. Chứng minh: Giả sử hai số tự nhiên liên tiếp là n và n+1.  n   , ta cần chứng minh một trong hai số n hoặc. n +1 chia hết cho 2. Xét tích n.(n+1) khi đó cần chứng minh tương đương n.(n+1) ⋮ 2. (1). + Với n = 1 khi đó n.(n + 1) = 1.2 =2 ⋮ 2 suy ra (1) luôn đúng. + Giả sử (1) đúng với n = k, k  1  hay k.(k + 1) ⋮ 2. Ta cần chứng minh (1) đúng với n = k + 1 tức là chứng minh: (k+1).(k+2) ⋮ 2 Thật vậy ta có: (k + 1).(k + 2) = k(k + 1) + 2.(k + 1). Theo giả thiết quy nạp ta có k(k + 1) ⋮ 2 mà 2.(k + 1) ⋮ 2 Suy ra (k +1). ( k + 2). ∀ k∈N .. ⋮ 2 hay (1) được chứng minh.. Nhận xét: i. Ở bài toán này khi ta sử dung phương pháp quy nạp, ta dễ dàng đưa ra điều cần chứng minh bằng cách phân tích biểu thức cần chứng minh qua giả thiết đã có. ii. Bài toán có cách giải khác được giới thiệu ở phần sau từ bài toán trên ta có bài toán tổng quát sau:.

<span class='text_page_counter'>(16)</span> Bài toán 1.2. Trong n số tự nhiên liên tiếp có một số chia hết cho n Chứng minh: Giả sử có n số tự nhiên liên tiếp n là (p + 1); (p + 2); ...; (p +n). Ta cần chứng minh trong n số tự nhiên trên có một số chia hết cho n Xét tích: (p + 1).(p + 2)....(p + n) Điều cần chứng minh tương đương là (p + 1) ; (p + 2) ; ... ; (p +n) ⋮ n (**) + Với p = 1 ta có (1 + 1).(1 + 2)...( 1 + n) ⋮ n luôn đúng. + Giả sử (**) đúng với p = k ; k >1. N ta có. (k + 1).(k + 2) ... ( k + k) ⋮ k. (2). Ta cần chứng minh (**) đúng với p = k +1 Tức là chứng minh (k + 1 + 1).( k +2) ... ( k +1 + k +1) ⋮ (k+1) Thật vậy ta có: (k + 1 + 1).( k +2)...( k +1 + k +1) = (k + 2).(k + 3)...( 2k +2) = 2(k +1).(k + 2)...(2k + 1). ⋮. k+1 Vậy (** ) được chứng minh. Bài toán 1.3. Chứng minh rằng tổng lập phương của ba số nguyên dương liên tiếp chia hết cho 9. Chứng minh: +¿ Giả sử ba số nguyên dương liên tiếp đó là: n, n + 1, n + 2; n Z ¿ Ta phải chứng minh: n3 + (n + 1)3 + (n + 2)3. ⋮ 9. + Với n = 1 ta có 13 + (1 + 1)3 + (1 + 2)3= 13 +23 + 33 = 36 Giả sử (3) đúng với n = -k , k >1 k3 + (k + 1)3 + (k + 2)3 Thật vậy. ⋮ 9 nên (3) đúng. +¿¿ Z khi đó ta có ⋮ 9. (3).

<span class='text_page_counter'>(17)</span> (k + 1)3 + (k + 2)3+ (k + 3)3 = (k +1)3+ ( k + 2)3 + k3 + 9K2 + 27K + 27 = K3 + (K + 1)3+ (K +2)3 + 9K2 +27K + 27 = K3 + (K + 1)3+ (K +2)3 + 9(K2 +3K + 3) Mà theo giả thiết quy nạp ta có:  K3+ (K+1)3 + (K+2)3 ⋮ 9 K  . Mặt khác 9(K2 + 3K + 3) ⋮ 9 Vậy (K + 1)3 + (K + 2)3 + (K + 3)3 ⋮ 9 hay (3) được chứng minh. Nhận xét: Từ hai bài toán trên ta thấy phương pháp chứng minh quy nạp được sử dụng thuận lợi và hiệu quả. Để thấy rõ hơn tính ưu việt của phương pháp quy nạp ta xem xét bài toán sau..

<span class='text_page_counter'>(18)</span>