Congruence (สามหลักท้าย)

[polsk133]

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

รู้ได้อย่างไรหรอครับ TT

$\phi (125) = 100$ ซึ่ง $100 \mid 29!$ ลงตัว

จาก $2^{100} \equiv 1 (mod 125)$

$2^{100k} = 2^{29!} \equiv 1 (mod 125)$

ปล. หายไปนานเลยนะครับคุณ Mol3ius

[poper]

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

แบ่งเป็นแบบนี้นะครับ

$2^{29!} \equiv 0 \pmod{ 8} $

$2^{29!} \equiv 1 \pmod{125}$

โดย Euclid algorithm จะได้ว่า

$\therefore 2^{29!} $ จะมีเลข 3 หลักท้ายคือ $376$

รบกวนแสดงวิธีทำส่วนของ Euclid algorithm ทีครับ
ผมทำแล้วมันงงๆอ่ะครับ

[polsk133]

8m=125n+1
8m-125n=1
ใช้วิธีหา หรม จะได้mมา
ซึ่งจะได้ว่า $2^29!\equiv 8m mod1000$
แล้วก็แทนmลงไปครับ

[poper]

งงตรงหาหรม.อ่ะครับ
สมมุติผมใช้ Euclid algorithm จะได้แบบนี้ใช่มั้ยครับ
$5=125-8(15)$ แล้วยังไงต่ออ่ะครับ

[polsk133]

ก็หา หรม วิธียูคลิดแล้วทำย้อนครับ
125=8(15)+5
8=5(1)+3
5=3(1)+2
3=2(1)+1
2=1(2)
แล้วก็ทำย้อน
1=3-2(1)
1=3-(5-3)
1=3(2)-5
1=(8-5)(2) -5
1=8(2)-5(3)
1=8(2)-(125-8(15))(3)
1=8(47)-125(3)
ได้m=47

[poper]

ขอบคุณครับ

[Mojo-Mojo]

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

8m=125n+1
8m-125n=1
ใช้วิธีหา หรม จะได้mมา
ซึ่งจะได้ว่า $2^{29!}\equiv 8m mod1000$
แล้วก็แทนmลงไปครับ

$2^{29!}\equiv 8m (mod1000)$ มันมายังไงเหรอครับ ช่วยอธิบายหน่อยนะครับ