ผลต่างระหว่างรุ่นของ "ทฤษฎีบทเล็กของแฟร์มา"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ไม่มีความย่อการแก้ไข |
ป้ายระบุ: เพิ่มข้อความไม่เป็นวิกิขนาดใหญ่ การแก้ไขแบบเห็นภาพ |
||
บรรทัด 12:
== บทพิสูจน์ ==
[[ปีแยร์ เดอ แฟร์มา]]ได้ตั้งทฤษฎีบทนี้โดยไม่ได้ให้บทพิสูจน์ไว้ ต่อมา [[กอทท์ฟรีด วิลเฮล์ม ไลบ์นิซ]] ได้เขียนบทพิสูจน์ไว้ในหนังสือโดยไม่ได้ลงวันที่ รู้เพียงว่าเขาพิสูจน์ได้ก่อน [[ค.ศ. 1683]]
การพิสูจน์ที่ 1
ถ้า p เป็นจำนวนเฉพาะ และ <math>p\nmid a</math> แล้ว <math>a^{p-1} \equiv 1 \pmod{p}\,\!</math>
จำนวนเต็ม a ทุกจำนวนสมภาคกับ 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} ที่ทำให้ <math>r\cdot a \equiv 0</math>(mod p) แล้ว <math>p\mid r\cdot a</math>เป็นไปไม่ได้ เพราะ <math>p\nmid a</math>และ r<p ทำให้ <math>p\nmid r</math>ดังนั้น
ไม่มีจำนวน r ที่ทำให้ <math>r\cdot a \equiv 0</math>ฉะนั้นในเซต {a,2a,3a,...,(p-1)a} จะไม่มี 0 เป็นสมาชิก
กรณีที่ 2 ในเซต {a,2a,3a,...,(p-1)a} ไม่มีตัวไหนที่ซ้ำกันภายใต้ mod p
มีจำนวน r,s เป็นสมาชิกในเซต {1,2,3,...,p-1} และ <math>r\neq s</math> ดังนั้น
จะพิสูจน์ว่า <math>a\cdot r\not\equiv a\cdot s</math> ก็คือ <math>a\cdot r - a\cdot s\not\equiv 0</math>แยกตัวประกอบได้ <math>a(r-s)\not\equiv 0</math>การที่จะทำให้เกิดข้อขัดแย้งได้
<math>r-s\not\equiv 0</math> จึงมีสมการคือ
0<r<p 0<s<p หา r-s นำ 0<s<p คูณด้วย -1 ได้ -p<-s<0 นำมาบวกด้วย 0<r<p จะได้
-p<r-s<p และ <math>r\neq s</math> ทำให้ <math>r-s\neq 0</math>
ถ้า r-p เป็นจำนวนเต็มบวก 0<r-s<p ดังนั้น <math>p\mid r-s</math>
ถ้า r-p เป็นจำนวนเต็มลบ -p<r-s<0 ดังนั้น <math>p\mid r-s</math>
หมายความว่า <math>r-s \not\equiv 0</math>(mod p) ดังนั้น <math>a\cdot r\not\equiv a\cdot s</math>(mod p)
ก็คือภายในเซต {a,2a,3a,...,(p-1)a} ไม่มีตัวไหนที่ซ้ำกันภายใต้ mod p
จากสองกรณีจะได้ เซต {a,2a,3a,...,(p-1)a} กับ {1,2,3,...,p-1} (mod p) ทั้งสองเซตเท่ากันภายใต้ mod p
ดังนั้นเมื่อเอาสมาชิกในแต่ละเซตคูณกันจะได้ตัวเลขที่เท่ากันภายใต้ mod p
ax2ax3ax...x(p-1)xa <math>\equiv</math> 1x2x3,...,p-1 (mod p)
(p-1)! <math>a^{p-1} \equiv </math>(p-1)! (mod p)
เนื่องจาก (p-1)! <math>\not\equiv 0 </math>(mod p) เพราะ p เป็นจำนวนเฉพาะจึงไม่มีผลคูณใดใน (p-1)! คูณได้ p ที่จะทำให้ (p-1)!<math>\equiv0</math>(mod p)
เราจึงหารทั้งสองข้างด้วย (p-1)! ได้
<math>a^{p-1} \equiv 1 \pmod{p}\,\!</math>
== จำนวนเฉพาะเทียม ==
| |||