ทฤษฎีบทเล็กของแฟร์มา

ทฤษฎีบทเล็กของแฟร์มา (อังกฤษ: Fermat's little theorem) กล่าวว่า ถ้า p เป็นจำนวนเฉพาะแล้ว สำหรับจำนวนเต็ม a ใด ๆ จะได้ว่า

$a^{p}\equiv a{\pmod {p}}\,\!$

หมายความว่า ถ้าเลือกจำนวนเต็ม a มาคูณกัน p ครั้ง จากนั้นลบด้วย a ผลลัพธ์ที่ได้จะหารด้วย p ลงตัว (ดูเลขคณิตมอดุลาร์)

ทฤษฎีบทนี้กล่าวอีกแบบหนึ่งได้ว่า ถ้า p เป็นจำนวนเฉพาะ และ a เป็นจำนวนเต็มที่เป็นจำนวนเฉพาะสัมพัทธ์กับ p แล้ว จะได้ว่า

$a^{p-1}\equiv 1{\pmod {p}}\,\!$

a^(p-1) สมภาคกับ 1 มอดุโล p เมื่อ p เป็นจำนวนเฉพาะนั้น ควรแก้เป็น a^p สมภาคกับ a มอดุโล p มากกว่า

บทพิสูจน์

ปีแยร์ เดอ แฟร์มาได้ตั้งทฤษฎีบทนี้โดยไม่ได้ให้บทพิสูจน์ไว้ ต่อมา กอทท์ฟรีด วิลเฮล์ม ไลบ์นิซ ได้เขียนบทพิสูจน์ไว้ในหนังสือโดยไม่ได้ลงวันที่ รู้เพียงว่าเขาพิสูจน์ได้ก่อน ค.ศ. 1683

จำนวนเฉพาะเทียม

ถ้าa และ p เป็นจำนวนเฉพาะสัมพัทธ์กัน และทำให้ $\,a^{p-1}-1$ หารด้วย p ลงตัว แล้ว p ไม่จำเป็นจำนวนเฉพาะเสมอไป ถ้า p ไม่เป็นจำนวนเฉพาะ เราจะเรียก p ว่าเป็นจำนวนเฉพาะเทียม (pseudoprime) ฐาน a. ใน ค.ศ. 1820 F. Sarrus พบว่า 341 = 11×31 เป็นจำนวนเฉพาะเทียมฐาน 2 ตัวแรก