tailieunhanh - Á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 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=). Nếu p là số nguyên tố, bài toán coi như đã xong. Nếu p không. | Nội dung Ánh xạ 1 Số nguyên – đồng dư thức 2 Số nguyên tố 3 Hệ g- phân 4 Nhóm I 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 Nhóm I Ứng dụng vào bảo mật 5 Định lý Bezout Phá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. Nhóm I Định lý Bezout Chứ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 ) 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) Nhóm I Suy ra : rn th(rn-2 , rn-3) Đị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. Nhóm I Đị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. Nhóm I 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=). 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 = (hay a= ). a có 2 ước số m,n 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. Nhóm I Định lý Bezout Chứ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 ) 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) Nhóm I Suy ra : rn th(rn-2 , rn-3) Định lý Bezout Chứng minh : b) (a,b) = 1 suy ra tồn tại x,y Z / ax + by = (a,b) = 1 .