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

     
Hôm nay chúng ta sẽ với mọi người trong nhà học về Định lý Fermat "nhỏ".Chúng ta đã thấy rằng định lý bé dại Fermat rất là tiện dụngtrong lúc làm những phép giám sát modulo.Định lý này tuyên bố như sau.Với phần đa số nhân tố $p$ và với tất cả số nguyên $a$ không phân chia hết cho $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ư họ cần search $3^n = ~?~ pmod7$, trong các số đó $n$ là 1 con số lớn nào đó.Làm sao bạn có thể làm được?
Để tính $3^n pmod7$ mang lại một số lượng lớn $n$, bọn họ lấy $n$ rồi chia nó đến 6.Giả sử như bọn họ được kết quả $n = 6k+r$, trong những số đó số dư $r=0,1,2,3,4,5$, như vậy thì
Vậy bằng cách sử dụng định lý nhỏ tuổi Fermat, họ đã giản mong một con số 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 kiếm $3^2012$ modulo $7$. Bọn họ lấy $2012$ rồi phân tách nó mang đến $6$, chúng ta có $2012 = 6 imes 335 + 2$, vậy thì
Bây giờ chúng ta cùng nhau minh chứng Định lý nhỏ dại Fermat. Trước tiên để cho dễ hiểu chúng ta chứng minh mang đến trường hợpđặc biệt là $3^6 = 1 pmod7$ với sau đó bọn họ sẽ chứng tỏ 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 tức 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 lại 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 bọn họ đã chứng minh ngừng Định lý nhỏ Fermat mang đến trường đúng theo $p=7$ và $a=3$.Chứng minh cho trường hợp bao quát cũng giống hệt như cầm này.
Chứng minh Định lý bé dại Fermat.Giả sử rằng $p$ là số nguyên tố cùng $a$ không phân tách hết cho $p$. Coi xét các con số sau:$a$, $2a$, $3a$, $dots$, $(p-1)a$. Bọn họ đặt
Chúng ta dấn xét nhì điều.Điều trang bị nhất
, sẽ là $r_i eq 0$. Nguyên nhân vậy?Đó bởi vì 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 $i$ không chia hết mang đến số thành phần $p$.
Điều nhấn xét vật dụng hai là các số $r_1, r_2, r_3, dots, r_p-1$ phải trọn vẹn khác nhau. Vì sao vậy?Nếu $r_i = r_j$ thì điều gì đã xảy ra? giả dụ $r_i = r_j$ thì $ia = r_i = r_j = ja pmodp$, và vày vậy$(i-j)a = 0 pmodp$. Tính năng này cũng ko thể xẩy ra vì $a$ cùng $i-j$ phần đông không chia hết mang lại số yếu tắc $p$.

Xem thêm: Hồi Ức Cái Giá Của Tội Ác - Phim Cái Giá Của Tội Ác (Htv2) (20 Tập)


Như vậy chúng ta có $p-1$ con số $r_1, r_2, r_3, dots, r_p-1$, toàn bộ chúng đều không giống nhau và nằm trong khoảng$<1,p-1>$. Vậy thì $p-1$ số lượng này $r_1, r_2, r_3, dots, r_p-1$ phải là 1 trong những hoán vị của $p-1$ con số$1,2,3, dots, p-1$. Bởi 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ý nhỏ Fermat là như sau.Bởi vì chưng $a^p-1 = 1 pmodp$, vì vậy nếu $x$ là số dương bé dại nhất thế nào cho $a^x = 1 pmodp$ thì $x$ sẽ phải làmột mong số của $p-1$. Chẳng hạn như trong trường đúng theo $p=7$, theo Định lý bé 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 làm việc mỗ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 dưới đây diễn tả sự tuần hoàn của $a^n$ modulo 7.
*
sự tuần trả của $a^n$ modulo 7

1. Chứng tỏ rằng $2011^2011^2011 + 2012^2012^2012 + 2013^2013^2013 + 2014^2014^2014$ phân tách hết đến 11.
2. Cho $p$ là một vài nguyên tố cùng $a$ là số không chia hết đến $p$. điện thoại tư vấn $x$ là số nguyên dương nhỏ nhất sao cho$a^x = 1 pmodp$. Minh chứng rằng $x$ là 1 trong những ước số của $p-1$.
3. Lần lượt tính $2^n pmod11$ cho $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 giống như cho $3^n$, $4^n, dots, 10^n$ modulo $11$.

Xem thêm: So Sánh Bội Số (So Sánh Gấp 3 Lần Tiếng Anh Như Thế Nào? Gấp 3 Lần In English


*

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ố tự 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 liên kết 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à 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ủ yếu phương kỳ lạ của Vianney!

Câu iq về đo lường

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

Định lý Wilson

Bộ số Pitago

Modulo mang lại 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ới định lý Wolstenholme

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

Dựng đa giác phần đông 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ố kỳ diệu của Euler


Tổ hợp


Bài toán kết nối facebook

Dãy số Fibonacci và một câu hỏi 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ý con đường cao tam giác vuôngĐịnh lý MorleyPhương tíchTrục đẳng phương và trọng điể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 5 cánh Do TháiHãy lưu ý trường hợp quánh biệtBài toán về tìm khoảng cách ngắn nhất với 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ằng thước cùng compa

Bài toán phân tách hình tứ giácDựng hình ngũ giác đềuDựng hình đa giác đềuDựng nhiều giác gần như 15 cạnhĐịnh lý mặt đường cao tam giác vuôngThuật toán dựng hìnhCông thức lượng giác Gauss mang đến 17-giác rất nhiều Dựng hình chỉ bởi compa dùng compa chia những đ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 nhỏ bé 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 tạo thành blog toán họcHọc toán bên trên WolframDịch tư liệu toán họcViết văn phiên bản toán học tập PDF trực tuyến bởi LaTeXChia bổ tài liệu toán học trên Google Drive


© vườn Toán blog
Xin lưu giữ ý: Nếu bạn muốn sao chép và thịnh hành lại những nội dung bài viết trên trang blog này, xin hãy nhớ là ghi tên tác giả và địa chỉ cửa hàng nguồn.