ทฤษฎีบทเล็กของแฟร์มา
บทความนี้ไม่มีการอ้างอิงจากแหล่งที่มาใด |
ทฤษฎีบทเล็กของแฟร์มา (อังกฤษ: 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 ตัวแรก