Chứng minh định lý fermat nhỏ

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ọ đặt
Chú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 7

1. 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 facebook

Phép nhân thời trang bị đá

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 cùng một việc xếp hình

James vẽ hình

Câu hỏi của James

Hình vuông số chính phương kỳ diệu của Vianney!

Câu đố mẹo về đo lường

Công thức lượng giác Gauss mang lại 17-giác đều

Chà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 đều

Dựng nhiều giác gần như 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 với 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 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ừa


Số phức


Số phức

phương pháp Moivre


Lượng giác


Công thức lượng giác mang lại góc bội

Công thức lượng giác Gauss đến 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 việc về số nguyên tố

Định lý Wilson

Bộ số Pitago

Modulo cho số hữu tỷ

Modulo đến 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 iq về đo lường

Dựng đa giác hầu như 15 cạnh

Bò đi bé bọ cạp!

Liên phân số Fibonacci

Hằng đẳng thức Pitago

Hình vuông số vi diệu của Euler


Tổ hợp


Bài toán liên kết facebook

Dã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 Pascal


Hì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 II


Dựng hình


Dựng hình bởi thước cùng compa

Bà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ẳng


Giải tích


Ngày số Pi 2015

Chuỗi TaylorTổng nghịch hòn đả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 tài khoản google

Cá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 blog
Xin 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.