Ví dụ:Với $p=7$ và $a=3$, $$3^6 = 1 pmod7$$Với $p=13$ với $a=2014$, $$2014^12 = 1 pmod13$$Với $p=29$ và $a=15$, $$15^28 = 1 pmod29$$
Giả sử như họ cần tìm kiếm $3^n = ~?~ pmod7$, trong các số ấy $n$ là 1 trong những con số to nào đó.Làm sao chúng ta cũng có thể làm được?
Để tính $3^n pmod7$ mang đến một số lượng lớn $n$, chúng ta lấy $n$ rồi phân tách nó mang đến 6.Giả sử như bọn họ được kết quả $n = 6k+r$, trong những số ấy số dư $r=0,1,2,3,4,5$, do vậy thì
Vậy bằng phương pháp sử dụng định lý nhỏ Fermat, chúng ta đã giản cầu một con số lớn $3^n$ thànhmột bé số nhỏ $3^r pmod7$.
Bạn đang xem: Chứng minh định lý fermat nhỏ
Ví dụ: kiếm tìm $3^2012$ modulo $7$. Họ lấy $2012$ rồi phân tách nó mang lại $6$, bọn họ có $2012 = 6 imes 335 + 2$, vậy thì
Bây giờ chúng ta cùng nhau chứng tỏ Định lý nhỏ dại Fermat. Trước tiên khiến cho dễ hiểu chúng ta chứng minh đến trường hợpđặc biệt là $3^6 = 1 pmod7$ và sau đó bọn họ sẽ minh chứng cho ngôi trường hợp tổng thể 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ì? có nghĩa là số $(3^6 -1) imes 1 imes 2 imes 3 imes 4 imes 5 imes 6$cho hết mang đến 7. 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 chúng ta đã bệnh minh ngừng Định lý bé dại Fermat mang lại trường vừa lòng $p=7$ và $a=3$.Chứng minh mang đến trường hợp tổng quát cũng tương đồng như cố kỉnh này.
Chứng minh Định lý bé dại Fermat.Giả sử rằng $p$ là số nguyên tố và $a$ không phân tách hết mang đến $p$. Xem xét các con số sau:$a$, $2a$, $3a$, $dots$, $(p-1)a$. Chúng ta đặt
Chúng ta nhấn xét nhì điều.Điều trang bị nhất, đó là $r_i eq 0$. Tại sao vậy?Đó nguyên nhân là nếu $r_i=0$ thì $ia = r_i = 0 pmodp$.Cái này sẽ không thể nào xẩy ra vì $a$ và $i$ không phân tách hết mang đến số nhân tố $p$.
Điều thừa nhận xét sản phẩm hai là những số $r_1, r_2, r_3, dots, r_p-1$ phải hoàn toàn khác nhau. Vì chưng 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à vị vậy$(i-j)a = 0 pmodp$. Cái này cũng không thể xẩy ra vì $a$ và $i-j$ những không phân chia hết mang lại số nhân tố $p$.
Xem thêm: 10397 Em Nói Thật Nhé, Học Phí Trường Nguyễn Khuyến Tphcm Là Bao Nhiêu? ?
Như vậy chúng ta có $p-1$ số lượng $r_1, r_2, r_3, dots, r_p-1$, tất cả chúng đều khác biệt 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à một trong những hoán vị của $p-1$ nhỏ số$1,2,3, dots, p-1$. Vày đó
$$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ý nhỏ tuổi Fermat là như sau.Bởi vì chưng $a^p-1 = 1 pmodp$, do đó nếu $x$ là số dương nhỏ dại nhất sao cho $a^x = 1 pmodp$ thì $x$ cần phải làmột mong số của $p-1$. Ví dụ như trong trường đúng theo $p=7$, theo Định lý nhỏ 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 = trăng tròn = 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 sinh sống mỗi trường hợp, $1^1 = 2^3 = 3^6 = 4^3 = 5^6 = 6^2 = 1 pmod7$, số nón $x = 1, 3, 6, 3, 6, 2$ đềulà ước số của $p-1=6$. Hình dưới đây biểu đạt sự tuần hoàn của $a^n$ modulo 7.
 |
