Tài liệu định lý euler

Định lý Euler Định lý Euler phát biểu rằng nếu n là số nguyên dương bất kỳ và a là số nguyên tố cùng nhau với n, thì trong đó φ(n) là ký hiệu của phi hàm Euler đếm số các số nguyên giữa 1 và n nguyên tố cùng nhau với n. Đây là tổng quát hóa của định lý nhỏ Fermat vì nếu n = p là số nguyên tố thì φ(p) = p − 1. Định lý này có thể được sử dụng để dễ dàng giản ước với mô-đun n rất lớn. Ví dụ tìm chữ số tận cùng của số 7222. 7222 ≡ 74x55 + 2 ≡ (74)55x72 ≡ 155x72 ≡ 49 ≡ 9 (mod 10). Vậy 7222 có chữ số tận cùng là 9. Định lý Euler cũng là định lý cơ bản của các hệ thống mã hóa RSA. Chứng minh Gọi là các số nguyên dương nhỏ hơn và nguyên tố cùng nhau với . Với mọi 2 số phân biệt : . Do vậy, là một hoán vị theo mô-đun của . Suy ra . Giản ước đồng dư thức, . Định lý được chứng minh. Định lý Femart tương đương với định lý Euler 1. Định lý Femart : giả sử p là số nguyên tố, a là 1 số nguyên dương khi đó a^(p - 1) = 1(Mod p) 2. Định lý Euler : m là số nguyên dương a là một số nguyên sao cho (a,m) = 1; gọi L = tổng số các số nguyên i (i < m) mà i nguyên tố với m. Khi đó a^L = 1 (Mod p); Chứng minh Định lý Wilson bằng công thức nội suy K ỳ trước chúng ta đã học về hai công thức nội suy cho đa thức, đó là công thức nội suy Newton và công thức nội suy Lagrange. Cả hai công thức này đều có thể dùng để chứng minh Định lý Wilson. Nguyễn Thái Sơn Page 1 Ở đây, chúng ta chỉ trình bày một cách chứng minh định lý Wilson sử dụng công thức nội suy Newton. Xin dành cho các bạn phần còn lại, đó là chứng minh Định lý Wilson sử dụng công thức nội suy Lagrange. Định lý Wilson là một định lý nổi tiếng trong số học. Định lý này nói rằng nếu p là một số nguyên tố thì số (p−1)!+1 sẽ chia hết cho p. Ví dụ, với p=2, 1!+1=2 chia hết cho 2 với p=3, 2!+1=3 chia hết cho 3 với p=5, 4!+1=25 chia hết cho 5 với p=7, 6!+1=721 chia hết cho 7     Có nhiều cách chứng minh Định lý Wilson. Kỳ trước, chúng ta đã trình bày một cách chứng minh sử dụng phép sai phân của đa thức ΔP(x)=P(x+1)−P(x) Lời giải mà chúng ta sắp trình bày đây sẽ sử dụng công thức nội suy Newton. N ếu P(x) là một đa thức bậc n và x1, x2, …, xn, xn+1 là n+1 số khác nhau thì công thức nội suy Newton là công thức sau đây P(x)=α1+α2(x−x1)+α3(x−x1)(x−x2)+⋯+αn+1(x−x1)(x−x2)…(x−xn) Các hệ số trong công thức nội suy Newton được xác định như sau. Muốn xác định hệ số α1, chúng ta thay x=x1 vào công thức. Muốn xác định hệ số α2, chúng ta thay x=x2. Tương tự như vậy, hệ số cuối cùng αn+1 sẽ được xác định nếu chúng ta thay x=xn+1. V ậy để chứng minh định lý Wilson, chúng ta sẽ sử dụng công thức nội suy Newton cho đa thức Chúng ta sẽ dùng đa thức sau đây P(x) nào? P(x)=xp−1−1 Đa thức này là từ định lý nhỏ Fermat mà ra. Định lý nhỏ Fermat. Nếu p là số nguyên tố và số a không chia hết cho p thì ap−1=1(modp). Các bạn có thể đọc cách chứng minh định lý nhỏ Fermat ở đây. Định lý nhỏ Fermat nói lên điều gì? Đó là nếu chúng ta chọn đa thức giá trị P(1), P(2), P(3), …, P(p−1) đều chia hết cho p. Đ P(x)=xp−1−1 như trên thì định lý nhỏ Fermat cho ta biết rằng các a thức P(x)=xp−1−1 có bậc là p−1 và chúng ta sẽ sử dụng x1=1, x2=2, …, xp=p cho công thức nội suy Newton như sau P(x)=xp−1−1=α1+α2(x−1)+α3(x−1)(x−2)+⋯+αp(x−1)(x−2)…(x−(p−1)) Bây giờ chúng ta lần lượt thayx=1,2,3,…để xác định các hệ sốα1,α2,α3,….  Đầu tiên, với x=1, chúng ta có α1=0, do đó P(x)=xp−1−1=α2(x−1)+α3(x−1)(x−2)+⋯+αp(x−1)(x−2)…(x−(p−1))  Với x=2, chúng ta có P(2)=α2. Vì P(2) chia hết cho p theo định lý nhỏ Fermat, cho nên α2=pβ2. Nguyễn Thái Sơn Page 2 Với x=3, chúng ta có  P(3)=2α2+2α3, do đó 2α3=P(3)−2α2=pz3−2pβ2=pβ3, cho nên α3=pβ3γ3, trong đó (γ3,p)=1. Với x=4, chúng ta có  P(4)=3α2+6α3+3!α4 do đó 3!α4=P(4)−3α2−6α3=pz4−3pβ2−6pβ3γ3=pβ4γ3, cho nên α4=pβ4γ4, trong đó (γ4,p)=1. Tương tự, chúng ta sẽ thấy rằng với mọi  i=2,3,4,5,…,p−1 thì αi=pβiγi, trong đó (γi,p)=1. Hệ số cuối cùng αp thì sao? Nếu chúng ta so sánh hệ số của bậc p−1 trong công thức nội suy Newton P(x)=xp−1−1=α2(x−1)+α3(x−1)(x−2)+⋯+αp(x−1)(x−2)…(x−(p−1)) thì chúng ta sẽ thấy rằng ở vế bên trái, hệ số của xp−1 chính là 1, còn ở vế bên phải hệ số của xp−1 chính là αp. Do đó αp=1. αi, và công thức nội suy Newton trở thành P(x)=xp−1−1=pβ2γ2(x−1)+pβ3γ3(x−1)(x−2)+⋯+(x−1)(x−2)…(x−(p−1)) Tóm lại, chúng ta đã xác định toàn bộ các hệ số Bây giờ nếu thay x=0 vào, chúng ta sẽ có −1=pβ2γ2(−1)+pβ3γ3(−1)22!+⋯+pβp−1γp−1(−1)p−2(p−2)!+(−1)p−1(p−1)! Do đó (−1)p−1(p−1)!+1=pbγ2γ3…γp−1 Ở đẳng thức trên, vế bên trái là một số nguyên, do đó pb phải chia hết cho γ2 hết cho p cho nên b phải chia hết cho γ2 γ3… γp−1. Tức là γ3… γp−1. Nhưng các số γ2, γ3, …, γp−1không chia bγ2γ3…γp−1 là một số nguyên. Chúng ta suy ra Từ đó chúng ta có định lý Wilson (−1)p−1(p−1)!+1=0(modp) (p−1)!+1=0(modp) H ôm nay chúng ta đã chứng minh định lý Wilson bằng cách sử dụng định lý nhỏ Fermat và công thức nội suy Newton. Chúng ta tạm dừng ở đây, và xin hẹn gặp lại các bạn ở kỳ sau. Bài tập về nhà. Chứng minh định lý Wilson bằng cách sử dụng công thức nội suy Lagrange. Chứng minh lại định lý Wilson K ỳ trước chúng ta đã học về modulo cho số hữu tỷ. Để miêu tả ứng dụng của nó, hôm nay chúng ta sẽ chứng minh lại Định lý Wilson bằng cách sử dụng ngôn ngữ modulo. Định lý Wilson là một định lý nổi tiếng trong số học. Định lý này được phát biểu như sau. Nguyễn Thái Sơn Page 3 Định lý Wilson. Nếu p là một số nguyên tố thì (p−1)!=−1(modp). Ví dụ,  với p=2, 1!=1=−1(mod2) với p=3,  2!=2=−1(mod3) với p=5,  4!=24=−1(mod5) với p=7,  6!=720=−1(mod7) T hường thường để giải quyết một bài toán về số nguyên bằng cách sử dụng modulo cho số hữu tỷ thì chúng ta sử dụng một định lý đơn giản sau đây Định lý. Cho n, a, b là các số nguyên. Vậy thì a=Qb(modn) sẽ tương đương với điều kiện a=b(modn). Giả sử chúng ta cần chứng minh a=b(modn) cho hai số nguyên a và b nào đó. Đôi khi, nếu chúng ta chứng minh theo modulo cho số nguyên thì có thể rất khó để chứng minh được trực tiếp a=b(modn). Tuy nhiên, nếu chúng ta dùng modulo cho số hữu tỷ, thì trong quá trình chứng minh, chúng ta không còn bị hạn chế bởi số nguyên nữa, mà chúng ta có thể dùng cả những số hữu tỷ. Và nhờ vậy, có thể chúng ta sẽ chứng minh được a=Qb(modn) một cách dễ dàng hơn. Rồi từ đây, chúng ta sử dụng định lý trên để đưa về a=b(modn). B ây giờ chúng ta sẽ dùng phương pháp trên để chứng minh Định lý Wilson. Lời giải sẽ dùng công thức nội suy Newton với đa thức sau đây P(x)=xp−1−1. Theo Định lý nhỏ Fermat thì đa thức này sẽ có tính chất sau đây P(1)=P(2)=P(3)=⋯=P(p−1)=0(modp). Chứng minh Định lý Wilson sử dụng công thức Newton Nếu P(x) là một đa thức bậc n và x1, x2, …, xn, xn+1 là n+1 số khác nhau thì công thức nội suy Newton là công thức sau đây P(x)=α1+α2(x−x1)+α3(x−x1)(x−x2)+⋯+αn+1(x−x1)(x−x2)…(x−xn) Các hệ số trong công thức nội suy Newton được xác định như sau. Muốn xác định hệ số α1, chúng ta thay x=x1 vào công thức. Muốn xác định hệ số α2, chúng ta thay x=x2. Tương tự như vậy, hệ số cuối cùng αn+1 sẽ được xác định nếu chúng ta thay x=xn+1. Đa thức mà chúng ta sẽ dùng là đa thức suy Newton sẽ trở thành như sau P(x)=xp−1−1 có bậc là p−1. Chúng ta sẽ sử dụng x1=1, x2=2, …, xp=p. Công thức nội P(x)=xp−1−1=α1+α2(x−1)+α3(x−1)(x−2)+⋯+αp(x−1)(x−2)…(x−(p−1)) Nguyễn Thái Sơn Page 4 Rõ ràng các số αi là các số hữu tỷ. Chúng ta sẽ chứng minh hai điều sau:   αp=1 với mọi i=1,2,…,p−1, αi=Q0(modp). Chứng minh αp=1 Để chứng minh αp=1, chúng ta so sánh hệ số của bậc p−1 trong công thức nội suy Newton P(x)=xp−1−1=α1+α2(x−1)+α3(x−1)(x−2)+⋯+αp(x−1)(x−2)…(x−(p−1)) xp−1 chính là 1, còn ở vế bên phải hệ số của xp−1 chính là αp. Do đó αp=1. Chúng ta thấy rằng ở vế bên trái, hệ số của Chứng minh αi=Q 0(modp) cho các trường hợp i=1,2,…,p−1 Từ công thức nội suy P(x)=xp−1−1=α1+α2(x−1)+α3(x−1)(x−2)+⋯+αp(x−1)(x−2)…(x−(p−1))  Thay x=1, chúng ta có  Thay x=2, chúng ta có α1=0 P(2)=α2. Theo Định lý nhỏ Fermat thì P(2)=0(modp), do đó α2=Q0(modp)  Thay x=3, chúng ta có P(3)=α2(3−1)+α3(3−1)(3−2). 0(modp), do đó α3(3−1)(3−2)=Q0(modp). Theo Định lý nhỏ Fermat thì P(3)=0(modp), chúng ta lại có α2=Q Từ đó suy ra α3=Q0(modp)  Tương tự, thay x=i, chúng ta có P(i)=α2(i−1)+α3(i−1)(i−2)+⋯+αi(i−1)! Theo Định lý nhỏ Fermat thì P(i)=0(modp), chúng ta lại có α2=Qα3=Q⋯=Qαi−1=Q0(modp), do đó αi(i−1)!=Q0(modp), từ đó suy ra αi=Q0(modp). Tóm lại, chúng ta chứng minh được   αp=1 với mọi i=1,2,…,p−1, αi=Q0(modp). Do đó từ công thức Newton P(x)=xp−1−1=α1+α2(x−1)+α3(x−1)(x−2)+⋯+αp(x−1)(x−2)…(x−(p−1)) x thì P(x)=xp−1−1=Q(x−1)(x−2)…(x−(p−1))(modp) chúng ta suy ra rằng với mọi số hữu tỷ Thay x=0, chúng ta có −1=Q(−1)(−2)…(−(p−1))(modp). Tức là Nguyễn Thái Sơn (−1)p−1(p−1)!=Q−1(modp). Page 5 Nhưng cả hai vế là số nguyên, cho nên (−1)p−1(p−1)!=−1(modp). Từ đó chúng ta có Định lý Wilson (p−1)!=−1(modp). H ôm nay chúng ta đã chứng minh định lý Wilson bằng cách sử dụng định lý nhỏ Fermat và công thức nội suy Newton. Cách chứng minh này dùng ngôn ngữ modulo cho số hữu tỷ. Các bạn có thể đọc thêm các bài viết về Định lý Wilson trên blog này theo các link sau đây: Định lý Wilson I, Định lý Wilson II. Chúng ta tạm dừng ở đây, và xin hẹn gặp lại các bạn ở kỳ sau. Bài tập về nhà. Chứng minh định lý Wilson bằng cách sử dụng công thức nội suy Lagrange theo các bước sau đây. Giả sử p là một số nguyên tố. 1. Cho f(x) là một đa thức có hệ số hữu tỷ và có bậc bé thua hoặc bằng p−2. Dùng công thức nội suy Lagrange để chứng minh rằng nếu thì tất cả các hệ số của đa thức f(1)=Qf(2)=Qf(3)=Q⋯=Qf(p−1)=Q0(modp) f(x) sẽ =Q 0(modp). 2. Cho f(x) là một đa thức có hệ số nguyên và có bậc bé thua hoặc bằng p−2. Chứng minh rằng nếu f(1)=f(2)=f(3)=⋯=f(p−1)=0(modp) thì tất cả các hệ số của đa thức f(x) sẽ =0(modp). 3. Lấy Chứng minh rằng các hệ số của đa thức f(x)=(xp−1−1)−(x−1)(x−2)…(x−(p−1)) f(x) sẽ =0(modp). Hệ số tự do của đa thức trên bằng −1−(−1)p−1(p−1)! Từ đó suy ra Định lý Wilson. Nguyễn Thái Sơn Page 6 Định lý Wilson H ôm nay xin giới thiệu với các bạn một định lý liên quan đến số nguyên tố, đó là Định lý Wilson. Định lý này nói rằng nếu plà một số nguyên tố thì số (p−1)!+1 sẽ chia hết cho p. Ở đây, ký hiệu n! có nghĩa là n!=1×2×3×⋯×n. Ví dụ,     C 1!+1=2 chia hết cho 2 2!+1=3 chia hết cho 3 4!+1=25 chia hết cho 5 6!+1=721 chia hết cho 7 ó nhiều cách chứng minh Định lý Wilson. Cách chứng minh mà chúng ta sắp trình bày ở đây là cách chứng minh sử dụng định lý nhỏ Fermat. Định lý nhỏ Fermat. Nếu p là số nguyên tố và số a không chia hết cho p thì ap−1=1(modp). Các bạn có thể đọc cách chứng minh định lý nhỏ Fermat ở đây. Để chứng minh định lý Wilson, chúng ta sẽ sử dụng một vài tính chất của đa thức. Các tính chất này mặc dù rất đơn giản nhưng nếu chúng ta biết cách sử dụng thì nó sẽ trở nên rất hữu ích trong việc giải toán. T rước tiên chúng ta nói một chút về đa thức. Đa thức có dạng như sau P(x)=anxn+an−1xn−1+⋯+a1x+a0. Đa thức P(x) này có bậc là n và các số a0,a1,…,an gọi là các hệ số. Số a0 gọi là hệ số tự do, số a1 là hệ số bậc 1, a2là hệ số bậc 2,..., an là hệ số bậc n. Số a0 còn được gọi là hệ số cuối cùng và an gọi là hệ số đầu tiên của đa thức. Bây giờ chúng ta phát biểu một vài tính chất của đa thức. Tính chất 1. Đối với đa thức thì hệ số cuối cùng có thể được tính như sau: P(x)=anxn+an−1xn−1+⋯+a1x+a0 a0=P(0). Rõ ràng khi thay x=0 thì P(0)=a0. Do đó, tính chất 1 là hiển nhiên. Nguyễn Thái Sơn Page 7 Tính chất 2. Nếu P(x) là đa thức có bậc là n≥1, thì ΔP(x)=P(x+1)−P(x) sẽ là một đa thức có bậc n−1. Chúng ta chứng minh tính chất 2 này cho một trường hợp đặc biệt là đa thức xn, trường hợp tổng quát sẽ từ đó mà suy ra. Đối với đa thức xn, chúng ta có Δxn=(x+1)n−xn=nxn−1+(n2)xn−2+(n3)xn−3+⋯+nx+1 Vậy Δxn là một đa thức bậc n−1. Đối với trường hợp tổng quát thì ΔP(x)=anΔxn+an−1Δxn−1+⋯+a1Δx Vì Δxn là đa thức bậc n−1, Δxn−1 là đa thức bậc n−2, ..., do đó ΔP(x) là một đa thức bậc n−1. Tính chất 3. Hệ số đầu tiên của đa thức ΔP(x) sẽ bằng nan. Như ở trên chúng ta đã chứng minh rằng hệ số đầu tiên là nan. B Δxn là đa thức bậc n−1 với hệ số đầu tiên bằng n, do đó đa thức ΔP(x)=anΔxn+… sẽ có ây giờ chúng ta sử dụng ba tính chất trên của đa thức để chứng minh định lý Wilson. Định lý Wilson. Với mọi số nguyên tố p thì (p−1)!=−1(modp) Chứng minh. Chúng ta sẽ dùng đa thức f1(x)=xp−1−1 Chúng ta có những nhận xét về đa thức này như sau  f1(x) là một đa thức bậc p−1  hệ số đầu tiên của đa thức f1(x) là 1  hệ số cuối cùng của đa thức f1(x) là −1  theo định lý nhỏ Fermat, f1(1)=f1(2)=f1(3)=⋯=f1(p−1)=0(modp). Bây giờ chúng ta tạo đa thức mới như sau    f2(x)=Δf1(x)=f1(x+1)−f1(x) Theo tính chất 2 về đa thức mà chúng ta đã nói ở trên thì f2(x) là đa thức bậc p−2. Theo tính chất 3 thì hệ số đầu tiên của đa thức f2(x) là p−1. Và vì f2(x)=f1(x+1)−f1(x) cho nên f2(1)=f2(2)=⋯=f2(p−2)=0(modp). Tương tự với đa thức f3(x)=Δf2(x)=f2(x+1)−f2(x) chúng ta có  f3(x) là một đa thức bậc p−3  hệ số đầu tiên của đa thức f3(x) là (p−1)(p−2)  f3(1)=f3(2)=⋯=f3(p−3)=0(modp) Cuối cùng với đa thức fp−1(x)=Δfp−2(x)=fp−2(x+1)−fp−2(x) thì    fp−1(x) là một đa thức bậc 1 hệ số đầu tiên của đa thức fp−1(x) là (p−1)(p−2)…2=(p−1)! fp−1(1)=0(modp) Bây giờ chúng ta xem xét hệ số cuối cùng của các đa thức này.  Hệ số cuối cùng của đa thức f1(x) là f1(0)=−1.  Hệ số cuối cùng của đa thức f2(x) là Nguyễn Thái Sơn Page 8 f2(0)=f1(1)−f1(0)=−f1(0)(modp)  Hệ số cuối cùng của đa thức f3(x) là  Hệ số cuối cùng của đa thức fp−1(x) là f3(0)=f2(1)−f2(0)=−f2(0)(modp) fp−1(0)=fp−2(1)−fp−2(0)=−fp−2(0)(modp) Từ đó suy ra fp−1(0)=(−1)p−2f1(0)=1(modp). Tóm lại, fp−1(x) là một đa thức bậc 1, có hệ số đầu tiên là (p−1)!, hệ số cuối cùng là fp−1(0)=1(modp), cho nên fp−1(x)=(p−1)!x+c, ở đây, c=1(modp). Ở trên chúng ta đã chỉ ra rằng fp−1(1)=0(modp), tức là (p−1)!+c=0(modp) Kết hợp với c=1(modp), chúng ra suy ra định lý Wilson là (p−1)!+1=0(modp).■ Như vậy chúng ta đã chứng minh xong định lý Wilson. Chúng ta thấy rằng ba tính chất của đa thức ở trên mặc dù rất đơn giản nhưng đã giúp cho chúng ta chứng minh được định lý Wilson. Đặc biệt, chúng ta đã sử dụng công thức ΔP(x)=P(x+1)−P(x). Công thức này tương tự như là phép lấy đạo hàm trong giải tích vậy. Chúng ta tạm dừng ở đây, hẹn gặp lại các bạn ở kỳ sau. Bài tập về nhà. 1. Viết lại chi tiết cách chứng minh định lý Wilson cho trường hợp p=5. 2. Chứng minh rằng nếu n>1 và (n−1)!=−1(modn) thì n là một số nguyên tố. 3. Thay vì đặt ΔP(x)=P(x+1)−P(x), chúng ta có thể đặt ΔP(x)=P(x)−P(x−1). Phát biểu tính chất 2 và tính chất 3 cho trường hợp này. Nguyễn Thái Sơn Page 9 Định lý Euclid về số nguyên tố T iếp tục câu chuyện về số nguyên tố, hôm nay chúng ta sẽ chứng minh rằng tồn tại vô số các số nguyên tố. Đây chính là Định lý Euclid về số nguyên tố. Định lý này có một cách chứng minh rất là đơn giản, nhưng cách chứng minh này có lẽ là một trong những chứng minh hay nhất trong toán học. C húng ta chứng minh tồn tại vô số số nguyên tố như sau. Giả sử rằng p1, p2, ..., pk là một dãy số nguyên tố. Chúng ta chỉ ra rằng chúng ta sẽ tìm được một số nguyên tố mới không nằm trong dãy số này. Từ đó suy ra sẽ phải có vô số các số nguyên tố. Để chỉ ra số nguyên tố mới, chúng ta xây dựng số n=p1p2…pk+1. Rõ ràng n sẽ có một ước số nguyên tố p. Nhưng vì n không chia hết cho các số nguyên tố một số nguyên tố mới không nằm trong dãy số này. pi ở trên nên ước số nguyên tố pcủa n sẽ là Tóm tại, cứ lấy bất kỳ một dãy số hữu hạn các số nguyên tố thì chúng ta lại tìm được một số nguyên tố mới, điều đó chứng tỏ sẽ có vô hạn các số nguyên tố. Cách chứng minh ở trên thật là hay. Chúng ta sẽ dùng phương pháp chứng minh này để giải một vài bài toán tương tự. Bài toán 1. Chứng minh rằng có vô số các số nguyên tố có dạng Nguyễn Thái Sơn 4N+3. Page 10 C húng ta biết rằng 2 là số nguyên tố chẵn duy nhất, còn tất cả các số nguyên tố còn lại là số nguyên tố lẻ. Một số nguyên tố lẻ thì hoặc là có dạng 4N+1 hoặc là có dạng 4N+3. Muốn chứng minh rằng có vô số các số nguyên tố có dạng 4N+3, chúng ta lý luận tương tự như trên. Đó là với mọi dãy số nguyên tố p1, p2, ..., pk bất kỳ có dạng 4N+3, chúng ta sẽ chỉ ra được một số nguyên tố mới không nằm trong dãy này và cũng có dạng 4N+3. Chúng ta xây dựng số n=4p1p2…pk−1, số này có dạng 4N+3. Số n này sẽ phải có một ước số nguyên tố p có dạng 4N+3. Vì sao? Bởi vì n là số lẻ lớn hơn 1, cho nên nếu n không có ước số nguyên tố có dạng 4N+3 thì tất cả các ước số nguyên tố của n sẽ có dạng 4N+1. Vậy n sẽ là tích của các số có dạng 4N+1. Nhưng mà chúng ta dễ dàng thấy rằng tích của các số có dạng 4N+1 là một số có dạng 4N+1. Cho nên n cũng có dạng 4N+1, và đây là điều vô lý. Như vậy n sẽ có ước số nguyên tố p có dạng 4N+3. Tiếp theo, chúng ta thấy rằng vì n không chia hết cho các số nguyên tố pi ở trên nên ước số nguyên tố p của n sẽ là một số nguyên tố mới không nằm trong dãy số này. Vậy coi như chúng ta đã tìm ra lời giải cho bài toán. Lời giải bài toán 1. Để chứng minh rằng tồn tại vô số các số nguyên tố có dạng 4N+3, chúng ta sẽ chứng minh rằng, với mọi dãy số nguyên tố p1, p2, ..., pk có dạng 4N+3, sẽ tồn tại một số nguyên tố khác cũng có dạng 4N+3, và không nằm trong dãy số nguyên tố này. Thực vậy, lấy n=4p1p2…pk−1, số này có dạng 4N+3. Đầu tiên chúng ta khẳng định rằng n phải có một ước số nguyên tố có dạng 4N+3. Đó là vì nếu tất cả các ước số nguyên tố của dạng 4N+1 thì n sẽ là tích của các số có dạng 4N+1, suy ra n cũng có dạng 4N+1, vô lý. Tóm lại, n có ít nhất một ước số nguyên tố n có p có dạng 4N+3. Cuối cùng vì n không chia hết cho các số nguyên tố pi nên p≠pi. Tóm tại, cứ lấy bất kỳ một dãy số hữu hạn các số nguyên tố có dạng 4N+3 thì chúng ta lại tìm được một số nguyên tố mới cũng có dạng 4N+3, do đó sẽ tồn tại vô số các số nguyên tố có dạng 4N+3. ■ Bài toán 2. Chứng minh rằng tồn tại vô số các số nguyên tố có dạng L àm theo phương pháp ở trên thì chúng ta sẽ chọn 4N+1. n=4p1p2…pk+1 và tìm cách chứng minh rằng n sẽ có ước số nguyên tố có dạng 4N+1. Tuy nhiên nhìn kỹ ra thì cách chứng minh này không ổn. Đó là vì tích của hai số có dạng 4N+3là số có dạng 4N+1. Do đó có khả năng là n là tích của hai số nguyên tố có dạng 4N+3 và vì vậy n sẽ không có ước số nguyên tố nào có dạng 4N+1. Chúng ta phải tìm cách giải khác. Chúng ta sẽ dùng n=4p21p22…p2k+1. Để chứng minh n có ước số nguyên tố có dạng 4N+1, chúng ta sẽ dùng bổ đề sau. Bổ đề.Với mọi số tự nhiênxthìx2+1không có ước nguyên tố có dạng4N+3. Để chứng minh bổ đề này, chúng ta sẽ sử dụng Định lý nhỏ Fermat. Các bạn có thể đọc thêm về Định lý nhỏ Fermat ở đây: " modulo - Phần 5". Theo định lý nhỏ Fermat thì với mọi số nguyên tố p và với mọi số nguyên a không chia hết cho p, ap−1=1(modp). Bây giờ chúng ta chứng minh bổ đề theo phương pháp phản chứng. Đó là, giả sử như x2+1 có một ước số nguyên tố p=4N+3. Tức là x2=−1(modp). Từ đó chúng ta có x4N+2=(x2)2N+1=(−1)2N+1=−1(modp). Nhưng theo định lý nhỏ Fermat thì Nguyễn Thái Sơn Page 11 x4N+2=1(modp). Vậy 1=−1(modp), hay 2=0(modp). Đây là điều vô lý. Cho nên bổ đề đã được chứng minh. ■ Lời giải bài toán 2. Để chứng minh rằng tồn tại vô số các số nguyên tố có dạng 4N+1, chúng ta sẽ chứng minh rằng, với mọi dãy số nguyên tố p1, p2, ..., pk có dạng 4N+1, sẽ tồn tại một số nguyên tố khác cũng có dạng 4N+1 và không nằm trong dãy số nguyên tố này. Thực vậy, lấy n=4p21p22…p2k+1. Vì n có dạng x2+1, nên theo bổ đề trên mà chúng ta vừa chứng minh, thì n không có ước số nguyên tố có dạng 4N+3. Vì n là số lẻ nên toàn bộ các ước số nguyên tố của n sẽ có dạng 4N+1. Chúng ta lại dễ dàng thấy rằng không một số pinào trong dãy số trên là ước số của n. Vì vậy chúng ta đã tìm được những số nguyên tố mới có dạng 4N+1. Tóm tại, cứ lấy bất kỳ một dãy số hữu hạn các số nguyên tố có dạng dạng 4N+1, do đó sẽ có vô hạn các số nguyên tố có dạng 4N+1. C 4N+1 thì chúng ta lại tìm được một số nguyên tố mới cũng húng ta tạm dừng ở đây. Chỉ xin lưu ý là hai bài toán ở trên là hai trường hợp đặc biệt của một định lý tổng quát. Định lý này gọi là định lý Dirichlet về cấp số cọng. Định lý Dirichlet về cấp số cọng phát biểu như sau: nếu tại vô số các số nguyên tố có dạng aN+b. a và b là hai số nguyên tố cùng nhau thì sẽ tồn Hẹn gặp lại các bạn ở bài sau. Bài tập về nhà. 1. Chứng minh rằng tồn tại vô số các số nguyên tố có dạng 6N+1. 2. Chứng minh rằng tồn tại vô số các số nguyên tố có dạng 6N+5. 3. Thử chọn vài giá trị khác cho Nguyễn Thái Sơn a và b rồi chứng minh rằng tồn tại vô số các số nguyên tố có dạng aN+b. Page 12 Một vài bài toán về số nguyên tố Kỳ trước, chúng ta đã học về số nguyên tố, và Định lý Euclid cho chúng ta biết rằng tồn tại vô hạn các số nguyên tố. Kỳ này, chúng ta tếp tục xem xét về số nguyên tố. Các nhà toán học nổi tếng như Fermat, Euler, Gauss rất thích thú tm hiểu về các số nguyên tố. Có nhiều bài toán về số nguyên tố, phát biểu thì rất đơn giản, nhưng đến nay vẫn chưa ai tm ra được lời giải. Giả thuyết Goldbach Đây có lẽ là bài toán nổi tếng nhất về số nguyên tố. Giả thuyết Goldbach dự đoán rằng mọi số chẵn lớn hơn 2 đều có thể viết được thành tổng của hai số nguyên tố. Ví dụ như        4=2+2 6=3+3 8=3+5 10=3+7=5+5 12=5+7 14=3+11=7+7 ... Nguyễn Thái Sơn Page 13 Nhà toán học Goldbach đã nêu lên giả thuyết này trong một lá thơ gởi cho nhà toán học Euler vào năm 1742. Hiện tại với công cụ máy vi tnh hiện đại, các nhà toán học đã kiểm tra thấy giả thuyết Goldbach đúng đến số hàng tỉ tỉ, tuy nhiên lời giải tổng quát cho mọi số chẵn thì đến nay vẫn chưa ai chứng minh được. Có một số tổ chức đã đưa ra giải thưởng lên đến cả triệu đô la cho người nào giải được bài toán này, nhưng chưa có ai là người may mắn thắng được những giải thưởng này. Bài toán chưa có lời giải. Có đúng hay không rằng mọi số chẵn lớn hơn 2 đều có thể viết được thành tổng của hai số nguyên tố. Định lý Chebyshev Định lý Chebyshev là một kết quả rất đẹp, đó là với mọi * ở giữa 2 và 4 có số nguyên tố 3,  ở giữa 3 và 6 có số nguyên tố 5, n>1, luôn tồn tại một số nguyên tố nằm giữa hai số n và 2n. Ví dụ như, ở giữa 4 và 8 có số nguyên tố 5 và 7, v.v...  Định lý Chebyshev. Với mọi số tự nhiên n>1, luôn tồn tại một số nguyên tố p thoã mãn n0 chứng minh rằng nếu 2n+1 là số nguyên tố thì n phải có dạng n=2m. Tức là nếu 2n+1 là số nguyên tố thì nó phải có dạng 22m+1. 2. Chứng minh rằng tồn tại một đa thức thứ 100. P(x) sao cho P(1)=2, P(2)=3, P(3)=5, P(4)=7, P(5)=11,..., P(100)= số nguyên tố Fermat và định lý cuối cùng của Fermat Hôm nay, 17/08 là kỉ niệm ngày sinh Fermat Pierre de Fermat sinh ngày 17 tháng 8 năm 1601 tại Pháp, ông mất lúc 63 tuổi, vào năm 1665. Fermat là một học giả vĩ đại, một nhà toán học nổi tiếng và là cha đẻ của lý thuyết số hiện đại. Fermat xuất thân từ một gia đình khá giả, ông học ở Toulouse và lấy bằng cử nhân luật dân sự rồi làm chánh án nhưng lại vô cùng say mê toán học với thói quen nổi tiếng là ghi các ghi chú bên lề các quyển sách. Ông vừa là một luật sư, vừa là một nhà toán học đã đóng góp nhiều vào sự phát triển bước đầu của toán học. Đặc biệt, ông được nhớ đến qua sự khám phá một phương pháp đầu tiên để tìm cực đại và cực tiểu của tung độ của đường cong. Ông cũng nghiên cứu về lý thuyết số và có nhiều đóng góp trong các lảnh vực hình học giải tích, xác suất và quang học. Người ta biết đến Fermat không phải là một nhà toán học mà là một luật sư. Định lý cuối cùng của Fermat được nghĩ ra năm 1637 khi Fermat nghiên cứu quyển sách toán cổ Hy lạp Arithmetica, viết bởi Diophantus vào khoảng năm 250 AD. Trang sách đã gợi ý cho Fermat bàn về các tính chất quanh định lý Pythagore, có đại ý là: Trong một tam giác vuông, bình phương của cạnh huyền bằng tổng số bình phương của hai cạnh góc vuông. Nói khác đi, phương trình $x^2+y^2=z^2 $ có vô số lời giải và từ đó sẽ tìm được bộ 3 số Pythagore. Từ định lý Pythagore, Fermat đã tìm xem có 3 số nguyên x,y,z nào thỏa cho một phương trình như phương trình của Pythagore nhưng ở bậc cao hơn hay không xn+yn=zn Nhưng đều thất bại. Theo Fermat thì phương trình này với 3 ẩn số nguyên x,y,z và n>2 không thể giải được. Nguyễn Thái Sơn Page 15 Ông đã viết điều này bên lề quyển Arithmetica đại khái như sau: Không thể nào tách một số lập phương thành tổng số của hai số lập phương khác, hay một số tứ phương thành tổng số của hai số tứ phương khác. Một cách tổng quát: Không thể tách rời bất kỳ lũy thừa bậc lớn hơn hai nào của một số nguyên thành hai lũy thừa cùng bậc của hai số nguyên khác. và ông còn viết thêm: Tôi đã tìm được một chứng minh tuyệt vời cho mệnh đề này nhưng lề của quyền sách này không đủ chỗ để viết. Định lý này của Fermat đã gây cảm hứng cho nhiều thế hệ tiếp theo, không những cho các nhà toán học mà còn cho cả những người hiếu kỳ muốn thử tài mình. Người thì tìm cách chứng minh định lý đó đúng, người thì tìm cách chứng minh định lý đó sai. Các trường hợp n=3 và 5 đã được Euler, Dirichlet và Legendre chứng minh năm 1825 và phải đến 15 năm sau, trường hợp n=7 mới được Gabriel Lamé chứng minh. Một điều không may là các chứng minh đó tương đối dài và khó mà suy rộng đến trường hợp tổng quát. Mặc dầu được gọi là định lý nhưng mệnh đề mà Fermat nêu lên chưa được chứng minh đúng một cách tổng quát. Sở dĩ định lý này được gọi là "Định lý cuối cùng của Fermat" vì tất cả những mệnh đề toán học mà Fermat nêu lên đều đã được chứng minh, trừ mệnh đề này! Năm 1823 và 1850, Hàn lâm viện Khoa học Pháp treo hai giải thưởng cho một lời giải đúng của định lý. Một giải thưởng thứ ba do Hàn lâm viện Brussels đề nghị năm 1883 và năm 1908, nhà toán học tài tử Paul Friedrich Wolfskehl tặng 100,000 Mác cho Hàn lâm viện Khoa học Göttingen để làm giải thưởng. Sau đó thì cả ngàn lời giải đã được gởi đến các Hàn lâm viện trong khoảng thời gian từ 1908 đến 1911, nhưng tất cả đều sai! Theo thời gian, có rất nhiều công trình đã được thực hiện để cố chứng minh định lý sau cùng của Fermat, nhưng tất cả những chứng minh nầy đều được khám phá là sai. Càng cố gắng bao nhiêu, các nhà toán học càng thất vọng bấy nhiêu và một chứng minh được chấp nhận càng xa vời. Nhà toán học người Đức Ernst Kummer đã chứng minh định lý này là đúng với mọi số nguyên tố tới 100 (trừ 3 Số nguyên tố phi chính quy là 37, 59, 67). Nguyễn Thái Sơn Page 16 Cuối cùng nó được chứng minh bởi Andrew Wiles năm 1993 sau gần 8 năm ròng nghiên cứu, phát triển chứng minh các giả thiết có liên quan. Mãi đến tháng 8 năm 1995 hội thảo ở Đại học Boston, giới toán học công nhận chứng minh là đúng. (Xem thêm hành trình chứng minh định lý lớn Fermat từ Wikipedia) Helen G. Grundman, giáo sư toán trường Bryn Mawr College, đánh giá tình hình của cách chứng minh đó như sau: "Tôi nghĩ là ta có thể nói, vâng, các nhà toán học hiện nay đã bằng lòng với cách chứng minh Định lý lớn Fermat đó. Tuy nhiên, một số sẽ cho là chứng minh đó của một mình Wiles mà thôi. Thật ra chứng minh đó là công trình của nhiều người. Wiles đã có đóng góp đáng kể và là người kết hợp các công trình lại với nhau thành cái mà ông đã nghĩ là một cách chứng minh. Mặc dù cố gắng khởi đầu của ông được phát hiện sau đó là có sai lầm, Wiles và người phụ tá Richard Taylor đã sửa lại được, và nay đó là cái mà ta tin là cách chứng minh đúng Định lý lớn Fermat." "Chứng minh mà ta biết hiện nay đòi hỏi sự phát triển của cả một lãnh vực toán học chưa đuợc biết tới vào thời Fermat. Bản thân định lý được phát biểu rất dễ dàng và vì vậy xem ra có vẻ đơn giản một cách giả tạo; bạn không cần biết rất nhiều về toán để hiểu bài toán. Tuy nhiên, để rồi nhận ra rằng, theo kiến thức tốt nhất của bạn, cần phải biết rất nhiều về toán mới có thể giải được nó. Vẫn là một câu hỏi chưa có lời đáp rằng liệu có hay không một cách chứng minh Định lý lớn Fermat mà chỉ liên quan tới toán học và các phương pháp đã có vào thời Fermat. Chúng ta không có cách nào trả lời trừ phi ai đó tìm ra một chứng minh như vậy." (Wikipedia). Nguyễn Thái Sơn Page 17 Nguyễn Thái Sơn Page 18