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

ทฤษฎีบทเล็กของแฟร์มา (อังกฤษ: 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 และได้ชื่อว่าเป็น "ทฤษฎีบทเล็ก" เพื่อแยกแยะให้แตกต่างกับทฤษฎีบทสุดท้ายของแฟร์มา^[1]

บทพิสูจน์

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

บทพิสูจน์ด้านล่าง^[3] เป็นบทพิสูจน์สำหรับรูปแบบหนึ่งของทฤษฎีบทดังกล่าวที่ว่า: ถ้า $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^[4] ก่อนจะถูกค้นพบใหม่ในภายหลังโดย ดีรีเคล^[5] นอกจากนี้ยังมีบทพิสูจน์ในรูปแบบอื่น ๆ เช่น พิสูจน์จากทฤษฎีบทของออยเลอร์ ใช้วิธีการทางคอมบินาทอริกส์^[6] หรือทางทฤษฎีกรุป^[7]

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

ถ้า $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

อ้างอิง

↑ ^1.0 ^1.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.
↑ Ore, Øystein (1988). Number theory and its history. New York: Dover. p. 273. ISBN 0-486-65620-9. OCLC 17413345.
↑ 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.
↑ Ivory, James (1806), "Demonstration of a theorem respecting prime numbers", New Series of the Mathematical Depository, 1 (II): 6–8
↑ 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
↑ 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.
↑ 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.

[:0-1] 1.0 ^1.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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]