| sự tuần hoàn của $a^n$ modulo 7 |
1. Minh chứng rằng $2011^2011^2011 + 2012^2012^2012 + 2013^2013^2013 + 2014^2014^2014$ phân tách hết mang lại 11.
2. đến $p$ là một vài nguyên tố với $a$ là số không phân tách hết mang lại $p$. Hotline $x$ là số nguyên dương nhỏ tuổi nhất sao cho$a^x = 1 pmodp$. Chứng minh rằng $x$ là một trong những ước số của $p-1$.
3. Theo lần lượt tính $2^n pmod11$ mang đến $n=0,1,2,3,dots$ rồi phát biểu tính tuần trả của $2^n$ modulo $11$.Làm tương tự 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) ▼ mon sáu(6) ► 2011(7)
Bài toán kết nối facebook
Phép nhân thời đồ dùng đá
Mắt Biếc hồ nước Thu
Lục giác kỳ diệu
Định lý Pitago
1 = 2012 = 2013
Dãy số Fibonacci với một vấn đề xếp hình
James vẽ hình
Câu hỏi của James
Hình vuông số bao gồm phương vi diệu của Vianney!
Câu đố vui về đo lường
Công thức lượng giác Gauss mang đến 17-giác đều
Chào năm mới 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 đều
Dựng nhiều giác hồ hết 15 cạnh
Ngày số Pi (2015)
Ngày số Pi (2016)
0.9999999... Có bằng 1 không? (2015)
Hình tam giác
Bàn cờ vua cùng kim từ bỏ tháp
Dãy số
Dãy số - Phần 1
Dã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 Pascal
Quy nạpQuy hấp thụ IIQuy hấp thụ 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ừa
Số phức
Số phức
công thức Moivre
Lượng giác
Công thức lượng giác cho góc bội
Công thức lượng giác Gauss cho 17-giác đều
Ngày số Pi (2016)
Radian là gì?
Số học
modulo - Phần 1
modulo - Phần 2
modulo - Phần 3
modulo - Phần 4
modulo - Phần 5
modulo - Phần 6
Số nguyên tố
Định lý Euclid về số nguyên tố
Một vài vấn đề về số nguyên tố
Định lý Wilson
Bộ số Pitago
Modulo cho số hữu tỷ
Modulo mang lại số hữu tỷ II
Chứng minh lại định lý Wilson
Bổ đề Bezout
Thuật toán Euclid
Tổng luỹ thừa
Tổng luỹ thừa và định lý Wolstenholme
Câu đố vui về đo lường
Dựng đa giác hầu như 15 cạnh
Bò đi nhỏ bọ cạp!
Liên phân số Fibonacci
Hằng đẳng thức Pitago
Hình vuông số kỳ diệu của Euler
Tổ hợp
Bài toán kết nối facebook
Dãy số Fibonacci với một vấn đề xếp hìnhHằng đẳng thức về hàng số FibonacciDãy số Fibonacci cùng tam giác Pascal
Hình học
Định lý Pitago
Định lý mặt đường cao tam giác vuôngĐịnh lý MorleyPhương tíchTrục đẳng phương và tâm đẳ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 sáng Do TháiHãy lưu ý trường hợp sệt 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 II
Dựng hình
Dựng hình bởi thước cùng compa
Bài toá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 đều 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 đến 17-giác số đông Dựng hình chỉ bởi compa dùng compa chia đa số đoạn thẳng
Giải tích
Ngày số Pi 2015
Chuỗi TaylorTổng nghịch đảo bình phương
Giúp bé bỏng thông minh
Xì-tin năng động
Tạp chí toán học
Kỹ năng mềm
Tạo lập thông tin tài khoản google
Cách chế tạo 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 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 Toán blog
Xin lưu ý: Nếu bạn muốn sao chép và thông dụng lại những bài viết trên trang blog này, xin nhớ là ghi tên người sáng tác và địa chỉ cửa hàng nguồn.
