ทฤษฎีบทเล็กๆ ของแฟร์มาต์เป็นทฤษฎีบทพื้นฐานในทฤษฎีจำนวนเบื้องต้น ซึ่งให้กำลังในการคำนวณของจำนวนเต็มโมดูโลจำนวนเฉพาะ เป็นกรณีเฉพาะของทฤษฎีบทออยเลอร์ และจำเป็นในการใช้งานของทฤษฎีจำนวนเบื้องต้น เช่น การทดสอบเบื้องต้นและการเข้ารหัสคีย์สาธารณะ นี่เรียกว่าทฤษฎีบทเล็กๆ ของแฟร์มาต์
ทฤษฎีบทของแฟร์มาต์เรียกอีกอย่างว่าทฤษฎีบทเล็ก ๆ ของแฟร์มาต์ที่นิยามว่า P เป็นจำนวนเฉพาะและ 'a' เป็นจำนวนเต็มบวกที่ P หารไม่ได้ -
a P-1 ≡ 1 mod P
เงื่อนไขที่สองบอกว่าถ้า P เป็นจำนวนเฉพาะและ a เป็นจำนวนเต็ม แล้ว a P ≡ 1 mod P.
หลักฐาน − Zp คือเซตของจำนวนเต็ม {0, 1…P-1} เมื่อคูณด้วยโมดูโล P ผลลัพธ์จะรวมองค์ประกอบทั้งหมดของ Zp ในบางลำดับ ยิ่งกว่านั้น ax 0 ≡ 0 mod P ดังนั้นหมายเลข (P-1) {a mod P, 2a mod P,…((P-1) a mod P)} เป็นเพียงตัวเลข {1, 2 ,…(P-1)} ตามลำดับค่ะ
การคูณตัวเลขในทั้งสองขั้นตอนและรับผลลัพธ์ mod P ให้
ก x 2 ก x …. x ((P-1)a)=[(ตัวดัดแปลง P) x (2a mod P) x …. x ((P-1) ตัวดัดแปลง P)] ตัวดัดแปลง P
=[1 x 2 x…x (P-1)] mod P
=(P-1)! mod P
แต่
ก x 2a x…x ((P-1)a) =(P-1)!a P-1
(P-1)! a P-1 ≡ (𝑃 − 1)! mod P
a P-1 ≡ 1 mod P
พิจารณาเซตของจำนวนเต็มบวกที่น้อยกว่า p:{1, 2... p1} และคูณแต่ละองค์ประกอบด้วย a, modulo p เพื่อรับเซต X ={a mod p, 2a mod p . . (p1) ตัวดัดแปลง p}. ไม่มีองค์ประกอบของ X ใดที่คล้ายกับศูนย์เพราะ p ไม่หาร a.
นอกจากนี้ จำนวนเต็มสองจำนวนใน X ไม่เหมือนกัน หากต้องการดูสิ่งนี้ ให้พิจารณาว่า (ja ≡ p) โดยที่ 1 ≤ p1 เนื่องจาก p จึงสามารถลบ a ออกจากสมการทั้งสองข้างได้ผลลัพธ์เป็น − j≡ p)
ความคล้ายคลึงสุดท้ายนี้ไม่สามารถเข้าถึงได้เนื่องจาก j และ k เป็นจำนวนเต็มบวกที่น้อยกว่า p ดังนั้นจึงเข้าใจว่าองค์ประกอบ (p1) ของ X เป็นจำนวนเต็มบวกทั้งหมดโดยไม่มีองค์ประกอบสองอย่างเหมือนกัน
ตัวเลข − ทฤษฎีบทของแฟร์มาต์ระบุว่าหาก p เป็นจำนวนเฉพาะและ a เป็นจำนวนเต็มบวกที่หารด้วย P ไม่ได้แล้ว a P−1 ≡ 1(mod p)
ดังนั้น 3 10 ≡ 1(สมัย 11)
ดังนั้น 3 201 =(3 10 ) 20 x 3 ≡ 3 (mod 11)
ทฤษฎีบทเล็ก ๆ ของ Fermats บางครั้งมีประโยชน์สำหรับการค้นหาวิธีแก้ปัญหาสำหรับการยกกำลังบางตัวอย่างรวดเร็ว ตัวอย่างต่อไปนี้แสดงแนวคิด
ตัวอย่างที่ 1 − หาผลลัพธ์ของ 6 10 mod 11
วิธีแก้ปัญหา
เรามี 6 10 mod 11 =1 นี่เป็นรุ่นแรกของทฤษฎีบทเล็กๆ ของแฟร์มาต์ โดยที่ p =11
ตัวอย่าง2 − หาผลลัพธ์ของ 3 12 mod 11
วิธีแก้ปัญหา
ดังนั้นเลขชี้กำลัง (12) และโมดูลัส (11) จึงไม่เท่ากัน ด้วยการแทนที่สิ่งนี้สามารถกำหนดได้โดยใช้ทฤษฎีบทเล็ก ๆ ของแฟร์มาต์
3 12 mod11 =(3 11 x3)mod11 =(3 11 mod11)(3 mod 11) =(3x3)mod11 =9
