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

[banker]

ถูกครับ

การแจกแจง หรือยกกำลัง ทำได้หลากหลายแบบ แล้วแต่จินตนาการของแต่ละคน (ทำบ่อยๆ ก็เป็นประสบการณ์ไป)

ทำบ่อยๆ ทำมากๆ ก็อาจข้ามบางขั้นตอน จนกลายเป็นกลับไปสู่สามัญ

[poper]

ขอบคุณครับ
ขออีกเยอะๆเลยครับเริ่มมันส์แล้ว

[banker]

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

ขอบคุณครับ
ขออีกเยอะๆเลยครับเริ่มมันส์แล้ว

จัดให้ตามคำขอครับ

4. จงหาเศษที่เกิดจากการหาร $9^{50}$ ด้วย $7$

5. จงหาเศษที่เกิดจากการหาร $5^{36}$ ด้วย $13$

6. จงหาเศษที่เกิดจากการหาร $17^{75}$ ด้วย $19$

7. จงหาเลขโดดสองหลักสุดท้ายของ $9^{9^9}$

8. จงหาเลขโดดสามหลักสุดท้ายของ $7^{999}$

9. จงหาเศษที่เกิดจากการหาร $4444 ^{4444}$ ด้วย $9$

10. จงหาเศษที่เกิดจากการหาร $1^5 + 2^5 + 3^5 + ... + 99^5 +100^5$ ด้วย $4$

[Siren-Of-Step]

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

ถูกแล้วครับ

สะเพร่าเองซะงั้น

[Siren-Of-Step]

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

จัดให้ตามคำขอครับ

4. จงหาเศษที่เกิดจากการหาร $9^{50}$ ด้วย $7$

5. จงหาเศษที่เกิดจากการหาร $5^{36}$ ด้วย $13$

6. จงหาเศษที่เกิดจากการหาร $17^{75}$ ด้วย $19$

7. จงหาเลขโดดสองหลักสุดท้ายของ $9^{9^9}$

8. จงหาเลขโดดสามหลักสุดท้ายของ $7^{999}$

9. จงหาเศษที่เกิดจากการหาร $4444 ^{4444}$ ด้วย $9$

10. จงหาเศษที่เกิดจากการหาร $1^5 + 2^5 + 3^5 + ... + 99^5 +100^5$ ด้วย $4$

ข้อ 4. $9^6 \equiv 1 \pmod{7}$
$9^{50} \equiv 4 \pmod{7} $

ข้อ 5 $5^{12} \equiv 1 \pmod{13}$
$5^{36} \equiv 1 \pmod{13}$

ข้อ 6 $17^{18} \equiv 1 \pmod{19}$
$17^{75} \equiv 11 \pmod{19}$

ข้อ 7 Hint : mod 100

ข้อ 8 Hint : mod 1000

ข้อ 9 ไม่แน่ใจ แปลงมาเป็น $7^{4444} $
$7^8 \equiv 1 \pmod{9}$
$7^{4440} \equiv 1 \pmod{9}$
$7^{4444} \equiv 7 \pmod{9}$

ช้อ 10
ผมถึกเอาคิดแยกเอาเลย

[neem]

ขอบคุณมากๆค่ะ อยากรู้มานานแล้วว่า mod คืออะไร

ในที่สุดก็ได้รู้ ต้องขอบคุณมากๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆๆอีกทีค่ะ

[MiNd169]

เพิ่มเติม

แสดงวิธี หรือ บอกแนว ข้อนี้ให้หน่อยนะครับ

$5^{2008} + 2^{2010}$ หารด้วย $7^2$ เหลือเศษเท่าไร

ขอบคุณครับ

[กิตติ]

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

7. จงหาเลขโดดสองหลักสุดท้ายของ $9^{9^9}$

ข้อนี้เอาเรื่องเพราะทำให้ต้องคิดสองต่อ
จาก$9^{9^9}=9^{\overbrace{9.9...9}^{9 ตัว} }$
รอบแรกหาก่อนว่า$n$ที่ทำให้$9^n \equiv 1 \pmod{100} $จะได้ว่า$9^{10} \equiv 1 \pmod{100} $.....ไล่หาไปเรื่อยๆทีละตัวเอาจนถึงตัวที่10
รอบต่อมาเอา$n$ที่ได้ไปหาตัวลงท้ายของ$\overbrace{9.9...9}^{9 ตัว} $ เพื่อหาวนรอบลงท้าย จะได้ว่า$9^2 \equiv 1 \pmod{10} $
จะได้ว่า$9^9 \equiv 9 \pmod{10} $......เศษคือ$9$
เอาเศษที่ได้ไปแทนใน$9^{9^9}$ เพื่อหาสองตัวท้าย....คือ $9^{9^9} \equiv 9^9 \pmod{100}$
$9^9 \equiv 89 \pmod{100} $
ดังนั้นสองตัวท้ายของ$9^{9^9}$ คือ $89$

