Modulo - Phần 5 - Vườn Toán

Trang chủ » Fermat Nhỏ » Modulo - Phần 5 - Vườn Toán

Có thể bạn quan tâm

Trang

  • Trang nhà
  • Kỹ năng mềm
  • Giới thiệu

modulo - Phần 5

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ỏ Fermat rất là tiện dụng trong khi làm các phép tính toán modulo. Định lý này phát biểu như sau. Với mọi số nguyên tố $p$ và với mọi số nguyên $a$ không chia hết cho $p$ thì $$ a^{p-1} = 1 \pmod{p} . $$ Ví dụ:
  • Với $p=7$ và $a=3$, $$3^6 = 1 \pmod{7}$$
  • Với $p=13$ và $a=2014$, $$2014^{12} = 1 \pmod{13}$$
  • Với $p=29$ và $a=15$, $$15^{28} = 1 \pmod{29}$$
Giả sử như chúng ta cần tìm $3^{n} = ~?~ \pmod{7}$, trong đó $n$ là một con số lớn nào đó. Làm sao chúng ta có thể làm được? The Định lý nhỏ Fermat, chúng ta biết rằng $$3^6 = 1 \pmod{7} .$$ Để tính $3^n \pmod{7}$ cho một con số lớn $n$, chúng ta lấy $n$ rồi chia nó cho 6. Giả sử như chúng ta được kết quả $n = 6k+r$, trong đó số dư $r=0,1,2,3,4,5$, như vậy thì $$3^{n} = 3^{6k+r} = (3^6)^k \times 3^r = 1^k \times 3^r = 3^r \pmod{7}$$ Vậy bằng cách sử dụng định lý nhỏ Fermat, chúng ta đã giản ước một con số lớn $3^{n}$ thành một con số nhỏ $3^r \pmod{7}$. Ví dụ: Tìm $3^{2012}$ modulo $7$. Chúng ta lấy $2012$ rồi chia nó cho $6$, chúng ta có $2012 = 6 \times 335 + 2$, vậy thì $$ 3^{2012} = 3^{6 \times 335 + 2} = (3^6)^{335} \times 3^2 = 1^{335} \times 3^2 \pmod{7}$$ Vì vậy, $3^{2012} = 3^2 = 9 = 2 \pmod{7}$. Bây giờ chúng ta cùng nhau chứng minh Định lý nhỏ Fermat. Trước tiên để cho dễ hiểu chúng ta chứng minh cho trường hợp đặc biệt là $3^6 = 1 \pmod{7}$ và sau đó chúng ta sẽ chứng minh cho trường hợp tổng quát là $a^{p-1} = 1 \pmod{p}$. Chúng ta thấy rằng $$3 \times 1 = 3 \pmod{7}$$ $$3 \times 2 = 6 \pmod{7}$$ $$3 \times 3 = 2 \pmod{7}$$ $$3 \times 4 = 5 \pmod{7}$$ $$3 \times 5 = 1 \pmod{7}$$ $$3 \times 6 = 4 \pmod{7}$$ Nhân các đẳng thức này lại với nhau, chúng ta có $$3^6 \times 1 \times 2 \times 3 \times 4 \times 5 \times 6 = 1 \times 2 \times 3 \times 4 \times 5 \times 6 \pmod{7}$$ Vì vậy nên $$(3^6 -1) \times 1 \times 2 \times 3 \times 4 \times 5 \times 6 = 0 \pmod{7}$$ Đẳng thức này có nghĩa là gì? Có nghĩa là số $(3^6 -1) \times 1 \times 2 \times 3 \times 4 \times 5 \times 6$ cho hết cho 7. Chúng ta suy ra số $3^6 -1$ cũng chia hết cho 7. Tức là $3^6 = 1 \pmod{7}$. Vậy chúng ta đã chứng minh xong Định lý nhỏ Fermat cho trường hợp $p=7$ và $a=3$. Chứng minh cho trường hợp tổng quát cũng giống hệt như thế này. Chứng minh Định lý nhỏ Fermat. Giả sử rằng $p$ là số nguyên tố và $a$ không chia hết cho $p$. Xem xét các con số sau: $a$, $2a$, $3a$, $\dots$, $(p-1)a$. Chúng ta đặt $$a = r_1 \pmod{p}$$ $$2a = r_2 \pmod{p}$$ $$3a = r_3 \pmod{p}$$ $$\dots$$ $$(p-1)a = r_{p-1} \pmod{p}$$ trong đó $r_1, r_2, r_3, \dots, r_{p-1}$ là các số nằm trong khoảng $[0,p-1]$. Chúng ta nhận xét hai điều. Điều thứ nhất, đó là $r_i \neq 0$. Tại sao vậy? Đó là vì nếu $r_i=0$ thì $ia = r_i = 0 \pmod{p}$. Cái này không thể nào xảy ra vì $a$ và $i$ không chia hết cho số nguyên tố $p$. Điều nhận xét thứ hai là các số $r_1, r_2, r_3, \dots, r_{p-1}$ phải hoàn toàn khác nhau. Vì sao vậy? Nếu $r_i = r_j$ thì điều gì sẽ xảy ra? Nếu $r_i = r_j$ thì $ia = r_i = r_j = ja \pmod{p}$, và vì vậy $(i-j)a = 0 \pmod{p}$. Cái này cũng không thể xảy ra vì $a$ và $i-j$ đều không chia hết cho số nguyên tố $p$. Như vậy chúng ta có $p-1$ con số $r_1, r_2, r_3, \dots, r_{p-1}$, tất cả chúng đều khác nhau và nằm 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 hoán vị của $p-1$ con số $1,2,3, \dots, p-1$. Do đó $$r_1 \times r_2 \times r_3 \times \dots \times r_{p-1} = 1 \times 2 \times 3 \times \dots \times (p-1) .$$ Nhân các đẳng thức dưới đây lại với nhau $$a = r_1 \pmod{p}$$ $$2a = r_2 \pmod{p}$$ $$3a = r_3 \pmod{p}$$ $$\dots$$ $$(p-1)a = r_{p-1} \pmod{p}$$ chúng ta có $$a^{p-1} \times 1 \times 2 \times \dots \times (p-1) = r_1 \times r_2 \times \dots \times r_{p-1} = 1 \times 2 \times \dots \times (p-1) \pmod{p}$$ Vì vậy, $$(a^{p-1} - 1) \times 1 \times 2 \times \dots \times (p-1) = 0 \pmod{p},$$ và do đó $$a^{p-1} - 1 = 0 \pmod{p} .$$ Vậy, chúng ta đã chứng minh xong Định lý nhỏ Fermat rằng $a^{p-1} = 1 \pmod{p}. \blacksquare$ Một hệ quả của Định lý nhỏ Fermat là như sau. Bởi vì $a^{p-1} = 1 \pmod{p}$, cho nên nếu $x$ là số dương nhỏ nhất sao cho $a^x = 1 \pmod{p}$ 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 hợp $p=7$, theo Định lý nhỏ Fermat thì $$1^6=2^6=3^6=4^6=5^6=6^6 = 1 \pmod{7},$$ số dương nhỏ nhất $x$ để cho $a^x = 1 \pmod{7}$ được liệt kê dưới đây
  • Với $a=1$ thì $x=1$ $$1^1 = 1 \pmod{7}$$
  • Với $a=2$ thì $x=3$ $$2^1 = 2, ~2^2 = 4, ~2^3 = 8 = 1 \pmod{7}$$
  • 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 \pmod{7}$$
  • Với $a=4$ thì $x=3$ $$4^1 = 4, ~4^2 = 16 = 2, ~4^3 = 8 = 1 \pmod{7}$$
  • 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 \pmod{7}$$
  • Với $a=6$ thì $x=2$ $$6^1 = 6, ~6^2 = 36 = 1 \pmod{7}$$
