ส่วนที่เหลือของ p 12 ^ คืออะไร (p-1) เมื่อ p เป็นไพร์ม?

ตอบ:

ส่วนที่เหลือเท่ากับ #0# เมื่อ # P # เป็นทั้ง #2# หรือ #3#และมันเท่ากับ #1# สำหรับหมายเลขสำคัญอื่น ๆ ทั้งหมด

คำอธิบาย:

ก่อนอื่นปัญหานี้สามารถแก้ไขได้ว่าต้องหาค่าของ # 12 ^ (p-1) mod p # ที่ไหน # P # เป็นจำนวนเฉพาะ

ในการแก้ปัญหานี้คุณต้องรู้ทฤษฎีของออยเลอร์ ทฤษฎีบทของออยเลอร์กล่าวว่า #a ^ { varphi (n)} - = 1 mod n # สำหรับจำนวนเต็มใด ๆ # A # และ # n # นั่นคือ coprime (พวกเขาไม่แบ่งปันปัจจัยใด ๆ) คุณอาจจะสงสัยในสิ่งที่ # varphi (n) # คือ. นี่คือฟังก์ชันที่รู้จักกันในชื่อ totient มันถูกกำหนดให้เท่ากับจำนวนจำนวนเต็ม # <= n # เช่นนั้นจำนวนเต็มเหล่านั้น coprime ถึง # n #. โปรดจำไว้ว่าจำนวน #1# ถือเป็น coprime ของจำนวนเต็มทั้งหมด

ตอนนี้เรารู้ทฤษฎีของออยเลอร์แล้วเราสามารถแก้ไขปัญหานี้ได้

โปรดทราบว่าจำนวนเฉพาะทั้งหมดที่นอกเหนือจาก #2# และ #3# เป็น coprime ด้วย #12#. ลองแยก 2 และ 3 ออกทีหลังแล้วจดจ่อกับช่วงเวลาที่เหลือ เนื่องจากจำนวนเฉพาะเหล่านั้นเป็น coprime ถึง 12 เราจึงสามารถใช้ทฤษฎีบทของออยเลอร์กับพวกเขาได้:

# 12 ^ { varphi (p)} - = 1 mod p #

ตั้งแต่ # P # เป็นจำนวนเฉพาะ # varphi (P) = P-1 #. มันสมเหตุสมผลแล้วเพราะทุก ๆ หมายเลขที่น้อยกว่าจำนวนเฉพาะจะเป็น coprime ด้วย

ดังนั้นตอนนี้เรามี # 12 ^ {p-1} - = 1 mod p #

สามารถแปลนิพจน์ด้านบนเป็น # 12 ^ {p-1} # หารด้วย # P # มีที่เหลืออยู่ #1#.

ตอนนี้เราแค่ต้องพิจารณา #2# และ #3#ซึ่งอย่างที่คุณพูดก่อนหน้านี้ทั้งคู่มีส่วนที่เหลืออยู่ #0#.

ดังนั้นเราได้พิสูจน์แล้วว่า # 12 ^ {p-1} # หารด้วย # P # ที่ไหน # P # เป็นจำนวนเฉพาะมีเศษเหลือ #0# เมื่อ p เป็นอย่างใดอย่างหนึ่ง #2# หรือ #3# และมีส่วนที่เหลืออยู่ #1# มิฉะนั้น.