Ánh xạ và số nguyên

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=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 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ố. Nhóm I Các định lý cơ bản Phá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ất thành tích của một số số nguyên tố theo dạng : n = Nhóm I Các định lý cơ bản Chứng minh định lý 3 : Nhóm I Các định lý cơ bản Chứng minh định lý 3 : Nhóm I Các định lý cơ bản Chứng minh định lý 3 : Nhóm I Định lý Fermat nhỏ Phát biểu định lý : Chứng minh định lý : Nhóm I Định lý Fermat nhỏ * Chứng minh định lý : Nhóm I Định lý Euler Phát biểu định lý : Nhóm I Định lý Euler Phát biểu định lý Nhóm I Định lý Euler Ví dụ : Nhóm I Định lý Euler Phát biểu định lý : Chứng minh định lý : Nhóm I Định lý Euler Chứng minh định lý : Nhóm I Ứng dụng vào bảo mật Phát biểu hệ quả : Nhóm I Ứng dụng vào bảo mật Ứng dụng : Nhóm I Ứng dụng vào bảo mật Ví dụ : Nhóm I Ứng dụng vào bảo mật Ví dụ : Nhóm I Ứng dụng vào bảo mật Hệ quả : Nhóm I Ứng dụng vào bảo mật Ứng dụng : Nhóm I Tiếp tục Ostoren