อ้างอิง:
ข้อความเดิมเขียนโดยคุณ กิตติ
ข้อนี้โหดมากเลยครับ.....หมดเวลาเป็นชั่วโมงเพื่อไล่หาค่า
$7^4 \equiv 401 \pmod{1000} $
$7^5 \equiv 807 \pmod{1000} $
ใช้วิธี$a \equiv b \pmod{c} \rightarrow a^n \equiv b^n \pmod{c} $
ตัวกำหนดความยากง่ายก็คือ$b$...นี่แหละครับ ยิ่งน้อย เวลาเอาไปคูณกับอะไรหรือยกกำลังก็ง่ายขึ้น.....ผมนั่งไล่ไปจนได้
$7^{22} \equiv 49 \pmod{1000} $....จริงๆไล่ไปจนถึง$7^{30}$....เริ่มไม่ไหวแล้ว ผมเลือกตรงนี้เพราะเห็นว่าค่า$49$น้อยที่สุดแล้ว และเรารู้ว่า$9^n$ลงท้ายด้วย$1$กับ$9$ เท่านั้น ดังนั้นมีโอกาสที่จะหา$7^n \equiv 1 \pmod{1000} $ได้
$7^{44} \equiv 401 \pmod{1000}$
$7^{88} \equiv 801 \pmod{1000}$
$7^{176} \equiv 601 \pmod{1000}$
$7^{352} \equiv 201 \pmod{1000}$
$7^{704} \equiv 401 \pmod{1000}$
$7^{704+176} \equiv 601\times 401 \pmod{1000} \rightarrow 7^{880} \equiv 1 \pmod{1000} $......ตรงนี้บังเอิญได้พอดี จริงๆกะว่าจะเอาตัวมาคูณไปเรื่อยๆจนถึง$7^{999}$
จะได้ว่า$999=880+119$
$7^{999} \equiv 7^{119} \pmod{1000} $
$7^{88+22} \equiv 49\times 801 \pmod{1000} \rightarrow 7^{110} \equiv 249 \pmod{1000} $
$7^{4+5} \equiv 401\times 807 \pmod{1000} \rightarrow 7^9\equiv 607 \pmod{1000}$
$7^{110+9} \equiv 249\times 607 \pmod{1000}\rightarrow 7^{119} \equiv 143 \pmod{1000} $
คำตอบมาแล้ว สามตัวหลักสุดท้ายของ$7^{999}$ คือ$143$
โจทย์ข้อนี้กินแรงมากเลยครับ....ถ้าจะผิดก็ด้วยเบลอในตัวเลข โหดได้ใจเลยครับ
ไม่รู้ว่ามีทริคคิดให้สั้นกว่านี้ได้ไหม....หมดแรงเลยวันนี้
|
ใช้ทวินามเอาครับ $7^4 = 2401 , 7^{4n} = 2401^n = (2400+1)^n$
หาเศษจากการหารด้วย 1000 คือ $1+\binom{n}{1}2400$
$n=249 , 24(249)(100)+1 = m01 = 601$
$601*7^3 = 206$
$143$