SỐ NGUYÊN PHÉP CHIA HẾT1. Định nghĩaTậ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.{}0, 1, 2,....= ±ZSố nguyên lớn hơn gọi số nguyên dương. Số nguyên nhỏ hơn gọi là số nguyên âm.2. Tính chất2.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 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ếp2.4 Nguyên lý qui nạp: Cho là tập hợp con của Z. Nếu và thì mọi số nguyên lớnhơn hay bằng đều thuộc A.2.5 Nếu a, thì b2.6 : >a a3. Phép chia hết3.1. Định nghĩaCho a, là hai số nguyên bất kỳ, khác 0. Nếu tồn tại số nguyên sao cho bq thì tanói chia hết cho hay là bội của (a b) hay là ước của (b|a)3.2. Định lý (thuật toán chia) Cho a, là hai số nguyên bất kỳ, khác 0. Khi đó, tồn tại duy nhất các số nguyên q, saocho bq với |b|.3.3. Các tính chất của phép chia hết3.3.1. Nếu thì am với mọi số nguyên m.3.3.2. Nếu và thì c3.3.3. Nếu và thì ax by c+M x, ax by gọi là tổ hợp tuyến tính của a, b)3.3.4. Nếu thì |a| |b|3.3.5. Nếu và thì |a| |b|3.3.6. am bm, *BÀI TẬPBài 1. Cho a, b, là các số nguyên, 0, b. Chứng minh a/ (a b) b/ (a n) (a b) với lẻc/ (a n) b) với chẵnBài 2. Chứng minh rằng với mọi số nguyên na/ 3n 26n 27 169b/ 3n không chia hết cho 121Bài 3.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ọisố 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) 241Bài 4. Chứng minh rằng 1( 1) 2kka+-M với nguyên, lẻ.Bài 5. Chứng minh rằng (n 1)(n 2) …(2n) với mọi số nguyên dương nBài 6. Chứng minh rằng tồn tại vô số nguyên dương thỏa mãn n.Bài 7. Giả sử x, y, là những số tự nhiên thỏa 2. Chứng minh xyz 60Bài 8. Cho x,y,z là các số nguyên thỏa (x y)(y z)(z x) z. Chứng minh zchia hết cho 27.Bài 9. Chứng minh rằng nếu ab thì 8a 6b 7Bài 10. Chứng minh rằng nếu và 35 chia hết cho 11 thì chia hết 11.2ƯỚC SỐ CHUNG LỚN NHẤT, BỘI SỐ CHUNG NHỎ NHẤT1. Ước chung lớn nhất1.1. Định nghĩaSố nguyên dương được gọi là ước chung lớn nhất của các số nguyên a1 a2 …, an nếu dlà ước chung của a1 a2 …, an và nếu là một ước chung khác của chúng thì là ước của d.Ký hiệu: UCLN(a1 ,a2 ,…,an hay (a1 ,a2 ,…,an )Ví dụ: (-20, 30, 50) 10; (15, 20, 18) 1Các số nguyên a1 a2, …, an gọi là nguyên tố cùng nhau nếu (a1 a2 …, an 1Cá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ùngnhau.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 Euclid1.2.1. Bổ đề Nếu bq thì (a,b) (b,r)Chứng minh:Ta có (a,b) |a và (a,b)| (a,b)| (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 và bĐầu tiên ta chia cho được dư r1 (0 r1 <|b|), chia cho r1 được dư r2 (0 r2 Õikki iip trong đó pi (i=1,2,…k) là những số nguyên tố đôi một khác nhau. Ta nói có dạng phân tích chính tắc.4.1. Hệ quả64.1.1. Nếu có dạng phân tích chính tắc 21 2...a aa=kkn thì số tất cả các ước số dương của là1 2( 1)( 1)...( 1) +k4.1.2. Nếu 1ikiin pa==Õ ,1ikiim pb==Õ ,, 0i ia thì 1, 2, ..., )i ii kb = (m,n) =min( )1i ikiipa b=Õ [m,n] =max( )1a b=Õi ikiip5. Định lý: Tập hợp các số nguyên tố là vô hạnChứng minhGiả sử chỉ có số nguyên tố p1 p2 …, pn Xét số p1 p2 …pn .N nên tồn tại một số nguyên tố là ước của N. Rõ ràng 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 1. Khi đó mọi số tự nhiên đều có thể biểu diễn được mộtcách duy nhất dưới dạng d0 d1 d2 …. dn (1), trong đó các số nguyên dương dithỏa mãn di 1.Chứng minhTa chứng minh bằng qui nạp theo N.Với 1, ta có biểu diễn duy nhất 1Giả sử biểu diễn nói trên có được và duy nhất cho mọi số 1, 2, …, Xét số N. Gọi d0 là số sao cho 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 N1 101 3...nnN dd bb--= +Như vậy d0 d1 d2 dn nNếu có một cách biểu diễn khác như thế cho tức là:N d0 d1 d2 dn a0 a1 a2 an n.Khi đó d0 a0 là số dư khi chia cho b) N1 101 3... ...n nn nN dd bb- --= 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ĩaGiả sử là số tự nhiên lớn hớn và {0,1,2,…, 1} là tập hợp gồn ký hiệu các sốtự nhiên đầu tiên. Ta nói số tự nhiên được viết trong hệ g- phân hoặc hệ thống ghi cơ số g)nếu trong an an-1 n-1 …. a1 a0 trong đó là một số nguyên dương và ai M, an 0.Ký hiệu: 0....n na a- (g) có thể bỏ (g) nếu không nhầm lẫn.6.3. Hệ nhị phânHệ thống ghi số này sử dụng hai chữ số 0, 1.Một số tự nhiên trong hệ nhị phân được viết 0....n na a- với ai 0,1,2,..,n là một trongcác chữ số 0,1 và an có nghĩa là an an-1 n-1 …+ a1 .2 a076.3.1. Định lýCho số tự nhiên N. Gọi là số các chữ số (0,1) của khi viết trong hệ nhị phân, ta có =[log2 N] 1Chứng minhTa có an-2 -2 a1 a0 ai {0,1} -1 log2 hay [log2 N] suy ra đpcm. 7. Phần nguyên7.1. Định nghĩaPhần nguyên, ký hiệu [x], của số thực là số nguyên lớn nhất không vượt quá x.Phần phân của ký hiệu {x}, là [x].7.2. Tính chất7.2.1. [x] {x}7.2.2. [x] Z7.2.3. {x} 17.2.4. [x] x7.2.5. Nếu thì [x k] [x] k, {x k} {x} k7.2.6. [x y] [x] [y] bằng hoặc 17.2.7. [x y] [x] [y] {x y} {x} {y}7.3. Định lý* Nếu là số thực dương và thì naé ùê úë là số tất cả các số nguyên dương là bội của nnhưng không vượt qua .* Nếu a, 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! 21 2... 0a aaa >kk ip pthì số mũ ai của pi nào đó sẽ là 2... ....é ùé ùa +ê úê úê úë ûë ûiiki in np pChứng minhTổng trên là hữu hạn vì khi đủ lớn thì pi khi đó 1.... 0+é ù+ =ê úë ûk ki in np pGiả sử là một ước của n!.Ta có n! 1.2…p.(p+1)…2p…3p….é ùê úë ûnpp …n !é ùê úë ûé ù=ê úë ûnpmnp qp với ùê úë np và (p,q) =1Tương tự 'é ùê úë ûé ù=ê úë ûmpmm qp với (p,q’) 18Suy ra 22! ' 'é ùé ù+ê úê úë ûé ù= =ê úë ûnn np pm nn qq qqp với (p,qq’) 1Cứ tiếp tục như thế ta thu được số mũ của 2... ...é ùa +ê úë ûkn np pVí dụ: Số mũ của trong phân tích 100! ra thừa số nguyên tố là52 3100 100 100... 20 245 5é ùa =ê úë Từ đó 100! Có tận cùng 24 chữ số0.BÀI TẬPBài 1. Tìm tất cả số nguyên tố vừa là tổng của số nguyên tố, vừa là hiệu của số nguyên tố.Bài 2. Chứng minh rằng mọi số tự nhiên luôn tồn tại 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 để 6n biểu diễn dưới dạng tổng của số nguyên tốBài 4. Tìm tất cả các số tự nhiên lẻ để n, 10, 14 là số nguyên tố.Bài 5. Tìm tất cả các số nguyên tố sao cho 2p là số nguyên tố.Bài 6. Cho a, b, là các số nguyên khác 0, thỏa mãn 22 2a bc b+=+Chứng minh rằng không thể là số nguyên tố.Bài 7. Tìm tất cả các số nguyên tố sao cho 11 có đúng ước số nguyên dương.Bài 8. Tìm tất cả các số nguyên tố sao cho hệ phương trình 2x 2, 2y cónghiệm nguyên.Bài 9. Chứng minh rằng nếu và 8p lẻ là số nguyên tố thì 8p 2p là số nguyên tố.Bài 10. Tìm tất cả các số tự nhiên sao cho 1, 3, 7, 9, 13 và 15 đều là sốnguyên tốBài 11. Cho 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íchhai số còn lại. Chứng minh rằng có ít nhất ba trong bốn số đó phải bằng nhau.9ĐỒNG DƯ1. Định nghĩaCho a, b, là các số nguyên, 0. Nếu chia hết cho thì được gọi là đồng dư với modulo m, ký hiệu mod m.2. Tính chấtCho a, b, c, là các số nguyênNếu mod thì mod Nếu mod và mod thì mod mNếu mod và mod thì mod mNếu mod và mod thì ac bd mod Nếu mod m, nguyên dương thì mod mNếu mod và d| thì mod dNếu mod thì ac bc mod cm với mọi khác 0.Nếu ab ac mod và (a,m) thì mod mod mi =1,2,…,n) mod [m1 ,m2 ,…,mn ]3. Định lý Fermat nhỏGiả sử nguyên tố, (a, p) 1. Khi đó p–1 mod pChứng minhXét số a, 2a, 3a, …, (p 1)a. Ta chứng minh rằng không tồn tại số đồng dư trong phépchi cho p.Giả sử ka la mod với k, {1,2,…,p 1} và a(k l) (mâuthuẩn)Vậy khi chia số trên cho ta nhận được số dư khác nhau từ 1, 2,…, 1. Suy ra a. 2a. …(p 1)a 1.2….(p 1) mod (p 1)!. p–1 (p 1)! mod pVì ((p 1)!,p) nên p–1 mod p.Từ định lý ta có mod (với 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 nếu với mỗi số nguyên ytồn tại duy nhất một xi sao cho xi mod m.Tập {1,2,…, 1, m} là một hệ thặng dư đầy đủ modulo m* Mọi hệ thặng dư đầy đủ modulo đều có đúng phần tử* Một tập gồm phần tử là một hệ thặng dư đầy đủ modulo nếu và chỉ nếu hai phầntử khác nhau bất kỳ của nó không đồng dư với nhau modulo m.* Cho số nguyên và 0. Tập hợp tất cả các số nguyên thỏa mãn mod đượcgọi là một lớp đồng dư modulo m, ký hiệu {}a mt Z= Có lớp đồng dư phân biệtmodulo m, thu được bằng cách lấy lần lượt 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 nếu (ri ,m) 1,ri rj j, i, và với mọi số nguyên nguyên tố cùng nhau với thì tồn tại ri sao cho ri mod m.Số các phần tử của hệ thặng dư thu gọn modulo được xác định bởi hàm Euler (m)jlà số cácsố nguyên dương không vượt quá và nguyên tố cùng nhau với m.5. Hàm phi Euler10Trên đây chỉ là phần trích dẫn 10 trang đầu của tài liệu và có thế hiển thị lỗi font, bạn muốn xem đầyđủ tài liệu gốc thì ấn vào nút Tải về phía dưới.
