[หยินหยาง]

ข้อความเดิมเขียนโดยคุณ banker

เรียนถามคุณหยินหยาง ทำไมต้องหาร n ด้วย 3 ครับ แล้วแนวคิด mod 7 คิดยังไงครับ

แนวคิดของผมคือ

$2^n+1 = (641)(409^2+2556^2)$ ซึ่งผมจะเอา 7 ไปหารจะได้ว่า ฝั่งขวามือจะเหลือเศษ 5 ดังนั้นจะเขียนได้ว่า
$ 2^n+1 \equiv 5 (mod 7)$
$2^n \equiv 4 (mod 7)$ จะเห็นได้ว่า $n > 2$ และ $(4,7)=1$
$\therefore 2^{n-2} \equiv 1 (mod 7)$
และเพราะว่า 3 เป็นจำนวนเต็มบวกที่น้อยที่สุดซึ่ง $2^3 \equiv 1 (mod 7)$
ดังนั้น จะได้ว่า $3|n-2$

หมายเหตุเนื่องจากข้อนี้เป็นข้อสอบ ตัวเลือกจึงสามารถใช้วิธีคิดแบบนี้ได้และตัวเลือกที่ให้ก็มีเพียงตัวเดียวที่เข้าเงื่อนไขที่ว่านี้ด้วย

ปล. คุณ Scylla_Shadow นี่เล่นจำตัวเลขเลยหรือนี่ แต่อยากจะบอกว่าต้องระวังคือไม่สามารถบอกได้ว่าถ้า n เป็นตัวอื่นไม่ได้หมายความว่าจะไม่มี 641 เป็นตัวประกอบ แต่ถ้าโจทย์เปลี่ยนเป็น จงหา n ที่ $641|2^n+1$ ก็พอไหว