[banker]

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

ข้อนี้เอาเรื่องเพราะทำให้ต้องคิดสองต่อ
จาก$9^{9^9}=9^{\overbrace{9.9...9}^{9 ตัว} }$
รอบแรกหาก่อนว่า$n$ที่ทำให้$9^n \equiv 1 \pmod{100} $จะได้ว่า$9^{10} \equiv 1 \pmod{100} $.....ไล่หาไปเรื่อยๆทีละตัวเอาจนถึงตัวที่10
รอบต่อมาเอา$n$ที่ได้ไปหาตัวลงท้ายของ$\overbrace{9.9...9}^{9 ตัว} $ เพื่อหาวนรอบลงท้าย จะได้ว่า$9^2 \equiv 1 \pmod{10} $
จะได้ว่า$9^9 \equiv 9 \pmod{10} $......เศษคือ$9$
เอาเศษที่ได้ไปแทนใน$9^{9^9}$ เพื่อหาสองตัวท้าย....คือ $9^{9^9} \equiv 9^9 \pmod{100}$
$9^9 \equiv 89 \pmod{100} $
ดังนั้นสองตัวท้ายของ$9^{9^9}$ คือ $89$

ถูกต้องครับ

หรืออีกมุมมอง

$ \because 9^9 \equiv9 \pmod{10}$

$9^{9^9}= 9^{9+10k} $

$ \because (9^{10})^k \equiv 1 \pmod{100}$

$9^{9^9}\equiv 9^9 \times 9^{10k}\equiv 9^9 \times 1\pmod{100} \equiv 9^9 \pmod{100} \equiv89 \pmod{100}$

[Siren-Of-Step]

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

7. จงหาเลขโดดสองหลักสุดท้ายของ $9^{9^9}$

ข้อ 7

โดย จะหาเลขสองหลักสุดท้ายของ $9^{9^9}$
$9^3 \equiv 29 \pmod{100}$
$9^9 \equiv 29^3 \equiv 89 \pmod{100} $
จะไ้ด้ $9^{9^9} \equiv 89^9 \pmod{100}$
จะหาสองหลักสุดท้าย คิดเฉพาะ$ 9^9$ เท่านั้น
$9^9 \equiv 29^3 \equiv 89 \pmod{100} $

[banker]

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

10. จงหาเศษที่เกิดจากการหาร $1^5 + 2^5 + 3^5 + ... + 99^5 +100^5$ ด้วย $4$

$1^5 \equiv 1 \pmod{4} $

$2^5 \equiv 0 \pmod{4} $

$3^5 \equiv 3 \pmod{4} $

$4^5 \equiv 0 \pmod{4} $


$1^5+2^5+3^5 +4^5 \equiv 1+0+3+0 \pmod{4} \equiv4 \pmod{4} \equiv0 \pmod{4} $


$5^5 \equiv (4+1)^5\equiv 1 \pmod{4} $

$6^5 \equiv (4+2)^5 \equiv 2^5 \equiv 0 \pmod{4} $

$7^5 \equiv (4+3)^5\equiv 3 \pmod{4} $

$8^5 \equiv (2^5)^3\equiv 0 \pmod{4} $


$5^5+6^5+7^5 +8^5 \equiv 1+0+3+0 \pmod{4} \equiv4 \pmod{4} \equiv0 \pmod{4} $
.
.
.

$97^5 \equiv (96+1)^5\equiv 1 \pmod{4} $

$98^5 \equiv (96+2)^5 \equiv 2^5 \equiv 0 \pmod{4} $

$99^5 \equiv (96+3)^5\equiv 3 \pmod{4} $

$100^5 \equiv (2^5)^{20}\equiv 0 \pmod{4} $


$97^5+98^5+99^5 +100^5 \equiv 1+0+3+0 \pmod{4} \equiv4 \pmod{4} \equiv0 \pmod{4} $



