Fermat number

[กระบี่ทะลวงด่าน]

ช่วยหน่อยครับ
$2^{2^{2551}}+1$. มีเลขโดดสี่หลักสุดท้ายคืออะไร

[Thgx0312555]

เนื่องจาก $\phi (625) = 500$
พิจารณา $2^{2551} \ (mod \ 500)$

$500 = 125 \times 4$

$2^{2551} \equiv 0 \ (mod \ 4)$

โดย Euler's theorem
$2^{100} \equiv 1 \ (mod \ 125)$
$2^{2500} \equiv 1 \ (mod \ 125)$
$2^{2551} \equiv 2^{51} \ (mod \ 125)$

แต่ $2^7 \equiv 3 \ (mod \ 125)$
$2^{14} \equiv 9 \ (mod \ 125)$
$2^{35} \equiv 243 \equiv -7 \ (mod \ 125)$

$2^{49} \equiv -63 \equiv 62 \ (mod \ 125)$
$2^{50} \equiv 124 \equiv -1 \ (mod \ 125)$
$2^{51} \equiv -2 \ (mod \ 125)$

ดังนั้น
$2^{2551} \equiv -2 \ (mod \ 125)$

โดย Euclidean Algorithm
$2^{2551} \equiv 248 \ (mod \ 500)$

$2^{2551} - 248 = 500k, \exists k \in \mathbb{Z}$

$2^{2^{2551}} = 2^{500k+248} = (2^{500})^k \times 2^{248} \equiv 2^{248} \ (mod \ 625)$
$2^{2^{2551}} \equiv 2^{248} \equiv 0 \ (mod \ 16)$

ดังนั้น
$2^{2^{2551}} \equiv 2^{248} \ (mod \ 10000)$
ก็ไปคำนวณออกมาว่า $2^{248}$ ลงท้ายด้วยเลขอะไรแล้วก็บวก $1$ ครับ

[กระบี่ทะลวงด่าน]

Thank you very much krub