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

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

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

$a^{p}\equiv a{\pmod {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{\pmod {p}}\,\!$

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

บทพิสูจน์

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

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

พิสูจน์ —

สมมติให้ $p$ เป็นจำนวนเฉพาะ และ $a$ เป็นจำนวนเต็มที่เป็นจำนวนเฉพาะสัมพัทธ์กับ $p$

แนวคิดของบทพิสูจน์อาศัยข้อสังเกตที่ว่า ลำดับของจำนวนเต็มต่อไปนี้

$a,2a,3a,\dotsc ,(p-1)a$

เป็นลำดับเดียวกับ $1,2,3,\dotsc ,p-1$ ในมอดุโล $p$ แต่ต่างกันแค่การเรียงลำดับเท่านั้น

เพื่อพิสูจน์ข้อความข้างต้น เราสังเกตว่า จำนวนทุกตัวในลำดับ $a,2a,3a,\dotsc ,(p-1)a$ ไม่มีจำนวนใดคอนกรูเอนซ์กับ 0 ในมอดุโล $p$ ซึ่งเห็นได้ชัดจากการที่ทุกจำนวน $k$ ในลำดับ $1,2,3,\dotsc ,p-1$ ไม่มีตัวประกอบร่วมกันกับ $p$ และ $a$ ก็ไม่มีตัวประกอบร่วมกับกับ $p$ ด้วย ดังนั้นผลคูณ $ka$ ไม่มีตัวประกอบร่วมกันกับ $p$ (ดูเพิ่มที่ บทตั้งของยุคลิด)

ต่อไป เราพิสูจน์ว่าทุกสมาชิกในลำดับ $a,2a,3a,\dotsc ,(p-1)a$ แตกต่างกันทั้งหมดในมอดุโล $p$

สมมติให้ $k$ และ $m$ เป็นจำนวนเต็มในลำดับ $1,2,3,\dotsc ,p-1$ ที่ทำให้ $ka\equiv ma{\pmod {p}}$

จากสมบัติการตัดออกในเลขคณิตมอดุลาร์จะได้

$k\equiv m{\pmod {p}}$

แต่จาก $k,m$ มีค่าอยู่ในช่วง $1,2,3,\dotsc ,p-1$ จึงบังคับให้ $k=m$ เท่านั้น

จากการพิสูจน์ข้างต้น เมื่อลดทอนลำดับ $a,2a,3a,\dotsc ,(p-1)a$ ในมอดุโล $p$ จะต้องแตกต่างกันทั้งหมด แต่เนื่องจาก $a,2a,3a,\dotsc ,(p-1)a$ เป็นลำดับที่มีสมาชิกทั้งหมด $p-1$ ตัวที่แตกต่างกันทั้งหมด ดังนั้นเมื่อลดทอนแล้วจะต้องได้เป็นการเรียงลำดับใหม่ของ $1,2,3,\dotsc ,p-1$ เท่านั้น

จึงทำให้ได้ว่า

${\begin{aligned}\displaystyle a\times 2a\times 3a\times \dotsb \times (p-1)a&\equiv 1\times 2\times 3\times \dotsb \times (p-1){\pmod {p}}\\a^{p-1}(p-1)!&\equiv (p-1)!{\pmod {p}}\end{aligned}}$

และจาก $(p-1)!$ เป็นจำนวนเฉพาะสัมพัทธ์กับ $p$ จึงส่งผลให้สามารถตัดออกจากทั้งสองข้างของสมการคอนกรูเอนซ์ได้ จึงสรุปได้ว่า $a^{p-1}\equiv 1{\pmod {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