ทุกๆ 4 จำนวน เศษรวมกันเป็น 0

$1^5 + 2^5 + 3^5 + ... + 99^5 +100^5 \equiv 0 \pmod{4}$


เศษที่เกิดจากการหาร $1^5 + 2^5 + 3^5 + ... + 99^5 +100^5$ ด้วย $4$ คือ $0$

[กิตติ]

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

8. จงหาเลขโดดสามหลักสุดท้ายของ $7^{999}$

ข้อนี้โหดมากเลยครับ.....หมดเวลาเป็นชั่วโมงเพื่อไล่หาค่า
$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$
โจทย์ข้อนี้กินแรงมากเลยครับ....ถ้าจะผิดก็ด้วยเบลอในตัวเลข โหดได้ใจเลยครับ
ไม่รู้ว่ามีทริคคิดให้สั้นกว่านี้ได้ไหม....หมดแรงเลยวันนี้

[banker]

วันสองวันก่อนเป็นวันหวยออก ก็เลยมานั่นขีดๆเขียนๆหาสูตรเลขท้ายสองตัวสามตัว

แล้วก็ได้สูตรเด็ดมาสองสูตร

เลขท้ายสองตัว $(1+10k)^n \equiv 1+10kn \pmod {100}$

เลขท้ายสามตัว $(1+100k)^n \equiv 1+100kn \pmod {1000} $


ที่มาที่ไป

ไม่ใช่การพิสูจน์ เพียงแต่จะเล่าว่า ขีดเขียนอย่างไร ถึงออกมาเป็นแบบนี้

จากการสังเกต

เพราะว่า $(1+10)^1 = 11 $ นั่นคือ $(1+10)^1 \equiv 1+ 10 \times 1 \equiv 11 \pmod {100}$

เพราะว่า $(1+10)^2 = 121 $ นั่นคือ $(1+10)^2 \equiv 1+ 10 \times 2 \equiv 21 \pmod {100}$

เพราะว่า $(1+10)^3 = 1331 $ นั่นคือ $(1+10)^3 \equiv 1+ 10 \times 3 \equiv 31 \pmod {100}$

เพราะว่า $(1+10)^4 = 14641 $ นั่นคือ $(1+10)^4 \equiv 1+ 10 \times 4 \equiv 41 \pmod {100}$

เพราะว่า $(1+10)^5 = 161051 $ นั่นคือ $(1+10)^5 \equiv 1+ 10 \times 5 \equiv 51 \pmod {100}$
.
.
.
เราจึงอนุมานว่า $(1+10)^n = 11^n $ นั่นคือ $(1+10)^n \equiv 1+ 10 \times n \equiv 1+10n \pmod {100}$

แทนที่จะเป็น 10 ถ้าใส่ $k$ เข้าไปเป็น $10k$ โดย $k$ และ $n$ เป็นจำนวนนับไปก่อน ก็จะได้สูตร

เลขท้ายสองตัวเท่ากับ $(1+10k)^n \equiv 1+10kn \pmod {100}$



ทำนองเดียวกัน ถ้าเป็นเลขท้ายสามตัว จากการสังเกต

เพราะว่า $(1+100)^1 = 101 $ นั่นคือ $(1+100)^1 \equiv 1+ 100 \times 1 \equiv101 \pmod {1000}$

เพราะว่า $(1+100)^2 = 10201 $ นั่นคือ $(1+100)^2 \equiv 1+ 100\times 2 \equiv 201 \pmod {1000}$

เพราะว่า $(1+100)^3 = 1030301 $ นั่นคือ $(1+100)^3 \equiv 1+ 100 \times 3 \equiv 301 \pmod {1000}$

เพราะว่า $(1+100)^4 = 104060401 $ นั่นคือ $(1+100)^4 \equiv 1+ 100 \times 4 \equiv 401 \pmod {1000}$

เพราะว่า $(1+100)^5 = 10510100501 $ นั่นคือ $(1+100)^5 \equiv 1+ 100 \times 5 \equiv 501 \pmod {1000}$
.
.
.
เราจึงอนุมานว่า $(1+100)^n = 101^n $ นั่นคือ $(1+100)^n \equiv 1+ 100 \times n \equiv 1+100n

\pmod {1000}$

แทนที่จะเป็น 100 ถ้าใส่ $k$ เข้าไปเป็น $100k$ โดย $k$ และ $n$ เป็นจำนวนนับไปก่อน ก็จะได้

