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

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

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

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

$p\mid a^{p}-a$

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

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

บทพิสูจน์

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

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

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