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

[MiNd169]

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

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

ขอบคุณครับ

(ไปไม่ค่อยเป็นเลย ตัวหาร ยกกำลังแล้ว เยอะเนี่ย)

[Xx GAMMA xX]

คิดเศษจากการหาร$5^{2008}$ด้วย$7^2$ก่อนนะครับ
$5^{42} ≡ 1 (mod49)$
$(5^{42})^{47} ≡ 1 (mod49)$
$5^{1974}$ ≡ 1 (mod49)
$5^{2008}$ ≡ $3^{34}$ (mod49)
จาก$5^4$ ≡ 625 (mod49)
$5^4$ ≡ -12 (mod49)
$5^8$ ≡ 144 (mod49)
$5^8$ ≡ -3 (mod49)
$5^{32}$ ≡ 81 (mod49)
$5^{32}$ ≡ -17 (mod49)
$5^{34}$ ≡ -425 (mod49)
$5^{34}$ ≡ 16 (mod49)
ดังนั้น$5^{2008}$ ≡ $5^{34}$ (mod49)
$5^{2008}$ ≡ 16 (mod49)

หาเศษจากการหาร $2^{2010}$ ด้วย $7^2$
$2^{42}$ ≡ 1 (mod49)
$2^{1974}$ ≡ 1 (mod49)
$2^{2010}$ ≡ $2^{36}$ (mod49)
จาก$2^6$ ≡ 64 (mod49)
$2^6$ ≡ 15 (mod49)
$2^{12}$ ≡ 225 (mod49)
$2^{12}$ ≡ -20 (mod49)
$2^{24}$ ≡ 400 (mod49)
$2^{24}$ ≡ 8 (mod49)
($2^{24}$)($2^{12}$) ≡ -160 (mod49)
$2^{36}$ ≡ -160 (mod49)
$2^{36}$ ≡ 36 (mod49)
ดังนั้น$2^{2010}$ ≡ $2^{36}$ (mod49)
$2^{2010}$ ≡ 36 (mod49)
สรุป($5^{2008}$)+($2^{2010}$) ≡ 16+36 (mod49)
($5^{2008}$)+($2^{2010}$) ≡ 52 (mod49)
ผิดตรงไหนบอกด้วยนะครับ
ปล.ขอโทษผู้อ่านด้วยครับ(ใช้Latexไม่เป็น)

[MiNd169]

เรารู้ได้อย่างไรครับว่า

$5^{42} ≡ 1 (mod49)$

$2^{42} ≡ 1 (mod49)$

ในช่วงแรกน่ะครับ

ปล.ขอโทษผู้อ่านด้วยครับ(ใช้Latexไม่เป็น)
ใช้ $$ ครอบข้อความครับ ส่วนเลขชี้กำลังใช้ {ตัวเลข} อีกที

[Onasdi]

http://en.wikipedia.org/wiki/Euler's_theorem

[Xx GAMMA xX]

ใช้ทฤษฎีของ Fermat-Euler theorem เลยครับว่า
$a^{Ø(n)}$ ≡ 1 (modn)ครับ
ข้อนี้ n=$7^2$
ดังนั้น Ø(n) = Ø($7^2$) = $7^2$-$7^1$ = 49-7 = 42ครับ

ใช้ $$ ครอบข้อความครับ ส่วนเลขชี้กำลังใช้ {ตัวเลข} อีกที
ขอบคุณมากครับแต่ทำไมผมทำแล้วยังเป็นอย่างนี้อยู่เลยครับ

[nongtum]

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

$\begin{array}{rcl}
5^{2008}+2^{2010} &=& (7-2)^{2008}+4\cdot2^{2008} \pmod{49} \\
&\equiv& -2008\cdot 7\cdot 2^{2007}+5\cdot2^{2008} \pmod{49}\\
&\equiv& 7\cdot 2^{2007}+10\cdot2^{2007} \pmod{49}\\
&\equiv& 17\cdot 2^{12} \pmod{49}\\
&\equiv& 17\cdot 15^2 \pmod{49}\\
&\equiv& 51\cdot 25 \cdot 3 \pmod{49}\\
&\equiv& (2\cdot 25) \cdot 3 \pmod{49}\\
&\equiv& 3 \pmod{49}\\
\end{array}$

[กิตติ]

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

($5^{2008}$)+($2^{2010}$) ≡ 52 (mod49)

จริงๆแล้วมันคือ $5^{2008}+2^{2010} \equiv 3 \pmod{49} $
คำตอบน่าจะเป็นเศษ $3$

ขอบคุณมากครับที่ช่วยนำความรู้เรื่องEuler's theoremมาช่วยหาค่าที่เหลือเศษ1จากการหาร ช่วยย่นระยะเวลาไปได้อีกโขเลย

[neem]

#2 08 กรกฎาคม 2010, 17:11
banker
เซียนกระบี่ วันที่สมัครสมาชิก: 24 มกราคม 2002
ข้อความ: 3,930




--------------------------------------------------------------------------------

นั่ง Time Machine ไปยุคประถม

ถ้าถามว่า 5 หารด้วย 2 เหลือเศษเท่าไร เด็กๆก็ตอบได้ว่า เหลือเศษ 1

ถามว่า 289 หารด้วย 13 เหลือเศษเท่าไร

เด็กก็จะตั้งหารยาว ได้ผลลัพธ์เป็น 22 เหลือเศษ 3

เขียนในรูปเศษส่วน จะได้ 13289=1322(13)+3=1322(13)+313

