ความรู้เบื้องต้นเรื่อง mod

[กิตติ]

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

[ความรู้ยังอ่อนด้อย]

ครับ แต่ผมไม่รู้ว่าเขาจะเรียกผมหรือเปล่า

ตอนสอบผมก็ทำไม่ได้หลายข้อเลย

แต่ผมว่าคุณเก่งมากๆเลยนะครับ ดูจากกระทู้หลายๆ กระทู้แล้ว

[กิตติ]

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

[Siren-Of-Step]

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

ข้อนี้โหดมากเลยครับ.....หมดเวลาเป็นชั่วโมงเพื่อไล่หาค่า
$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$

[กิตติ]

ที่น้องsirenคิดนั้นก็เข้าข่ายเดียวกับที่ลุงBankerใบ้หวยให้ดูในกระทู้ก่อน
หลักการเดียวกัน

[Siren-Of-Step]

ให้เอากิตติเอาไปฝึกนะครับ

จงหาเลขสามหลักสุดท้ายของ $13^{2009}$ ข้อนี้ผมแนะนำให้ใช้ mod จะง่ายกว่าทวินามนะครับ (ความเห็นผมอะ)

[กิตติ]

ทวินามไม่เอาแล้วถ้าใช้modเป็น
จงหาเลขสามหลักสุดท้าย $13^{2009}$
$1000 = 2^35^3$
$\phi (1000) = 400$
$13^{400} \equiv 1 \pmod{1000} $
$(13^{400})^5 \equiv 1 \pmod{1000} $
$13^{2000}\equiv 1 \pmod{1000} $
$13^4 \equiv 561 \pmod{1000} $
$13^8 \equiv 721 \pmod{1000} $
$13^9 \equiv 9373 =373\pmod{1000} $
$13^{2009}\equiv 373 \pmod{1000} $
ลงท้ายด้วย$373$....ไม่รู้ว่าถูกไหม

[Siren-Of-Step]

ถูกต้องนะครับ !!

[-SIL-]

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

ทวินามไม่เอาแล้วถ้าใช้modเป็น
จงหาเลขสามหลักสุดท้าย $13^{2009}$
$1000 = 2^35^3$
$\phi (1000) = 400$
$13^{400} \equiv 1 \pmod{1000} $
$(13^{400})^5 \equiv 1 \pmod{1000} $
$13^{2000}\equiv 1 \pmod{1000} $
$13^4 \equiv 561 \pmod{1000} $
$13^8 \equiv 721 \pmod{1000} $
$13^9 \equiv 9373 =373\pmod{1000} $
$13^{2009}\equiv 373 \pmod{1000} $
ลงท้ายด้วย$373$....ไม่รู้ว่าถูกไหม

คิดว่าใช้ทวินามหหลังใช้ phi-func จะเท่กว่าครับ

[ความรู้ยังอ่อนด้อย]

φ(1000)=400

φ เครื่องหมายนี้คืออะไรหรอ

ผมลองดูแล้วตามไม่ทันเลย

[PGMwindow]

ขอบคุณสำหรับบทความเรื่อง mod มากครับ

[Onasdi]

ข้อความเดิมเขียนโดยคุณ ความรู้ยังอ่อนด้อย

φ(1000)=400

φ เครื่องหมายนี้คืออะไรหรอ

ผมลองดูแล้วตามไม่ทันเลย

มันคือ http://en.wikipedia.org/wiki/Euler&#...r.27s_function ครับ
เค้ากำลังใช้ทฤษฎีนี้อยู่ครับ http://en.wikipedia.org/wiki/Euler's_theorem

[IloveMathPK]

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

อ่านถึงตรงนี้ ผมเชื่อว่า พอจะเข้าใจพื้นฐานเรื่อง mod ได้แล้ว

ถ้าน้องๆหลานๆสนใจ ก็ต้องหาแบบฝึกหัดมาทำให้เกิดความช่ำชอง

ผมเชื่อว่า ด้วยพื้นฐานที่ได้อ่านมานี้ ก็สามารถไปอ่านเรื่อง mod ในหนังสือต่างๆด้วยความเข้าใจได้

ไม่มีวิธีลัดที่จะให้เก่งเรื่อง mod มากไปกว่าการทำแบบฝึกหัดมากๆ

ส่วนผม ผมคงจบตรงนี้ เพราะวัตถุประสงค์ของผม แค่เพื่อติวหลานที่อยู่ประถมเท่านั้น

โปรดอย่าถามอะไรที่ยากๆ หรือที่เกินประถมหรือมัธยมต้น

เพราะผมก็รู้แค่นี้แหละ

รู้แล้วเอามาเผยแพร่ให้เด็กๆของเรา เป็นเด็กเก่ง

เพราะเด็กๆในวันนี้ จะเป็นอนาคตของชาติต่อไป

ซึ้งครับ ขอบคุณมากครับ ผมเข้าใจขึ้นมากเลย อยากให้มีคนแบบนี้ในสังคมเยอะๆ

[polsk133]

น่าเสียดายนะครับ ที่ตอนแรกผมเข้ามายังไม่รู้เลยว่า mod คืออะไร แต่ก็ไม่เจอกระทู้นี้

[lookket]

ขอบคุณมากๆ ค่ะ