สูตร

เลขท้ายสามตัวเท่ากับ $(1+100k)^n \equiv 1+100kn \pmod {1000}$


มาลองทดสอบกันดู

$9^{10} = 3486784401$

ใช้สูตร สองหลักสุดท้ายของ $9^{10}$ คือ $(9^2)^{5} \equiv (81)^5 \equiv (1+80)^5 \equiv

1+80\times5 \equiv 01\pmod {100}$

$9^{75} = 9(9)^{74} =9(81)^{37} \equiv 9(1+80)^{37} \equiv 9(1+80\times37) \equiv 9(2961)

\equiv 26640 \equiv 40 \pmod {100}$


ตัวอย่าง 7. จงหาเลขโดดสองหลักสุดท้ายของ $9^{9^9}$

เพราะว่า $9^9 = 387420489$

$9^{9^9} = 9^{387420489} = 9 \times 9^{387420488} $
$\equiv 9(9^{387420488}) \equiv 9(81)^

{193710244} $
$\equiv 9(1+80)^{193710244} \equiv 9(1+80\times193710244) $
$\equiv 139471375689

\equiv 89 \pmod {100}$


8. จงหาเลขโดดสามหลักสุดท้ายของ $7^{999}$

$7^{999} = 7^{3} (7^{996}) = 7^{3} (7^4)^{249} = 7^{3} (2401)^{249}= 7^{3} (1+2400)^{249}$

$\equiv 7^3(1+2400\times249) \pmod {1000}$

$\equiv 7^3(601) \pmod {1000}$

$\equiv 206143 \pmod {1000}$

$\equiv 143 \pmod {1000}$


มันเป็นแค่การสังเกตของผม คงไม่ใข่ทฤษฎีบทอะไร

ใช้ได้กับบางจำนวนที่ยกกำลังแล้วทำให้เลขลงท้ายด้วย $1$ หรือ $01$ ได้

จะช่วยย่นเวลาในการหาเลขลงท้าย สองตัว หรือเลขลงท้ายสามตัว


ทำแบบฝึกหัดมากๆ แล้วความรู้จะแตกฉานเอง

[กิตติ]

ที่คุณอาBankerเขียนให้ดูนั้นน่าจะพอขยายความได้จาก
$(1+10k)^n \equiv 1+10kn \pmod {100}$

$(1+10k)^n =\binom{n}{0} .1^n.(10k)^0+\binom{n}{1} .1^{n-1}.(10k)^1+\binom{n}{2} .1^{n-2}.(10k)^2+\binom{n}{3} .1^{n-3}.(10k)^3+...+\binom{n}{n-1} .1^{1}.(10k)^{n-1}+\binom{n}{n} .1^0.(10k)^n$

$(1+10k)^n =1+n(10k)+\binom{n}{2} .1.(100)k^2+\binom{n}{3} (1000)k^3+...+\binom{n}{n-1} .(10)^{n-1}k^{n-1}+(10)^nk^n$

ถ้าลองเขียนในรูปการหารด้วย100 จะได้ว่า$(1+10k)^n \equiv 1+10nk \pmod{100} $

$(1+100k)^n =\binom{n}{0} .1^n.(100k)^0+\binom{n}{1} .1^{n-1}.(100k)^1+\binom{n}{2} .1^{n-2}.(100k)^2+\binom{n}{3} .1^{n-3}.(100k)^3+...+\binom{n}{n-1} .1^{1}.(100k)^{n-1}+\binom{n}{n} .1^0.(100k)^n$

$(1+100k)^n =1+n(100k)+\binom{n}{2} .1.(10000)k^2+\binom{n}{3} (10^6)k^3+...+\binom{n}{n-1} .(100)^{n-1}k^{n-1}+(100)^nk^n$

ถ้าลองเขียนในรูปการหารด้วย1000 จะได้ว่า$(1+100k)^n \equiv 1+100nk \pmod{1000} $

ดังนั้นสิ่งที่คุณอาbankerบอกว่าสังเกตแล้วจริงๆดูแบบนี้ก็ได้เหมือนกันครับ.....ข้อสังเกตของคุณอาสุดยอดเลยครับ

[คusักคณิm]

ขอบคุณคุณลุงมาdนะครับ
ที่ทำให้ผมใช้ mod เป็นแล้ว ^^