Ánh Xạ Và Số Nguyên Tố

Nội dung:Ánh xạ, Số nguyên tố - đồng dư thức, Số nguyên tố, Hệ g-phân. Số nguyên tố: Định lý Bezout, Các định lý cơ bản, Định lý Fermat nhỏ, Định lý Euler, Ứng dụng và bảo mật.Phát biểu định lý 1 :Ước số nhỏ nhất khác 1 của một số tự nhiên là một số nguyên tố.Chứng minh định lý 1 : Giả sử a là một số tự nhiên lớn hơn 1, p là ước số nhỏ nhất khác 1 của a ( a=p.k.l). Nếu p là số nguyên tố, bài toán coi như đã xong.Nếu p không...
Nội dung trích xuất từ tài liệu:
Ánh Xạ Và Số Nguyên Tố www.themegallery.comNhóm ILOGO Nội dung Ánh xạ 1 Số nguyên – đồng dư thức 2 Số nguyên tố 3 Hệ g- phân 4 www.themegallery.comNhóm ILOGO Số nguyên tố Định lý Bezout 1 Các định lý cơ bản 2 Định lý Fermat nhỏ 3 Định lý Euler 4 Ứng dụng vào bảo mật 5 www.themegallery.com Nhóm I LOGO Định lý BezoutPhát biểu : Với a,b ∈ N, a>b >=1; ta có : a) Tồn tại x,y ∈ Z : ax+by = (a,b). b) Nếu (a,b) = 1, tồn tại x,y ∈ Z sao cho ax + by = 1. ∈ c) (a,b) =1 nếu và chỉ nếu tồn tại x,y Z : ax + by = 1. www.themegallery.com Nhóm I LOGO Định lý BezoutChứng minh : a) Theo thuật toán Euclide : rn-2 = rn-1 qn-1 + rn hay rn = rn-2 - rn-1 qn-1 (rn là ước chung lớn nhất của a và b) Suy ra : rn là một tồ hợp tuyến tính của rn-1 , rn-2 Tạm viết là : rn  th( rn-1 , rn-2 ) Suy ra : rn  th(rn-2 , rn-3) và : rn-1  th( rn-2 , rn-3 ) Tiếp tục quy nạp ta có được : ∈ rn  th( rn-k , rn-k-1 ) và rn  th( a, b ) Hay tồn tại x,y Z / ax + by = rn = (a,b) (đpcm) www.themegallery.com Nhóm I LOGO Định lý Bezout Chứng minh : b) (a,b) = 1 suy ra tồn tại x,y ∈ Z / ax + by = (a,b) = 1 (đpcm). c) Gọi c là một ước chung của a và b Giả sử ax + by = 1 ⇔ ax + by chia het cho c ∈ ⇔ c là ước của 1 ⇔ c =1. Vậy (a,b) =1 nếu và chỉ nếu tồn tại x,y Z : ax + by = 1.∈⇔ www.themegallery.com Nhóm I LOGO Định lý Bezout Chứng minh : b) (a,b) = 1 suy ra tồn tại x,y ∈ Z / ax + by = (a,b) = 1 (đpcm). c) Gọi c là một ước chung của a và b Giả sử ax + by = 1 ⇔ ax + by chia het cho c ∈ ⇔ c là ước của 1 ⇔ c =1. Vậy (a,b) =1 nếu và chỉ nếu tồn tại x,y Z : ax + by = 1.∈⇔ www.themegallery.com Nhóm I LOGO Các định lý cơ bản Phát biểu định lý 1 : Ước số nhỏ nhất khác 1 của một số tự nhiên là một số nguyên tố. Chứng minh định lý 1 : Giả sử a là một số tự nhiên lớn hơn 1, p là ước số nhỏ nhất khác 1 của a ( a=p.k.l). Nếu p là số nguyên tố, bài toán coi như đã xong. Nếu p không là số nguyên tố ⇒ p = m.n(hay a= m.n.k.l). ⇒ a có 2 ước số m,n www.themegallery.com Nhóm I LOGO Các định lý cơ bảnPhát biểu định lý 2 : Có vô số số nguyên tố.Chứng minh định lý 2: Ta chứng minh bằng phương pháp phản chứng : Giả sử số các số nguyên tố là hữu hạn. Không mất tínhtổng quát ta giả sử chỉ có n số nguyên tố p1, p2,…,pn. Đặt T = p1p2…pn + 1 suy ra T > 1. Theo tính chất 1 thì q > 1 là ước nguyên tố của T. q ∈ S = {p1p2…pn} q | p1p2…pn Và q | T = (p1p2…pn + 1)nên q | 1 suy ra q = 1 ( vô lý vì q > 1) Vậy có vô số số nguyên tố. www.themegallery.com Nhóm I LOGO Các định lý cơ bảnPhát biểu định lý 3 : Định lý cơ bản của số học Mọi số nguyên n>=2 đều có thể biểu diễn duy nhấtthành tích của một số số nguyên tố theo dạng : n p1n1 . p2 2 ..... pk k n n= www.themegallery.com Nhóm I LOGO Các định lý cơ bảnChứng minh định lý 3 : www.themegallery.com Nhóm I LOGO Các định lý cơ bảnChứng minh định lý 3 : www.themegallery.com Nhóm I LOGO Các định lý cơ bảnChứng minh định lý 3 : www.themegallery.com Nhóm I LOGO Định lý Fermat nhỏPhát biểu định lý :Chứng minh định lý : www.themegallery.com Nhóm I LOGO Định lý Fermat nhỏ* Chứng minh định lý : ...