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

ทฤษฎีบทเล็กของแฟร์มา (อังกฤษ: 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

บทพิสูจน์ที่ 1

ถ้า p เป็นจำนวนเฉพาะ และ $p\nmid a$ แล้ว $a^{p-1}\equiv 1{\pmod {p}}\,\!$

กำหนดจำนวน 1,2,3,...,p-1 (mod p)

จะมีจำนวน 1,2,3,...,p-1 คูณจำนวนเหล่านี้ด้วย a ได้ a,2a,3a,...,(p-1)a (mod p)

พิสูจน์ว่าเซต {a,2a,3a,...,(p-1)a} กับ {1,2,3,...,p-1} (mod p) ทั้งสองเซตเท่ากันภายใต้ mod p

กรณีที่ 1 ไม่มีจำนวน r เป็นสมาชิกในเซต {1,2,3,...,p-1} ที่ทำให้ $r\cdot a\equiv 0$(mod p) แล้ว $p\mid r\cdot a$เป็นไปไม่ได้ เพราะ $p\nmid a$และ 0<r<p ทำให้ $p\nmid r$ดังนั้น

ไม่มีจำนวน r ที่ทำให้ $r\cdot a\equiv 0$(mod p) เพราะ p เป็นจำนวนเฉพาะวิธีเดียวที่จะหารด้วย p ลงตัวคือ r หรือ a จะต้องหารด้วย p ลงตัว

ฉะนั้นในเซต {a,2a,3a,...,(p-1)a} จะไม่มี 0 เป็นสมาชิกแสดงว่า ในเซต {a,2a,3a,...,(p-1)a} เมื่อ mod p จำนวนที่เป็นไปได้

คือ 1 ถึง p-1 ยกเว้น 0 ในเศษ p ที่เป็นไปได้

กรณีที่ 2 ในเซต {a,2a,3a,...,(p-1)a} ไม่มีตัวไหนที่ซ้ำกันภายใต้ mod p

มีจำนวน r,s เป็นสมาชิกในเซต {1,2,3,...,p-1} และ $r\neq s$ ดังนั้น

พิสูจน์ว่า $a\cdot r\not \equiv a\cdot s$(mod p) ก็คือ $a\cdot r-a\cdot s\not \equiv 0$ (mod p) แยกตัวประกอบได้ $a(r-s)\not \equiv 0$ การที่จะทำให้เกิดข้อขัดแย้งได้

$r-s\not \equiv 0$(mod p) จึงมีสมการคือ

0<r<p 0<s<p หา r-s นำ 0<s<p คูณด้วย -1 ได้ -p<-s<0 นำมาบวกด้วย 0<r<p จะได้

-p<r-s<p และ $r\neq s$ ทำให้ $r-s\neq 0$

ถ้า r-p เป็นจำนวนเต็มบวก 0<r-s<p ดังนั้น $p\nmid r-s$

ถ้า r-p เป็นจำนวนเต็มลบ -p<r-s<0 ดังนั้น $p\nmid r-s$

หมายความว่า $r-s\not \equiv 0$(mod p) ดังนั้น $a\cdot r\not \equiv a\cdot s$(mod p)

ดังนั้นภายในเซต {a,2a,3a,...,(p-1)a} ไม่มีตัวไหนที่ซ้ำกันภายใต้ mod p

จากสองกรณีจะได้ เซต {a,2a,3a,...,(p-1)a} มีตัวเลขตั้งแต่ 1 ถึง p-1 และเซตนี้มีสมาชิก p-1 ตัวและ ตัวเลขไม่ซ้ำกันทำให้มีเลขตั้งแต่ 1 ถึง p-1 ครบทุกตัวภายใต้ mod p

ทำให้ {a,2a,3a,...,(p-1)a} mod p={1,2,3,...,p-1}

ดังนั้นเมื่อเอาสมาชิกในแต่ละเซตคูณกันแล้วจะได้ตัวเลขที่เท่ากันภายใต้ mod p

ax2ax3ax...x(p-1)xa $\equiv$ 1x2x3,...,p-1 (mod p)

(p-1)! $a^{p-1}\equiv$(p-1)! (mod p)

เนื่องจาก ทฤษฎีบทของวิลสัน (p-1)! $\equiv -1$(mod p) ได้

$-a^{p-1}\equiv -1$ (mod p)

คูณด้วย -1 ทั้งสองข้างได้

$a^{p-1}\equiv 1{\pmod {p}}\,\!$ ถ้า $p\nmid a$

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

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