จะเห็นว่า 1322(13) ตัวเศษ มี 13 เป็นพหุคูณ หรือตัวร่วม ทำให้ หารด้วย 13 ลงตัว และมี 313 เศษคือ 3


แต่โจทย์ไม่ง่ายๆแบบข้างต้น มักเป็นการหารเลขยกกำลัง เช่น

210 หารด้วย 5 เหลือเศษ เท่าไร

จงหาเศษเหลือจากการหาร 3100 ด้วย 7

เศษเหลือจาการหาร 171000 ด้วย 13 เป็นเท่าไร

แบบนี้ถ้าทำแบบตั้งหารยาว คงยุ่งยากและยาวมากๆ

เราจะหาแนวทางในการหาเศษเหลือของตัวเลข xn ที่หารด้วย p

ค่อยๆทำความเข้าใจตัวอย่างต่อไปนี้นะครับ

----------------------------------------------------------------------------------

=(050)550−(150)549+(250)548−(350)547+...−(4950)51+1

เพราะว่า 5 หาร (k50)550−k ลงตัวทุกค่า k=0,1,...,49

คืออะไรคะ ช่วยอธิบายหน่อยค่ะ

[Onasdi]

ใช้ทฤษฎีบททวินามครับ

$(a+b)^n=\dbinom{n}{0}a^n+\dbinom{n}{1}a^{n-1}b+\dbinom{n}{2}a^{n-2}b^2+\dots+\dbinom{n}{n}b^n$ สำหรับจำนวนนับ $n$

โดยที่ $\displaystyle{\dbinom{r}{s}=\frac{r!}{(r-s)!s!}}$ สำหรับจำนวนนับ $r\ge s$

เช่น $(a+b)^3=\dbinom{3}{0}a^3+\dbinom{3}{1}a^2 b+\dbinom{3}{2}ab^2+\dbinom{3}{3}b^3=a^3+3a^2b+3ab^2+b^3$

[!!!-Argentum-!!!]

หยิบมาจาก TMO 1 ครับ ยังไม่มีใครเฉลย

ข้อ 15 วันแรก

จงหาจำนวนเต็ม $n$ ที่มากที่สุดซึ่ง $n$ $\leqslant$ $2004$ และ $3^{3n+3}$ - 27 หารด้วย 169 ลงตัว

[~ArT_Ty~]

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

หยิบมาจาก TMO 1 ครับ ยังไม่มีใครเฉลย

ข้อ 15 วันแรก

จงหาจำนวนเต็ม $n$ ที่มากที่สุดซึ่ง $n$ $\leqslant$ $2004$ และ $3^{3n+3}$ - 27 หารด้วย 169 ลงตัว

จัดรูปจะได้

$=27(3^{3n}-1)$

$=27(3^3-1)(3^{3n-3}+3^{3n-6}+...+3^3+1)$

$=27(26)(3^{3n-3}+3^{3n-6}+...+3^3+1)$

$\therefore 13\left|\,3^{3n-3}+3^{3n-6}+...+3^3+1\right. $

เห็นได้โดยง่ายว่า $3^{3n}\equiv 1(mod 13)$

$\therefore 3^{3n-3}+3^{3n-6}+...+3^3+1\equiv n(mod13) $

$\therefore 13\left|\,n\right. $

$\therefore n$ มากที่สุดคือ $n=2002$

[หยินหยาง]

ยังไม่ถูกครับ

[~ArT_Ty~]

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

ยังไม่ถูกครับ

แก้แล้วครับ

ผิดนิดเดียวเอง ขอโทษครับ

ผิดตรงไหนช่วยบอกด้วยนะครับ

[หยินหยาง]

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

แก้แล้วครับ

ผิดนิดเดียวเอง ขอโทษครับ

ผิดตรงไหนช่วยบอกด้วยนะครับ

ไม่ต้องบอกครับ ก็แก้แล้วนี่ครับ

[กิตติ]

จงหาจำนวนเต็ม $n$ ที่มากที่สุดซึ่ง $n$ $\leqslant$ $2004$ และ $3^{3n+3}$ - 27 หารด้วย 169 ลงตัว

$3^{3n+3}$ - 27 หารด้วย 169 ลงตัว ความหมายเดียวกับ $3^{3n+3}$หารด้วย169 เหลือเศษ 27
$3^{3n+3} \equiv 27 \pmod{169} $
ผมลองใช้Euler's theoremเล่นๆ....อ่านจากลิ้งค์ข้างต้นแล้วลองทำดู
ผมคิดได้ค่า$n=1976$
$\phi (169 ) = 169(1-\frac{1}{13}) = 12\times 13 = 156$
จาก $x \equiv y \pmod{\phi (n)} $ แล้ว $a^x \equiv a^y \pmod{n} $ เมื่อ $a$ กับ $n$ เป็นco-prime
$159 \equiv 3 \pmod{156} \rightarrow 3^{159} \equiv 3^3 \pmod{169} $
และจาก$156 \equiv 0 \pmod{156} \rightarrow 3^{156} \equiv 1 \pmod{169} $
$3^{159}\times 3^{156} \equiv 3^3 \pmod{169} \rightarrow 3^{159+156} \equiv 3^3 \pmod{169} $
จะได้ว่า$159+156m =3(n+1) \rightarrow 53+52m=n+1$
$n=52(m+1)\rightarrow m=\frac{n}{52}-1 $ เมื่อ $\ n \leqslant 2004$
ได้ค่า $n$ ที่มากที่สุดที่ยังทำให้เป็น $m$ จำนวนเต็มอยู่คือ $1976$
ไม่รู้ว่าผมงงตรงไหนหรือเปล่า.....