Chương 1 được tham khảo chủ yếu từ tài liệu [1| và một phần nhỏ trong tài liệu [3]. Các kiến thức ở chương này nhằm chuẩn bị những kiến thức cơ bản giúp cho việc trình bày chương sau được hệ thống và dễ theo dõi hơn.1 sẽ nhắc lại về lý thuyết chia hết trong tập số nguyên; đồng thời mục này cũng nhắc lại khái niệm hệ số nhị thức và định lý nhị thức.2 nhắc lại các khái niệm cơ bản về đồng dư thức thức, hệ thặng dư đầy đủ, định lý Euler, định lý Fermat nhỏ, phương trình đồng dư.1 Lý thuyết chia hết trong tập số nguyên Trong tập hợp số nguyên Z, các phép toán cộng, trừ và nhân luôn thực hiện được, tuy nhiên phép chia cho một số nguyên khác 0 không phải bao giờ cũng thực hiện được, nghĩa là phương trình ø+ = b, trong đó a,b € Z;a £0 khong phải lúc nào cũng có nghiệm trong Z. Trong trường hợp a+ = b có nghiệm trong Z, ching ta đi đến khái niệm chia hết. Giả sử a, 0 là hai số nguyên, ö # 0.
Ta nói b chza hết œ hay Ò là một ước của œ và kí hiệu b | ø nếu như có một số nguyên q sao cho a = bq. Khi đó ta cũng nói a chia hết cho b hay a là bội của b và viết aid. Khi ð không chia hết ø ta kí hiệu là b‡ a. Trong tập số nguyên Z, ta có (i) —5 chia hét 10 hay 10 chia hét cho —5, vi 10 = (—2).
5 (ii) 1 va —1 1A ước của mọi số nguyên a vi a = 1. (iii) 0 1A boi cha moi s6 nguyén b 4 0 vi 0 = ð. Néu b| avaa £0 thi tt a = bg ta c6 ¢ £0 do dé |q| > 1 cho nên |a| = |b|. Các tính chất chia hết sẽ được trình bày vấn tắt dưới đây.
() Số nguyên aø là ước của 1 khi và chỉ khi œ = +1. Nếu ø | b và b| a thì a = +Ö. (iii) ) (iv) Nếu b| ai, b | aạ,.,Ð | an, với Ù,ai,da,. Với mỗi cặp số nguyên a,b cho trước (b # 0), tồn tại duy nhất cặp số nguyên q,r thỏa mãn hệ thức a=bq+r, 0<r< |Ù.
Sự tồn tại cặp số nguyên g,r: Xét tập hợp ă gồm các bội của b không vượt quá ø M = {bz:z € Z,bz < a}.|ø| là một bội của b không vượt qua a nén M # Ú. Hơn nữa, M la một bộ phận của Z2 và bị chặn trên bởi ø do đó trong Mƒ có số lớn nhất, chẳng hạn là bg,ø € Z. Vì |b| > 1 nên ba + |b| > bạ, do đó bạ + |b| £ M cũng là bội của b cho nên ta có bq < a< bq + |b| hay 0 < a— bạ < |b|. Đặt = aT— bq ta được r € Z, a = bq +r và 0 < r < |b|.
Để chứng minh tính duy nhất của cặp g,r ta giả sử có cặp số nguyên đi,7¡ cùng thỏa mãn hệ thức a=bqtr,0<r< |); a = bại +rị, 0 Sr¡ < ||. Từ đây ta có b(q— gi) =— —ri) và |r — rị| < |b|. Khi đó do |b| > 0 và |b||g — øi| = |r — ri| < |b| ta được |g — gi | < 1. Do đó |q — m| = 0 hay q = q kéo theo r = 1).
Oo Dinh nghia 1. Cho a,b la cdc s6 nguyên cho trước, b # 0. Khi có đẳng thức a = bg +r, trong dé g là một số nguyên, 0 < r < |b|, thì ta nói a chia cho b được thương là q uà số dư r. Trong trường hợp số dư z = 0, ta có a = Ùq, nghĩa là ø chia hết cho ö.
Như vậy, phép chia hết là một trường hợp riêng của phép chia có dư. Số nguyên đ được gọi là một ước chung của các số nguyên ứ, đa,., đ„ nếu đ là ước đồng thời của mỗi số nguyên đó. Một ước chung đ của các số nguyên ø\, đa,., d„ sao cho mọi ước chung của ơ,da,., „ đều là ước của đ được gọi là ước chưng lớn nhất (viết tắt là ƯCLN) của các số đó., ø„ được gọi là nguyên tố cùng nhau nếu như ƯCLN của các số đó là 1. Số tự nhiên lớn hơn 1 không có ước nào khác ngoài 1 và chính nó được gọi là số nguyên tố.
Chúng ta sẽ nhắc lại định lý cơ bản nhưng không đề cập đến chứng mình của nó. Mỗi số tự nhiên lớn hơn 1 đều phân tích được thành tích những thừa số nguyên tố uà sự phân tích đó là duy nhất nếu không kể đến thú tự của các thừa số. Nội dung định lý cơ bản đã nói lên vai trò quan trọng của số nguyên tố trong tập các số tự nhiên: mỗi số tự nhiên lớn hơn 1 đều được “cấu tạo” từ những số nguyên tố bởi phép nhân, mà chúng ta biết số nguyên tố là những số có ít ước nhất. Từ định lý cơ bản, các nhà toán học đã đi đến các ứng dụng của nó như: tiêu chuẩn chia hết, ước chung lớn nhất - bội chung nhỏ nhất.
Các ứng dụng của định lý cơ bản đã được đề cập trong chương trình học đại học, trong luận văn này ta bỏ qua không nhắc lại. Phần cuối của mục này ta nhắc lại khái niệm và tính chất của hệ số nhị thức. Cho ø,z là các số nguyên không âm, hệ số nhị thức được kí hiệu là () = eo néu r <n va bang 0 nếu ngược lại; ta cũng thường kí hiệu hệ số nhị thức bởi C7. Từ định nghĩa, ta có (8) =1 = (") va (") = (,",) Định lý 1.
Cho œ va r la hai số nguyên dương, trong đó r <Sn. Ta sẽ biến đổi về phải và đưa dần dần về về trái: n—1 n—1 (n— 1)! (n — 1)! (-7)¬{ r ha. Œho +, là bai số thực bất kỳ oà n là số nguyên không âm. Chứng mình bằng phương pháp quy nạp.
Do đó giả thiết đúng với m„ = 0. Giả sử định lý đúng với số k > 0 nào đó, tức là (ø +)” -`Ệ jer (1.1) r=0 (+) theo công thức 1.1 - k+1 k+1-r, 7 k+1 x yt (" i) 1 “ fk+l1 k+1 ) + Jarre ( né (theo định lý 1.9) r r=1 Do vay theo quy nạp, giả thiết trên đúng với mọi số nguyên n > 0.2 Đồng dư thức và phương trình đồng dư Đồng dư là một phương pháp có tính chất bổ trợ về mặt kỹ thuật để giải quyết vẫn đề chia hết trong vành số nguyên. Chúng ta đã biết tập hợp các số dư trong phép chia các số nguyên cho một số tự nhiên cho trước là tập hữu hạn phần tử, trong khi tập hợp số nguyên Z là một tập vô hạn phần tử. Vì thế ta có thể chuyển việc nghiên cứu trên Z về nghiên cứu trên một tập hợp hữu hạn.
Ta nói œ đồng dư tới b theo modulo m, ki hiéu a = b (mod m), néu trong cdc phép chia a va b cho m ta dudc cing mot sé du, nghĩa là có các số nguyên gị, gs,7 với 0<r<m, sao choa=mq+r vab=mq tr. Trong trường hợp không xảy ra ø đồng dư với b theo modulo m ta việt a # b (mod mm). Ta có 3 = 10 (mod 7);—25 = 23 (mod 8) Để thấy được ý nghĩa của đồng dư thức, ta nhắc lại các điều kiện tương đương với định nghĩa của nó ở định lý sau. Các mệnh đề sau đâu là tương đương () a,b đồng dư uới nhau theo modulo mm; (ii) m chia hét a — b; (ii) Tồn tại số nguyên † sao cho a = b+ ml.
Từ định nghĩa và định lý trên, chúng ta có thể dễ dàng suy ra các tính chất của đồng dư thức sau đây: Chú ý 1. (ñ) Ta có thể cộng, trừ hoặc nhân từng vế của nhiều đồng dư thức theo cùng một modulo. Cụ thể là e a, = by (mod m) va ag = by (mod m) => ai + ay = by + by (mod m). That vay, tt a; = b; (mod m) va az = bp (mod m) ta 6 t,t, € Z sao cho ay = by + nh, q2 — bo + mMto.
Do đó ay £ ag = b) bg 4+ M(t + ta) S ay HaQ= bi +b2 (mod m). That vay, @102 = byby + m(boty + bite + mtyte) > a1. (iv) Ta có thể chia hai về của một đồng dư thức cho một ước chung của chúng nguyên tố với modulo. 10 (v) Ta có thể nhân hai vế và modulo của một đồng dư thức với cùng một số nguyên dương.
Nghĩa là œ=b_ (modm) > ae=Ùc_ (mod rnc),Ve € Z,c> 0. Tương tự, ta có thể chia hai vế và modulo của một đồng dư thức cho một ước chung dương của chúng. Cụ thể là a_b m 5 = 5 (mod 5): Ta biết rằng quan hệ đồng dư theo modulo là một quan hệ tương a=b (mod m),0 <6 € Z,6 | UCLN(a,b,m) > đương trong tập số nguyên Z cho nên tồn tại tập thương Z trên quan hệ tương đương này. Tập thương của Z trên quan hệ đồng dư theo modulo m gọi là tập các lớp thăng dư modulo m và kí hiệu là Z2.
Mỗi phần tử A của Z„„ được gọi là một lớp thăng dư modulo rn. Với AC Z7 vaa € A, ta ki hiéu G@={xE€Z|x=a (mod m)} thi @ = A. Nhu vậy, mỗi lớp thang du A modulo m cé dang @ (mod m), với œ là một phần tử tùy ý của 4. Phần tử ø như thé được gọi là một dai diện của lớp A và cũng gọi là một £hăng du modulo m.
Ta dé thay tap hop Zm com phan ti. Trong Zs, l6p thang du 1 (mod 8) 1a I={z€Z:z=1 (mod8)}={. N6i céch khác ƯCLN(A,mm) = UCLN(a,m) véia € A. (1ñ) Trong Z„„, tập hợp các lớp thặng dư nguyên tố với modulo m dugc ki hiệu bởi Z„.
Như vậy ZŸ, ={A Z„ : UCLN(A,m) = 1}. Số các phần tử của tập hợp Zÿ, được kí hiệu là (mm) (ta gọi là hàm Euler). Vì vậy, có thể nói g(m) là các số tự nhiên không vượt quá mm — và nguyên tố với rm. Ta cũng biết rằng Z„„ = {1,2,.
Trong Z¿ = {Ũ, 1,2,3, 4,5,6, 7} ta có ƯCLN(0, §) = 8,ƯCLN(T,§) = 1,ƯCLN(2,8) = 2,ƯCLN( ƯCLN(1. Các lớp nguyên tố với modulo 8 là 1, 3, 5, 7. Tổng quát hơn ta Ví dụ 1. Ta có ¿(1) = 1, có ¿(p) = p— 1 với p là số nguyên tố.
Tap hop gồm những số nguyên lấy ra ở mỗi lớp thặng dư của Z„ một và chỉ một số được gọi là hệ thăng du day di modulo m.