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

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

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

${\displaystyle a^{p}\equiv a{\pmod {p}}\,\!}$

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

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

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}\,\!}$

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

บทพิสูจน์

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

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

พิสูจน์ —

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

บทความหลัก: จำนวนเฉพาะเทียม

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

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

อ้างอิง

1. Burton, David M. (2011). The history of mathematics : an introduction (7th ed.). New York: McGraw-Hill. p. 514. ISBN 978-0-07-338315-6. OCLC 476835570.
2. Ore, Øystein (1988). Number theory and its history. New York: Dover. p. 273. ISBN 0-486-65620-9. OCLC 17413345.
3. Hardy, G. H. (2008). An introduction to the theory of numbers. E. M. Wright, D. R. Heath-Brown, Joseph H. Silverman (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921985-8. OCLC 214305907.
4. Ivory, James (1806), "Demonstration of a theorem respecting prime numbers", New Series of the Mathematical Depository, 1 (II): 6–8
5. Lejeune Dirichlet, Peter Gustav (1828), "Démonstrations nouvelles de quelques théorèmes relatifs aux nombres", Journal für die reine und angewandte Mathematik (ภาษาฝรั่งเศส), 3: 390–393
6. Golomb, S. W. (1956). "Combinatorial Proof of Fermat's "Little" Theorem". The American Mathematical Monthly. 63 (10): 718–718. doi:10.2307/2309563. ISSN 0002-9890.
7. Weil, André (1979). Number Theory for Beginners (ภาษาอังกฤษ). New York, NY: Springer New York. doi:10.1007/978-1-4612-9957-8. ISBN 978-0-387-90381-1.