Chúng ta thấy rằng ở mỗi trường hợp, $1^1 = 2^3 = 3^6 = 4^3 = 5^6 = 6^2 = 1 \pmod{7}$, số mũ $x = 1, 3, 6, 3, 6, 2$ đều là ước số của $p-1=6$. Hình dưới đây miêu tả sự tuần hoàn của $a^n$ modulo 7.
sự tuần hoàn của $a^n$ modulo 7
Xin hẹn gặp lại các bạn ở kỳ cuối tại "modulo - Phần 6". Bài tập về nhà. 1. Chứng minh rằng $2011^{2011^{2011}} + 2012^{2012^{2012}} + 2013^{2013^{2013}} + 2014^{2014^{2014}}$ chia hết cho 11. 2. Cho $p$ là một số nguyên tố và $a$ là số không chia hết cho $p$. Gọi $x$ là số nguyên dương nhỏ nhất sao cho $a^x = 1 \pmod{p}$. Chứng minh rằng $x$ là một ước số của $p-1$. 3. Lần lượt tính $2^n \pmod{11}$ cho $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 tương tự 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ố tự nhiên, tổng bình phương, ước số Bài đăng Mới hơn Bài đăng Cũ hơn Trang chủ

Ủng hộ Vườn Toán trên facebook

Facebook

