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

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา

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

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

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

บทพิสูจน์[แก้]

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

บทพิสูจน์ที่ 1[แก้]

ถ้า 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} ที่ทำให้ (mod p) แล้ว เป็นไปไม่ได้ เพราะ และ 0<r<p ทำให้ ดังนั้น

ไม่มีจำนวน r ที่ทำให้ (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} และ ดังนั้น

พิสูจน์ว่า (mod p) ก็คือ (mod p) แยกตัวประกอบได้ การที่จะทำให้เกิดข้อขัดแย้งได้

(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-p เป็นจำนวนเต็มบวก 0<r-s<p ดังนั้น

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

หมายความว่า (mod p) ดังนั้น (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 1x2x3,...,p-1 (mod p)

(p-1)! (p-1)! (mod p)

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

(mod p)

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

ถ้า

จำนวนเฉพาะเทียม[แก้]

ถ้า และ เป็นจำนวนเฉพาะสัมพัทธ์กัน และทำให้ หารด้วย ลงตัว แล้ว ไม่จำเป็นจำนวนเฉพาะเสมอไป ถ้า ไม่เป็นจำนวนเฉพาะ เราจะเรียก ว่าเป็น จำนวนเฉพาะเทียม (pseudoprime) ฐาน . ใน ค.ศ. 1820 F. Sarrus พบว่า เป็นจำนวนเฉพาะเทียมฐาน 2 ตัวแรก