Home / Tin Tức / chứng minh định lý fermat nhỏ Chứng minh định lý fermat nhỏ 21/03/2022 Hôm nay chúng ta sẽ cùng nhau học về Định lý Fermat "nhỏ".Chúng ta sẽ thấy rằng định lý nhỏ tuổi Fermat cực kì tiện dụngtrong lúc làm các phép giám sát và đo lường modulo.Định lý này phát biểu như sau.Với rất nhiều số nguyên tố $p$ và với tất cả số nguyên $a$ không phân chia hết mang đến $p$ thìVí dụ:Với $p=7$ cùng $a=3$, $$3^6 = 1 pmod7$$Với $p=13$ cùng $a=2014$, $$2014^12 = 1 pmod13$$Với $p=29$ cùng $a=15$, $$15^28 = 1 pmod29$$Giả sử như bọn họ cần search $3^n = ~?~ pmod7$, trong những số đó $n$ là 1 con số phệ nào đó.Làm sao bạn có thể làm được?Để tính $3^n pmod7$ mang đến một số lượng lớn $n$, bọn họ lấy $n$ rồi phân tách nó mang đến 6.Giả sử như họ được tác dụng $n = 6k+r$, trong những số ấy số dư $r=0,1,2,3,4,5$, bởi vậy thìVậy bằng cách sử dụng định lý nhỏ dại Fermat, bọn họ đã giản mong một số lượng lớn $3^n$ thànhmột con số nhỏ dại $3^r pmod7$.Bạn đang xem: Chứng minh định lý fermat nhỏVí dụ: tìm $3^2012$ modulo $7$. Bọn họ lấy $2012$ rồi phân tách nó mang đến $6$, bọn họ có $2012 = 6 imes 335 + 2$, vậy thìBây giờ họ cùng nhau minh chứng Định lý nhỏ tuổi Fermat. Trước tiên để cho dễ hiểu chúng ta chứng minh mang lại trường hợpđặc biệt là $3^6 = 1 pmod7$ cùng sau đó họ sẽ chứng minh cho ngôi trường hợp tổng quát là $a^p-1 = 1 pmodp$.$$3^6 imes 1 imes 2 imes 3 imes 4 imes 5 imes 6 = 1 imes 2 imes 3 imes 4 imes 5 imes 6 pmod7$$Đẳng thức này có nghĩa là gì? tức là số $(3^6 -1) imes 1 imes 2 imes 3 imes 4 imes 5 imes 6$cho hết cho 7. Bọn họ suy ra số $3^6 -1$ cũng phân chia hết mang đến 7. Có nghĩa là $3^6 = 1 pmod7$.Vậy họ đã bệnh minh hoàn thành Định lý nhỏ dại Fermat mang đến trường thích hợp $p=7$ và $a=3$.Chứng minh cho trường hợp bao quát cũng hệt nhau như nạm này.Chứng minh Định lý nhỏ dại Fermat.Giả sử rằng $p$ là số nguyên tố với $a$ không chia hết mang đến $p$. Coi xét những con số sau:$a$, $2a$, $3a$, $dots$, $(p-1)a$. Bọn họ đặtChúng ta dìm xét nhì điều.Điều sản phẩm công nghệ nhất, sẽ là $r_i eq 0$. Nguyên nhân vậy?Đó là do nếu $r_i=0$ thì $ia = r_i = 0 pmodp$.Cái này không thể nào xảy ra vì $a$ cùng $i$ không chia hết mang lại số nhân tố $p$.Điều nhấn xét thiết bị hai là những số $r_1, r_2, r_3, dots, r_p-1$ phải hoàn toàn khác nhau. Bởi vì sao vậy?Nếu $r_i = r_j$ thì điều gì đã xảy ra? nếu $r_i = r_j$ thì $ia = r_i = r_j = ja pmodp$, và bởi vậy$(i-j)a = 0 pmodp$. Tính năng này cũng không thể xảy ra vì $a$ cùng $i-j$ rất nhiều không chia hết cho số yếu tắc $p$.Xem thêm: Như vậy họ có $p-1$ con số $r_1, r_2, r_3, dots, r_p-1$, toàn bộ chúng đều khác nhau và bên trong khoảng$<1,p-1>$. Vậy thì $p-1$ con số này $r_1, r_2, r_3, dots, r_p-1$ phải là 1 hoán vị của $p-1$ con số$1,2,3, dots, p-1$. Vì đó$$r_1 imes r_2 imes r_3 imes dots imes r_p-1 = 1 imes 2 imes 3 imes dots imes (p-1) .$$$$a^p-1 imes 1 imes 2 imes dots imes (p-1) = r_1 imes r_2 imes dots imes r_p-1 = 1 imes 2 imes dots imes (p-1) pmodp$$Một hệ trái của Định lý bé dại Fermat là như sau.Bởi do $a^p-1 = 1 pmodp$, cho nên nếu $x$ là số dương nhỏ tuổi nhất sao để cho $a^x = 1 pmodp$ thì $x$ bắt buộc phải làmột ước số của $p-1$. Chẳng hạn như trong trường đúng theo $p=7$, theo Định lý nhỏ dại Fermat thìVới $a=1$ thì $x=1$ $$1^1 = 1 pmod7$$Với $a=2$ thì $x=3$ $$2^1 = 2, ~2^2 = 4, ~2^3 = 8 = 1 pmod7$$Với $a=3$ thì $x=6$ $$3^1 = 3, ~3^2 = 9 = 2, ~3^3 = 6, ~3^4 = 18 = 4, ~3^5 = 12 = 5, ~3^6 = 15 = 1 pmod7$$Với $a=4$ thì $x=3$ $$4^1 = 4, ~4^2 = 16 = 2, ~4^3 = 8 = 1 pmod7$$Với $a=5$ thì $x=6$ $$5^1 = 5, ~5^2 = 25 = 4, ~5^3 = 20 = 6, ~5^4 = 30 = 2, ~5^5 = 10 = 3, ~5^6 = 15 = 1 pmod7$$Với $a=6$ thì $x=2$ $$6^1 = 6, ~6^2 = 36 = 1 pmod7$$Chúng ta thấy rằng sống mỗi ngôi trường hợp, $1^1 = 2^3 = 3^6 = 4^3 = 5^6 = 6^2 = 1 pmod7$, số mũ $x = 1, 3, 6, 3, 6, 2$ đềulà mong số của $p-1=6$. Hình bên dưới đây diễn tả sự tuần trả của $a^n$ modulo 7.sự tuần trả của $a^n$ modulo 71. Chứng minh rằng $2011^2011^2011 + 2012^2012^2012 + 2013^2013^2013 + 2014^2014^2014$ phân chia hết mang đến 11.2. Mang đến $p$ là một trong những nguyên tố với $a$ là số không phân chia hết mang lại $p$. Gọi $x$ là số nguyên dương nhỏ dại nhất sao cho$a^x = 1 pmodp$. Chứng tỏ rằng $x$ là một trong những ước số của $p-1$.3. Thứu tự tính $2^n pmod11$ đến $n=0,1,2,3,dots$ rồi phát biểu tính tuần hoàn của $2^n$ modulo $11$.Làm giống như cho $3^n$, $4^n, dots, 10^n$ modulo $11$.Labels:bội số,chia hết,đại số,định lý Fẹcma,định lý Wilson,Fẹcma,modulo,số học,số nguyên,số nguyên tố,số trường đoản cú nhiên,tổng bình phương,ước số ► 2017(1) ► 2016(7) ► 2015(12) ► 2014(12) ► 2013(26) ▼ 2012(36) ▼ tháng sáu(6) ► 2011(7)Bài toán kết nối facebookPhép nhân thời trang bị đáMắt Biếc hồ nước ThuLục giác kỳ diệuĐịnh lý Pitago1 = 2012 = 2013Dãy số Fibonacci cùng một việc xếp hìnhJames vẽ hìnhCâu hỏi của JamesHình vuông số chính phương kỳ diệu của Vianney!Câu đố mẹo về đo lườngCông thức lượng giác Gauss mang lại 17-giác đềuChào năm mới tết đến 2014 Chào năm mới tết đến 2015 Chào năm mới tết đến 2016 Không gian 4d là gì?Dựng hình đa giác đềuDựng nhiều giác gần như 15 cạnhNgày số Pi (2015)Ngày số Pi (2016)0.9999999... Có bằng 1 không? (2015)Hình tam giácBàn cờ vua với kim từ bỏ thápDãy sốDãy số - Phần 1Dãy số - Phần 2Dãy số - Phần 3Dãy số - Phần 4Dãy số - Phần 5Dãy số - Phần 6Dãy số - Phần 7Dãy số - Phần 8Dãy số - Phần 9Đại sốTam giác PascalQuy nạpQuy nạp IIQuy nạp IIINhị thức Newton1 = 2012 = 2013Đa thức nội suy NewtonĐa thức nội suy LagrangeChứng minh Định lý Wilson bởi công thức nội suyTổng luỹ thừaSố phứcSố phức phương pháp MoivreLượng giácCông thức lượng giác mang lại góc bộiCông thức lượng giác Gauss đến 17-giác đềuNgày số Pi (2016)Radian là gì?Số họcmodulo - Phần 1modulo - Phần 2modulo - Phần 3modulo - Phần 4modulo - Phần 5modulo - Phần 6Số nguyên tốĐịnh lý Euclid về số nguyên tốMột vài việc về số nguyên tốĐịnh lý WilsonBộ số PitagoModulo cho số hữu tỷModulo đến số hữu tỷ IIChứng minh lại định lý WilsonBổ đề BezoutThuật toán EuclidTổng luỹ thừaTổng luỹ thừa và định lý WolstenholmeCâu iq về đo lườngDựng đa giác hầu như 15 cạnhBò đi bé bọ cạp!Liên phân số FibonacciHằng đẳng thức PitagoHình vuông số vi diệu của EulerTổ hợpBài toán liên kết facebookDãy số Fibonacci và một việc xếp hìnhHằng đẳng thức về hàng số FibonacciDãy số Fibonacci và tam giác PascalHình họcĐịnh lý PitagoĐịnh lý con đường cao tam giác vuôngĐịnh lý MorleyPhương tíchTrục đẳng phương và vai trung phong đẳng phươngĐịnh lý Ceva với Định lý MenelausLục giác kỳ diệuĐịnh lý PascalĐịnh lý PappusCánh bướm PascalBài toán nhỏ bướmĐịnh lý ngôi sao Do TháiHãy xem xét trường hợp đặc biệtBài toán về tìm khoảng cách ngắn nhất cùng một đặc điểm của hình elípĐiểm Fermat của hình tam giácĐiểm Fermat của hình tam giác IIDựng hìnhDựng hình bởi thước cùng compaBài toán phân chia hình tứ giácDựng hình ngũ giác đềuDựng hình đa giác đềuDựng đa giác mọi 15 cạnhĐịnh lý đường cao tam giác vuôngThuật toán dựng hìnhCông thức lượng giác Gauss mang lại 17-giác mọi Dựng hình chỉ bằng compa cần sử dụng compa chia hồ hết đoạn thẳngGiải tíchNgày số Pi 2015Chuỗi TaylorTổng nghịch hòn đảo bình phươngGiúp bé bỏng thông minhXì-tin năng độngTạp chí toán họcKỹ năng mềmTạo lập tài khoản googleCách chế tác blog toán họcHọc toán bên trên WolframDịch tài liệu toán họcViết văn bạn dạng toán học PDF trực tuyến bởi LaTeXChia té tài liệu toán học tập trên Google Drive© vườn cửa Toán blogXin lưu giữ ý: Nếu bạn có nhu cầu sao chép và thông dụng lại những nội dung bài viết trên trang blog này, xin nhớ rằng ghi tên người sáng tác và add nguồn.