Lưu trữ Blog

  • ▼  2012 (36)
    • ▼  tháng 6 (6)
      • modulo - Phần 6
      • modulo - Phần 5
      • modulo - Phần 4
      • modulo - Phần 3
      • modulo - Phần 2
      • modulo - Phần 1

English Version

English Version

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

Phép nhân thời đồ đá

Mắt Biếc Hồ Thu

Lục giác kỳ diệu

Định lý Pitago

1 = 2012 = 2013

Dãy số Fibonacci và một bài toán 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 cho 17-giác đều

Chào năm mới 2014

Chào năm mới 2015

Chào năm mới 2016

Không gian 4 chiều là gì?

Dựng hình đa giác đều

Dựng đa giác đều 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à kim tự tháp

Dãy số

Dãy số - Phần 1

Dãy số - Phần 2

Dãy số - Phần 3

Dãy số - Phần 4

Dãy số - Phần 5

Dãy số - Phần 6

Dãy số - Phần 7

Dãy số - Phần 8

Dãy số - Phần 9

Đại số

Tam giác Pascal

Quy nạp

Quy nạp II

Quy nạp III

Nhị thức Newton

1 = 2012 = 2013

Đa thức nội suy Newton

Đa thức nội suy Lagrange

Chứng minh Định lý Wilson bằng công thức nội suy

Tổ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 bài toán về số nguyên tố

Định lý Wilson

Bộ số Pitago

Modulo cho số hữu tỷ

Modulo cho 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 đố mẹo về đo lường

Dựng đa giác đều 15 cạnh

Bò đi con 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 bài toán xếp hình

Hằng đẳng thức về dãy số Fibonacci

Dãy số Fibonacci và tam giác Pascal

Hình học

Định lý Pitago

Định lý đường cao tam giác vuông

Định lý Morley

Phương tích

Trục đẳng phương và tâm đẳng phương

Định lý Ceva và Định lý Menelaus

Lục giác kỳ diệu

Định lý Pascal

Định lý Pappus

Cánh bướm Pascal

Bài toán con bướm

Định lý Ngôi Sao Do Thái

Hãy xem xét trường hợp đặc biệt

Bài toán về tìm khoảng cách ngắn nhất và một tính chất 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 và compa

Bài toán chia hình tứ giác

Dựng hình ngũ giác đều

Dựng hình đa giác đều

Dựng đa giác đều 15 cạnh

Định lý đường cao tam giác vuông

Thuật toán dựng hình

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

Dựng hình chỉ bằng compa

Dùng compa chia đều đoạn thẳng

Giải tích

Ngày số Pi 2015

Chuỗi Taylor

Tổng nghịch đảo bình phương

Giúp bé thông minh

Xì-tin năng động

BBC - Học tiếng Anh Du học Hoa kỳ Học Bổng Hoa Kỳ VOA - Học tiếng Anh

Tạp chí toán học

Kỹ năng mềm

Tạo lập tài khoản google

Cách tạo blog toán học

Học toán trên Wolfram

Dịch tài liệu toán học

Viết văn bản toán học PDF trực tuyến bằng LaTeX

Chia xẻ tài liệu toán học trên Google Drive

Từ khóa » Fermat Nhỏ