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

ปิแยร์ เดอ แฟร์มา

ทฤษฎีบทเล็กของแฟร์มา (แม่แบบ:Langx) กล่าวว่า ถ้า $p$ เป็นจำนวนเฉพาะแล้ว $a^p-a$ จะเป็นพหุคูณของ $p$ สำหรับทุกจำนวนเต็ม $a$ หรือเขียนในรูปเลขคณิตมอดุลาร์ได้เป็น

$a^p\equiv a(\mathrm{mod}p)$

ตัวอย่างเช่น เมื่อ $a=2$ และ $p=7$ พบว่า $2^7-2=128-2=126=7\times 18$ ดังนั้น $2^7-2$ จึงเป็นพหุคูณของ 7

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

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

ทฤษฎีบทเล็กของแฟร์มาเป็นผลลัพธ์พื้นฐานในทฤษฎีจำนวน และเป็นพื้นฐานของการทดสอบจำนวนเฉพาะของแฟร์มา ทฤษฎีบทนี้ได้ชื่อตาม ปีแยร์ เดอ แฟร์มา ผู้ได้เสนอทฤษฎีบทนี้ในปี ค.ศ. 1640 และได้ชื่อว่าเป็น "ทฤษฎีบทเล็ก" เพื่อแยกแยะให้แตกต่างกับทฤษฎีบทสุดท้ายของแฟร์มา

บทพิสูจน์

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

บทพิสูจน์ด้านล่าง เป็นบทพิสูจน์สำหรับรูปแบบหนึ่งของทฤษฎีบทดังกล่าวที่ว่า: ถ้า $p$ เป็นจำนวนเฉพาะ และ $a$ เป็นจำนวนเต็มที่เป็นจำนวนเฉพาะสัมพัทธ์กับ $p$ แล้วจะได้ว่า $a^{p-1}\equiv 1(\mathrm{mod}p)$

บทพิสูจน์ข้างต้น ค้นพบโดย James Ivory ก่อนจะถูกค้นพบใหม่ในภายหลังโดย ดีรีเคล นอกจากนี้ยังมีบทพิสูจน์ในรูปแบบอื่น ๆ เช่น พิสูจน์จากทฤษฎีบทของออยเลอร์ ใช้วิธีการทางคอมบินาทอริกส์ หรือทางทฤษฎีกรุป

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

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

จำนวนเต็ม $p$ ที่เป็นจำนวนเฉพาะเทียมฐาน $a$ สำหรับทุกจำนวนเต็ม $a$ ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ $p$ เรียกว่า จำนวนคาร์ไมเคิล (Carmichael number) ตัวอย่างจำนวนคาร์ไมเคิล เช่น 561