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

[banker]

ที่โพสต์กระทู้นี้ ไม่ได้แปลว่า ผมเก่งกาจ หรือเป็นเซียน

แต่เป็นเพราะมักมีกระทู้ถามว่า mod คืออะไร อยู่บ่อยๆ

และมักจะมีคำตอบว่า ให้ไปอ่านหนังสือเล่มนี้ เล่มโน้น

อย่างหนังสือ สอวน ทฤษฎีจำนวน

ไปอ่านแล้วก็หงายหลังออกมา ไม่รู้เรื่องเลยครับ

จนวันหนึ่งไปอ่านที่อาจารย์ ดำรงค์ ทิพย์โยธาเขียนไว้

อ่านแล้วเข้าใจพื้นฐานของการหาเศษเหลือ

จึงนำมาเรียบเรียงใหม่ แล้วมาโพสต์

ด้วยความหวังว่า ผู้ที่เคยได้ยินเรื่อง mod จะพอเข้าใจได้บ้างว่า mod คืออะไร แล้วหาได้อย่างไร

[banker]

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

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

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

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

เขียนในรูปเศษส่วน จะได้ $\frac{289}{13} = \frac{22(13) +3}{13} = \frac{22(13) }{13} + \frac{3}{13}$

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


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

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

จงหาเศษเหลือจากการหาร $3^{100}$ ด้วย $7$

เศษเหลือจาการหาร $17^{1000}$ ด้วย $13$ เป็นเท่าไร

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

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

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

[banker]

ตัวอย่างที่ 1

เศษเหลือที่ได้จากการหาร $2^{100}$ ด้วย 5 เท่ากับเท่าใด

วิธีที่ 1
เพราะว่า $2^{100} = (2^4)^{25}= (16)^{25} =...6$

เพราะฉะนั้นหลักหน่วยของ $2^{100}$ เป็นเลข $6$

สรุป เศษเหลือที่ได้จากการหาร $2^{100}$ ด้วย $5$ มีค่าเท่ากับ $1$


วิธีที่ 2

$2^{100}= (2^2)^{50} = 4^{50}= (5-1)^{50}$

$=\binom{50}{0}5^{50} - \binom{50}{1}5^{49} + \binom{50}{2}5^{48} - \binom

{50}{3}5^{47} + ... - \binom{50}{49}5^{1}+1 $

เพราะว่า $5$ หาร $\binom{50}{k}5^{50-k}$ ลงตัวทุกค่า $ k=0,1,...,49$

เพราะฉะนั้น $5$ หาร $2^{100}$ เหลือเศษ $1$

หมายเหตุ
การแก้ปัญญาข้อนี้วิธีที่ $1$ เป็นวิธีที่เข้าใจได้ง่ายกว่าวิธีที่ $2$ แต่เมื่อ

ต้องการหาในกรณีที่ตัวหารไม่ใช่เลข $5$ หรือ $10$ จะพบว่าวิธีที่ $2$ จะดีกว่า

ถึงตรงนี้ ก็ไปหาความรู้เรื่องทฤษฎีทวินามมาอ่าน หรืออย่างน้อย จำรูปแบบนี้ไว้ก่อนก็ได้

[banker]

ตัวอย่าง 2.

เศษเหลือที่ได้จากการหาร $10^{ 10}$ ด้วย $7$ เท่ากับเท่าใด

วิธีทำ

$ \because \ \ 10^{10} = (7+3)^{10}$

$ \ \ \ \ \ \ \ \ \ = \binom{10}{0}7^{10}\cdot 3^0 + \binom{10}{1}7^{9}\cdot 3^1 + ...+

\binom{10}{9}7^{1}\cdot 3^9 + 3^{10}$

เพราะฉะนั้นเศษเหลือที่ได้จากการหาร $10^{10}$ ด้วย $7$ ต้องเท่ากับเศษเหลือจากการหาร $3^{10}$ ด้วย $7$

แต่เพราะว่า $3^{10} =(3^2)^5 = 9^5 = (7+2)^5$

$= \binom{5}{0}7^{5}\cdot 2^0 + \binom{5}{1}7^{4} \cdot 2^1 + ... + \binom{5}{4}7^{1} \cdot

2^4 + 2^5$

เพราะฉะนั้นเศษเหลือที่ได้จากการหาร $3^{10}$ ด้วย $7$ ต้องเท่ากับเศษเหลือที่ได้จากการหาร $2^5$ ด้วย $7$

เพราะว่า $2^5 = 32 $ หารด้วย $7$ เหลือเศษ $4$

สรุป $10^{10}$ หารด้วย $7$ เหลือเศษ $4$

ถึงตรงนี้พอได้แนวคิดบ้างหรือยังครับ

ถ้าอย่างนั้น ก็มาดูตัวอย่างต่อไป

[banker]

ตัวอย่างที่ 3.
เศษเหลือที่ได้จากการหาร $10^{100} \ $ ด้วย $ \ 13$ เท่ากับเท่าใด


วิธีทำ

$10^{100} =(10^2)^{50} =(100)^{50} =[ 7(13)+9]^{50}$

เพราะว่าเศษเหลือจากการหาร $10^{100}$ ด้วย $13$ เท่ากับเศษเหลือที่ได้จากการหาร $9^{50}$ ด้วย $13$

$ \ \ \ 9^{50} = (9^2)^{25} =(81)^{25} =(6(13)+3)^{25}$


เพราะฉะนั้นเศษเหลือที่ได้จากการหาร $9^{50}$ ด้วย $13$ ต้องเท่ากับเศษเหลือที่ได้จากการหาร $3^{25} $ ด้วย $13$


$ \ \ \ \ 3^{25} = (3^5)^5 =(243)^5 =(18(13)+9)^5$


เศษเหลือจากการหาร $3^{25}$ ด้วย $13$ เท่ากับเศษเหลือจากการหาร $9^5$ ด้วย $13$


$ \ \ \ \ \ \ 9^5 = (3^2)^5 =(3^5)^2 =(243)^2 =(18(13)+9)^2$

เศษเหลือจากการหาร $9^5$ ด้วย $13$ เท่ากับเศษเหลือจากการหาร $9^2$ ด้วย $13$

เพราะว่า $9^2 = 81$ หารด้วย $13$ เหลือเศษ $3$

เพราะฉะนั้น $10^{100}$ หารด้วย $13$ เหลือเศษ $3$


เป็นไงครับ เริ่มมันแล้วหรือยัง :haha:

[banker]

มาดูตัวอย่างต่อไป ตอนนี้อาจต้องยาวหน่อย แต่พอถึงเรื่อง mod จะค่อยๆสั้น แล้วก็สั้นอีก

ใจเย็นๆ เอาให้คล่องก่อน แล้วพื้นฐานจะแน่น :D

ตัวอย่างที่ 4.

เศษเหลือที่ได้จากการหาร $2^{100}$ ด้วย $7$ เท่ากับเท่าใด


วิธีทำ

$2^{100} = (2^4)^{25} = (16)^{25} = (14+2)^{25}$

$ \ \ \ \ \ = \binom{25}{0}14^{25} \cdot 2^0 + \binom{25}{1}14^{24} \cdot 2^1 + ... + \binom

{25}{24}14^{1} \cdot 2^{24} +2^{25}$


เพราะว่า $7$ หาร $ \binom{25}{0}14^{25} \cdot 2^0 + \binom{25}{1}14^{24} \cdot 2^1 + ... + \binom{25}

{24}14^{1} \cdot 2^{24}$ ลงตัว

เพราะฉะนั้นเศษเหลือที่ได้จากการหาร $2^{100}$ ด้วย $7$ ต้องเท่ากับเศษที่ได้จากการหาร $2^{25}$ ด้วย $7$


$2^{25} = (2^5)^5 = 32^5 = (28+4)^5$

$ \ \ \ \ = \binom{5}{0}28^{5} \cdot 4^{0} + \binom{5}{1}28^{4} \cdot 4^{1} + ... + \binom{5}

{4}28^{1} \cdot 4^{4}+4^5$

เพราะว่า $7$ หาร $\binom{5}{0}28^{5} \cdot 4^{0} + \binom{5}{1}28^{4} \cdot 4^{1} + ... + \binom{5}

{1}28^{1} \cdot 4^{4}$ ลงตัว

เพราะฉะนั้นเศษเหลือจากการหาร $2^{25}$ ด้วย $7$ ต้องเท่ากับเศษเหลือที่ได้จากการหาร $4^5$ ด้วย $7$

$4^5 = (2^2)^5 = (2^5)^2 = (32)^2 = (28+4)^2 =28^2+2(28)(4)+4^2$

$ \ \ \ \ \ \ \ = 28^2+2(28)(4)+16$

$ \ \ \ \ \ \ \ = 28^2+2(28)(4)+14+2$

ดังนั้น $7$ หาร $4^5$ เหลือเศษ $2$

สรุป $7$ หาร $2^{100}$ เหลือเศษ $2$



เหตุผลสำคัญที่เราจะอ้างใช้ในโอกาสต่อไป คือ
ถ้า $x^n= (kp+r)^n$ แล้วเศษเหลือที่ได้จากการหาร $x^n$ ด้วย $p$ เท่ากับเศษเหลือ จากการหาร $r^n$ ด้วย $p$

ข้อพิสูจน์ จากการกระจายทวินาม
$(a+b)^n = \binom{n}{0}a^n+ \binom{n}{1}a^{n-1} b + \binom{n}{2}a^{n-2} b^2 +
... + \binom{n}{n} b^n$


ดั้งนั้น
$(kp+r)^n = \binom{n}{0}(kp)^n+ \binom{n}{1}(kp)^{n-1}r + ...+ \binom{n}{n-1}(kp)r^{n-1} +

\binom{n}{n}r^n$

แต่เพราะว่า $p$ หาร $\binom{n}{i}(kp)^{n-i}r^i$ ลงตัวทุกค่า $ i = 0,1,2,...,n-1$

เพราะฉะนั้น $p$ หาร $ \binom{n}{0}(kp)^n+ \binom{n}{1}(kp)^{n-1}r + ...+ \binom{n}{n-1}(kp)r^{n-1} $

ลงตัว

ดังนั้นเศษเหลือจากการหาร $ \ (kp+r)^n$ ด้วย $p$ ต้องเท่ากับเศษเหลือจากการหาร $r^n$ ด้วย $p$

ต่อนี้ไป เราจะไม่เขียนยาวๆแบบนี้อีกแล้ว

แต่จะอ้างเหตุผลข้างต้นแทน

ดูตัวอย่างต่อไปเลยครับ

[banker]

ตัวอย่างที่ 5.

เศษเหลือจากการหาร $2^{1000}$ ด้วย $13$ เท่ากับเท่าใด


วิธีทำ

$2^{1000} = (2^5)^{200} = (32)^{200} = (26+6)^{200} = (2(13)+6)^{200}$

$6^{200} = (6^2){100} =(36){100} =(26+10)^{100} =(2(13)+10)^{100}$

$10^{100} = (10^2)^{50} =(100)^{50} =(7(13)+9)^{50}$

$9^{50} = 81^{25} = (6(13)+3)^{25}$

$3^{25} = (3^5)^5 = (243)^5 = (18(13)+9)^5$

$9^5 = 59049$

เพราะว่า $59049$ หารด้วย $3$ เหลือเศษ $3$

โดยการอ้างเหตุผลข้างต้น
เศษเหลือจากการหาร $2^{1000}$ ด้วย $13$
= เศษเหลือจากการหาร $6^{200}$ ด้วย $13$
= เศษเหลือจากการหาร $10^{100}$ ด้วย $13$
= เศษเหลือจากการหาร $9^{50}$ ด้วย $13$
= เศษเหลือจากการหาร $3^{25}$ ด้วย $13$
= เศษเหลือจากการหาร $9^5$ ด้วย $13$
= เศษเหลือจากการหาร $59049$ ด้วย $13$
= $3$


หมายเหตุ การหาเศษเหลือแบบนี้จะทำได้เร็วหรือช้าขึ้นอยู่กับผู้ฝึก
จะแบ่งตัวเลขออกเป็นผลบวกหรือการแบ่งกำลัง (ฝึกบ่อยๆ จะมองออกเอง) ซึ่งอาจทำได้หลายวิธีเช่น

$2^{1000} = (2^8)^{125} =(256)^{125} =(19(13)+9)^{125}$

$9^{125} = 3^{250} =(3^5)^{50} =(243)^{50} =(18(13)+9)^{50}$

$9^{50} = (9^2)^{25} =81^{25} =(6(13)+3)^{25}$

$3^{25} = (243)^5 = (18(13)+9)^5$

$9^5 = 59049$

ดังนั้นจะได้เศษเหลือของ $2^{1000}$ หารด้วย $13$ เท่ากับ $3$ เหมือนกัน



แล้วเมื่อไรจะเข้าเรื่อง mod เสียที :haha:

ใจเย็นๆ ตัวอย่างข้างล่างนี้ เราก็จะเข้าเรื่อง mod เสียที :haha:

[banker]

ตัวอย่างที่ 6.

เศษเหลือจากการหาร $7^{2541}$ ด้วย $4$ เท่ากับเท่าใด


วิธีทำ
$ \ \ \ \ \ \ \ \ 7^{2541}= (4+3)^{2541}$

$ \ \ \ \ \ \ \ \ 3^{2541} = (3^3)^{847} =(27)^{847} =(6(4)+3)^{847}$

$ \ \ \ \ \ \ \ \ 3^{847} = (3^7)^{121} =(2187)^{121} =(546(4)+3)^{121}$

$ \ \ \ \ \ \ \ \ 3^{121} =(3^{11})^{11} = (177147)^{11}

= (44286(4)+3)^{11}$

$ \ \ \ \ \ \ \ \ 3^{11} = 177147$ หารด้วย $4$ เหลือเศษ $3$


เศษจากการหาร $7^{2541}$ ด้วย $4$
= เศษจากการหาร $3^{2541}$ ด้วย $4$
= เศษจากการหาร $3^{847}$ ด้วย $4$
= เศษจากการหาร $3^{121}$ ด้วย $4$
= เศษจากการหาร $3^{11}$ ด้วย $4$
= $3$



ในหลักสูตรเกี่ยวกับระบบจำนวนมีการกำหนดสัญลักษณ์ $a \equiv b \pmod{m} $

หมายความว่า $a-b$ หารด้วย $m$ ลงตัว ตัวอย่างเช่น

$10-1$ หารด้วย $3$ ลงตัว เพราะฉะนั้น $10 \equiv 1 \pmod{3} $

$17-5$ หารด้วย $12$ ลงตัว เพราะฉะนั้น $17 \equiv 5 \pmod{12} $

$100-50$ หารด้วย $10$ ลงตัว เพราะฉะนั้น $100 \equiv 50 \pmod{10} $


ในกรณีที่ $0\leqslant b < m$ และ $a \equiv b \pmod{m} $

จะได้ว่า $b$ เป็นเศษเหลือที่ได้จากการหาร $a$ ด้วย $m$

โดยการใช้สัญลักษณ์ $a \equiv b \pmod{m} $ จะได้ว่า

$7^{2541} \pmod{4} \equiv 3^{2541} \pmod{4} \equiv 3^{847} \pmod{4} \equiv 3^{121} \pmod{4} \equiv 3^{11}\pmod{4} $

$ \equiv 177147\pmod{4} $

$ \equiv 3 \pmod{4} $

ต่อไปพิจารณาเศษเหลือที่ได้จากการหาร$(m+b)^n$ ด้วย $m$ โดยการกระจายทวินาม

$(m+b)^n = \binom{n}{0}mn+\binom{n}{1}m^{n-1} b+...+ \binom{n}{n-1}mb^{n-1}+b^n$

ดังนั้น $(m+b)^n-b^n =\binom{n}{0}m^n+\binom{n}{1}m^{n-1} b+...+ \binom{n}{n-1}mb^{n-1}$

เพราะว่า $m$ หาร $\binom{n}{0}m^n+\binom{n}{1}m^{n-1} b+...+ \binom{n}{n-1}mb^{n-1}$ ลงตัว

เพราะฉะนั้น $m$ หาร $(m+b)^n-b^n$ ลงตัว

สรุป $(m+b)^n \equiv b^n \ (mod \ m) $

[banker]

ตัวอย่างที่ 7.

การหาเศษเหลือที่ได้จากการหาร $2^{1000}$ ด้วย $13$


เพราะว่า $ 2^{1000} =(2^4)^{250} =16^{250} =(13+3)^{250}$

เพราะฉะนั้น $2^{1000} \equiv (13+3)^{250} \pmod {13} \equiv 3^{250} \pmod {13}$


ในทำนองเดียวกันกับการพิสูจน์ว่า $(m+b)^n \equiv b^n \pmod{m} $

จะได้ว่า $(km+b)^n \equiv b^n \pmod{m} $

นั้นคือ ถ้า $m$ หาร $A$ ลงตัว แล้ว $(A+b)^n \equiv b^n \pmod{m} $

เพราะว่า $3^{250} = (3^5)^{50} = (243)^{50} =(18(13))+9)^{50}$

เพราะฉะนั้น $3^{250} \pmod {13} \equiv (18(13+9))^{50} \pmod {13}$

$\equiv 9^{50} \pmod {13} \ \ \ \ \ \ \ \ \ \equiv (9^2)^{25}

\pmod {13} $

$\equiv 81^{25} \pmod {13} \ \ \ \ \ \ \ \ \ \equiv (6(13)

+3)^{25} \pmod {13}$

$\equiv 3^{25} \pmod {13} \ \ \ \ \ \ \ \ \ \equiv (3^5)

^5 \pmod {13} $

$\equiv (18(13)+9)^5 \pmod {13} \ \ \ \ \ \ \ \ \ \equiv9^5 \pmod

{13} $

$\equiv 3^{10} \pmod {13} \ \ \ \ \ \ \ \ \ \equiv(3^5)

^2 \pmod {13} $

$\equiv 9^2 \pmod {13} \ \ \ \ \ \ \ \ \ \equiv 81

\pmod {13} $

$\equiv 3 \pmod {13} $


สรุป $2^{1000} \equiv 3 \pmod {13} $

นั้นคือ $2^{1000}$ หารด้วย $13$ เหลือเศษ $3$



ต่อไปเราจะหาเหตุผลที่สำคัญซึ่งจะช่วยในการหาเศษเหลือที่ได้จากการหารได้ง่ายขึ้น

ก่อนอื่นขอให้ดูจากตัวอย่างง่ายๆ ดังนี้

$14$ หารด้วย $3$ เหลือเศษ $2$
$11$ หารด้วย $3$ เหลือเศษ $2$

$(14)(11) = 154$ หารด้วย $3$ เหลือเศษ $1$

เศษที่เหลือจากการหารด้วย $3$ จากสองสมการข้างต้นคูณกัน

$(2)(2) = 4$ หารด้วย $3$ อีกครั้ง จะเหลือเศษ $1$

สรุปด้วยการเขียนในรูปแบบสัญลักษณ์

$14 \equiv 2 \pmod {3} $
$11 \equiv 2 \pmod {3} $

$ (14)(11) =(2)(2) \pmod {3} \equiv 4 \pmod {3} \equiv 1 \pmod {3}$

ในกรณีทั่วไปเราสรุปเป็นทฤษฎีบทได้ดังนี้

ทฤษฎีบท 1

$a,b,c,d $ เป็นจำนวนเต็ม, $m$ เป็นจำนวนเต็มบวก

ถ้า $a \equiv b \pmod {m }$ และ $c \equiv d \pmod {m }$ แล้ว


$ac \equiv bd \pmod {m }$
$a - c \equiv ( b - d ) \pmod {m }$
$a + c \equiv ( b + d) \pmod {m }$

ข้อพิสูจน์

$a \equiv b \pmod {m }, \ \ c \equiv d \pmod {m }$

$a = mk + b, \ \ c = ml + d$

$ a - c = mk + b - ml - d$

$ = m(k - 1) + ( b - d )$


เพราะฉะนั้น $m$ หาร $a - c$ เหลือเศษ $ b -d$

นั้นคือ $a- c \equiv (b - d ) \pmod {m }$

ในทำนองเดียวกัน $a + c \equiv ( b + d ) \pmod {m }$


เพราะว่า $ac = ( mk + b) (ml + d )$

$= m^2 kl + mkd + mbl + bd$

$= m ( mkl + kd + bl ) + bd$

เพราะฉะนั้น $m$ หาร $ac$ เหลือเศษ $bd$

นั้นคือ $ac \equiv bd \pmod {m }$

หมายเหตุ ผลจากทฤษฎีบทจะได้ว่า

ถ้า $a \equiv b \pmod {m } $ แล้ว $ \ a^n \equiv b^n \pmod {m }$ ทุกค่า $n$ ที่เป็นจำนวนเต็ม

ผลจากทฤษฎีบท 1 นี้จะช่วยให้การหาเศษเหลือง่ายขึ้น

เป็นอย่างไรบ้างครับ มึนไหม

ถ้ายังมึนก็ย้อนกลับไปอ่านใหม่อีกรอบ, อีกรอบ, อีกรอบ

ถ้าหายมึนแล้ว เรามาดูว่า จะใช้ mod ให้เกิดประโยชน์อย่างไร :D

[banker]

ตัวอย่างที่ 8.

การหาเศษเหลือของ $10^{10}$ หารด้วย ${7}$

วิธีทำ

เพราะว่า $10$ หารด้วย $7$ เหลือเศษ $3$

เพราะฉะนั้น $10 \equiv 3 \pmod{7} $

ดังนั้น $10^{10} \equiv 3^{10} \pmod{7}$

เพราะว่า $3^{10} = 9^5$ และ $ \ 9 \equiv 2 \pmod{7}$

เพราะฉะนั้น $3^{10} \pmod{7} \equiv 9^5 \pmod{7}$ $ \equiv (7+2)^5 \pmod

{7}$

$ \ \ \ \ \ \ \ \ \ \equiv 2^5 \pmod{7}$

$ \ \ \ \ \ \ \ \ \ \equiv 32 \pmod{7}$

$ \ \ \ \ \ \ \ \ \ \equiv 4 \pmod{7}$

สรุป $10^{10} \ $ หารด้วย $ \ 7$ เหลือเศษ $4$


เป็นยังไงบ้าง ง่ายไหมครับ

[banker]

ตัวอย่าง 9.

การหาเศษเหลือจากการหาร $10^{100} \ $ ด้วย $ \ 13$

วิธีทำ

$10^{100} = (10^2) ^{50} = 100^{50}$

เพราะว่า $100 \ $ หารด้วย $ \ 13$ เหลือเศษ $ \ 9 \ $

เพราะฉะนั้น $ 100 \equiv 9 \pmod{13} $

ดังนั้น $100^{50} \equiv 9^{50} \pmod{13} $

$\equiv (9^2)^{25} \pmod{13} \ \ \ \ \ \ \equiv 81^{25} \pmod{13}$

$\equiv (6(13)+3)^{25} \pmod{13} \ \ \ \ \ \ \equiv 3^{25} \pmod{13}$

$ \equiv (3^5)^5 \pmod{13} \ \ \ \ \ \ \equiv (243)^5 \pmod{13}$

$ \equiv (18(13)+9)^5 \pmod{13} \ \ \ \ \ \ \equiv 9^5 \pmod{13}$



แต่ $ \ 9 \equiv 9 \pmod{13}$

$9^2 \equiv 9^2 \pmod{13} \equiv 81 \pmod{13} \equiv 3 \pmod{13}$

$ 9^4 \equiv 3^2 \pmod{13} \equiv 9 \pmod{13}$

$9^5 \equiv 9 (9) \pmod{13} \equiv 81 \pmod{13} \equiv 3 \pmod{13}$

สรุป $10^{100} \equiv 100^{50} \pmod{13} \equiv 9^{50} \pmod{13}$

$ \equiv 9^5 \pmod{13} \equiv 3 \pmod{13}$

นั้นคือ $10^{100}$ หารด้วย $13$ เหลือเศษ $3$


มันส์ไหมครับ ถ้ามันส์ ก็มามันส์ด้วยกันต่อในตัวอย่างต่อไป :haha:

[banker]

ยังมีวิธีง่ายกว่านี้ขึ้นไปอีก

เรามาศึกษาด้วยกันนะครับ

ตัวอย่างที่ 10.

เศษเหลือที่ได้จากการหาร $13^{100}$ ด้วย $17$ เท่ากับเท่าใด


วิธีทำ

เศษเหลือที่ได้จากการหาร $13^{100}$ ด้วย $17$


$ \equiv 13^{100} \pmod{17} \ \ \ \ \ \equiv ( 13^2)^{50} \pmod{17} $

$ \equiv (169)^{50} \pmod{17} \ \ \ \ \ \equiv (9(17)+16)^{50} \pmod{17} $

$ \equiv (16)^{50} \pmod{17} \ \ \ \ \ \equiv (2^4)^{50} \pmod{17} $

$ \equiv (2^5)^{40} \pmod{17} \ \ \ \ \ \equiv (32)^{40} \pmod{17} $

$ \equiv ( 17+15)^{40} \pmod{17} \ \ \ \ \ \equiv (15)^{40} \pmod{17} $

$ \equiv (15^2)^{20} \pmod{17} \ \ \ \ \ \equiv (225)^{20} \pmod{17} $

$ \equiv (4)^{20} \pmod{17} \ \ \ \ \ \equiv 2^{40} \pmod{17} $

$ \equiv (2^5)^{8} \pmod{17} \ \ \ \ \ \equiv 32^8 \pmod{17} $

$ \equiv (17+15)^{8} \pmod{17} \ \ \ \ \ \equiv 15^8 \pmod{17} $

$ \equiv (15^2)^{4} \pmod{17} \ \ \ \ \ \equiv (225^4) \pmod{17} $

$ \equiv4^{4} \pmod{17} \ \ \ \ \ \equiv 256 \pmod{17} $

$ \equiv 1 \pmod{17} $



สรุป $13^{100}$ หารด้วย $17$ เหลือเศษ $1$







ต่อไปเราจะหาขั้นตอนวิธีที่จะทำให้การคำนวณง่ายขึ้น
ก่อนอื่นขอทบทวนแนวคิดของการหาหลักหน่วยของ $3^n$

เพราะว่า
$3^1= 3$

$3^2 = 9$

$3^3 = 27$

$3^4 = 81$
.
.
.


$ 3^{4k} = ...1$ หลักหน่วยเป็นเลข $1$

$3^{4k+1} = ...3 $ หลักหน่วยเป็นเลข $3$

$3^{4k+2} = ...9 $ หลักหน่วยเป็นเลข $9$

$3^{ 4k+3} =...7 $ หลักหน่วยเป็นเลข $7$

เพราะฉะนั้นหลักหน่วยของ $3^n$ จึงขึ้นอยู่กับเศษเหลือของ $n$ หารด้วย $4$


แนวทางการหาเศษเหลือจาก $a^n$ ด้วย $m$

1. หาค่า $k$ น้อยสุดที่ทำให้ $a^k \equiv 1 \pmod{m}$

2. หาเศษเหลือจากการหาร $n$ ด้วย $k$ สมมติเป็น $p$

3. จะได้ว่า $a^n \equiv a^p \pmod{m}$




มาดูตัวอย่างต่อไปนะครับ

[banker]

ตัวอย่าง 11.

การหาเศษเหลือจากการหาร $13^{100}$ ด้วย $17$

ขั้นตอนที่ 1
$13 \equiv 13 \pmod{17} $

$13^2 \equiv 169 \pmod{17} \ \ \ \ \equiv 16 \pmod{17}$

$13^3 \equiv 13(16) \pmod{17} \ \ \ \ \equiv 208 \pmod{17} \ \ \ \ \equiv 4 \pmod{17}$

$13^4 \equiv 13(4) \pmod{17} \ \ \ \ \equiv 52 \pmod{17} \ \ \ \ \equiv 1 \pmod{17}$

ได้ $k = 4$

ขั้นที่ $2 \ \ \ 100$ หารด้วย $4$ เหลือเศษ $0$

ขั้นที่ $3 \ \ \ 13^{100} \equiv 13^0 \pmod{17} \ \ \equiv 1 \pmod{17}$

สรุป $13^{100}$ หารด้วย $17$ เหลือเศษ $1$



ง่ายขึ้นไหมครับ :haha:

[banker]

ตัวอย่าง 12.

จงหาเศษเหลือที่ได้จากการหาร $10^{100}$ ด้วย $7$

วิธีทำ ขั้นที่ $1$ หาค่า $k$ น้อยสุดที่ทำให้ $ 10^k \equiv 1 \pmod{7} $

$ 10^1 \equiv 10 \pmod{7} \equiv 3 \pmod{7}$

$ 10^2 \equiv 30 \pmod{7} \equiv 2 \pmod{7}$

$ 10^3 \equiv 20 \pmod{7} \equiv 6 \pmod{7}$

$ 10^4 \equiv 60 \pmod{7} \equiv 4 \pmod{7}$

$ 10^5 \equiv 40 \pmod{7} \equiv 5 \pmod{7}$

$ 10^6 \equiv 50 \pmod{7} \equiv 1 \pmod{7}$


สรุป $k = 6$

ขั้นที่ $2 \ \ \ 100 = 16(6)+4 $

ขั้นที่ $3 \ \ \ 10^{100} \equiv 10^{16(6)+4} \pmod{7} \equiv 10^4 \pmod{7} \equiv 4

\pmod{7} $


สรุป $7$ หาร $10^{100}$ เหลือเศษ $4$

[banker]

ท้ายสุดของปัญหาในข้อนี้จะขอนำทฤษฎีของระบบจำนวนมาแนะนำให้ใช้
เพื่อเกิดประโยชน์ในการคิดเลขให้เร็วขึ้น ดังนี้

ทฤษฎีบท 2

ถ้า $p$ เป็นจำนวนเฉพาะ และ $a$ เป็นจำนวนบวกที่ $p$ หาร $a$ ไม่ลงตัวแล้ว

$ a^{p- 1} \equiv 1 \pmod{p} $


ตัวอย่าง 13.

จงหาเศษเหลือจากการหาร $10^{100}$ ด้วย $17$

วิธีทำ
เพราะว่า
$10^{16} \equiv 1 \pmod{17 } $ และ $ \ \ 100 = 6(16) + 4 $

เพราะฉะนั้น

$10^{16} \equiv 1 \pmod{17} $

$(10^{16})^6 \equiv 1^6 \pmod{17} $

$10^{6(16)} \equiv 1 \pmod{17} $

$10^{6(16)+4} \equiv 10^4 \pmod{17} $

เพราะว่า
$10^2 \equiv 100 \pmod{17} \ \ \ \equiv 15 \pmod{17} $

$10^3 \equiv 150 \pmod{17} \ \ \ \equiv 14 \pmod{17} $

$10^4 \equiv 140 \pmod{17} \ \ \ \equiv 4 \pmod{17} $


เพราะฉะนั้น $10^{100}$ หารด้วย $17$ เหลือเศษ $4$



ตัวอย่าง 14.

จงหาเศษเหลือจากการหาร $2^{100!}$ ด้วย ${19}$

วิธีทำ


เพราะว่า $2^{18} \equiv 1 \pmod{19} \ $ และ $\frac{100!}{18} \ $ เป็นจำนวนเต็ม

เพราะฉะนั้น
$(2^{18})^{\frac{100!}{18}} \equiv 1 \pmod{19} $

$2^{100!} \equiv 1 \pmod{19} $

เพราะฉะนั้น $19$ หาร $2^{100!}$ เหลือเศษ $1$

[banker]

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

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

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

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

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

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

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

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

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

[banker]

เสริมสุดท้าย

ถ้าเซียน หรือท่านผู้รู้เรื่อง mod เห็นว่า มีผิดพลาดตรงไหน

หรืออยากเพิ่มเติมตรงไหน ก็ช่วยแนะนำด้วยครับ

สุดท้ายจริงๆ ขอบคุณอาจารย์ ดำรงค์ ทิพย์โยธา ที่เสียสละเวลาเขียนหนังสือดีๆให้พวกเราได้เรียนรู้

[{ChelseA}]

:great:ขอบคุณ คุณลุง banker จริงๆครับ สมควรปักหมุดๆ

[Siren-Of-Step]

ฝากไว้
จงแสดงว่า $2^{340} \equiv 1 (mod 341)$

[banker]

ฝากไว้
จงแสดงว่า $2^{340} \equiv 1 (mod 341)$

hint
$2^{10} = (1024) = (1023+1) = (3(341) +1)$

[MiNd169]

ขอบคุณ คุณbankerมากครับ สมควรปักหมุดมากๆ
ขอถามหน่อยนะครับว่า ทวินาม เป็นเรื่องที่หาได้จากระดับการศึกษาชั้นไหนครับ

[หยินหยาง]

เสริมสุดท้าย

ถ้าเซียน หรือท่านผู้รู้เรื่อง mod เห็นว่า มีผิดพลาดตรงไหน

หรืออยากเพิ่มเติมตรงไหน ก็ช่วยแนะนำด้วยครับ



อยากเพิ่มเติมข้างหน้า mod เพื่อให้เกิดความกระชุ่มกระช่วยของ ท่านสว. banker โดยเติมคำว่า four เป็น four mod ครับ เพราะนอกจากจะปักหมุดแล้วอาจปักอกแถมอีกอย่างได้ครับ :D:D:laugh:

[poper]

ต้องขอขอบคุณคุณอา banker มากๆเลยครับ
ผมกำลังสนใจเรื่อง mod อยู่พอดี แต่หาอ่านยากมาก
ได้แบบนี้แล้วหาโจทย์ใน MC ทำให้มันส์ไปเลยล่ะกัน
ขอบคุณคุณอาอีกครั้งครับที่เสียสละเวลามาแบ่งปันความรู้:please:

[กิตติ]

ย่อยของยากให้ทานได้ง่ายและคล่องคอมากขึ้น
ขอบคุณครับคุณอาBanker

[JSompis]

อธิบายได้เห็นภาพเลยลุง เข้าใจง่ายดี ขอบคุณมากๆครับ เก็บเข้าคลังไว้ก่อน

[คusักคณิm]

ลองทำข้อพวกนี้แบบไม่ใช้ mod ดู ^^
จงหาเศษ
1.$(4)(4!)^2000$ หารด้วย 7
2.$(5)(5!)^2000$ หารด้วย 7
3.$(6)(6!)^2000$ หารด้วย 7

[กิตติ]

1.$(4!)^{2000}=24^{2000}=(7(3)+3)^{2000}$ เหลือเศษเท่ากับ $3^{2000}$
คิดตามแบบปกติ จะได้ว่า$(3^5)^{400}=(7(34)+5)^{400}$
$5^{400}=(7(89)+2)^{100}$
$2^{100}\times 4 =2^{102}=(7+1)^{34}$.....ตอบว่าเหลือเศษ 1
$24\equiv 24 (mod 7) \equiv3 (mod 7) $
$24^2 \equiv 72(mod 7) \equiv 2(mod 7)$
$24^3 \equiv 48(mod 7) \equiv 6(mod 7)$
$24^4 \equiv 144(mod 7) \equiv 4(mod 7)$
$24^5 \equiv 96(mod 7) \equiv 5(mod 7)$
$24^6 \equiv 120(mod 7) \equiv 1(mod 7)$
$24^6 \equiv 1(mod 7)$
ดังนั้น $k=6$
$2000=6(333)+2$
$24^{6(333)+2} \equiv 24^2(mod 7) \equiv 2(mod 7)$
$4\times 24^{2000} \equiv 4\times 2(mod 7) \equiv 8(mod 7) \equiv 1(mod 7)$
ได้คำตอบเท่ากันคือ เศษ 1

[poper]

ข้อ 2 แบบนี้ถูกรึป่าวอ่ะครับ
$5!=120$
${(120)}^{2000}={(7(17)+1)}^{2000}$
${(5!)}^{2000}≡1(mod 7)$
$5{(5!)}^{2000}≡5(mod 7)$
ตอบเหลือเศษ 5
(พิมเครื่องหมาย ≡ ยังไงอ่ะครับ)

[กิตติ]

2.$5(5!)^{2000}$ $(120)^{2000}$
แยกเป็น $8^{2000}\times 3^{2000} \times 5^{2000}$
$8^2 \equiv 64 (mod 7) \equiv 1(mod7)$
$2000 =2(1000)+0$
$8^{2000} \equiv 8^0(mod 7) \equiv 1(mod7)$...เศษ 1

$3^2 \equiv 9 (mod 7) \equiv 2(mod7)$
$3^3 \equiv 6 (mod 7) $
$3^4 \equiv 18 (mod 7) \equiv 4(mod7)$
$3^5 \equiv 12 (mod 7) \equiv 5(mod7)$
$3^6 \equiv 15 (mod 7) \equiv 1(mod7)$
$3^6 \equiv 1(mod7)$
$2000=6(333)+2$
$3^{2000} \equiv 9 (mod 7) \equiv 2(mod7)$......เศษ 2

$5^2 \equiv 25 (mod 7) \equiv 4(mod7)$
$5^3 \equiv 20 (mod 7) \equiv 6(mod7)$
$5^4 \equiv 30 (mod 7) \equiv 2(mod7)$
$5^5 \equiv 10 (mod 7) \equiv 3(mod7)$
$5^6 \equiv 15 (mod 7) \equiv 1(mod7)$
$2000=6(333)+2$
$5^{2000} \equiv 25 (mod 7) \equiv 4(mod7)$......เศษ 4

$8^{2000} \equiv 1(mod7)$ $3^{2000} \equiv 2(mod7)$
$8^{2000} \times 3^{2000} \equiv 1\times 2(mod7) \equiv 2(mod7)$
$8^{2000} \times 3^{2000} \equiv 2(mod7)$ กับ $5^{2000} \equiv 4(mod7)$
$8^{2000} \times 3^{2000} \times 5^{2000}\equiv 2\times 4(mod7) \equiv 1(mod7)$
$(120)^{2000}\equiv 1(mod7)$
$5\times (120)^{2000}\equiv 5\times 1(mod7) \equiv 5(mod7)$
ตอบเศษ 5

ให้ง่ายอีกหน่อยเมื่อกี้รู้แล้วว่า$(4!)^{2000} \equiv 2(mod7)$
$5^{2000} \equiv 4(mod7)$
$(4!)^{2000}\times5^{2000} \equiv 2\times 4(mod7) \equiv 1(mod7)$
$(5!)^{2000} \times 5 \equiv 5(mod7)$

[กระบี่เดียวดายแสวงพ่าย]

แหมตอนแรกผมนึกว่าจะหมายถึงmode (ฐานนิยม)เสียแล้วครับ

[กิตติ]

3.$6(6!)^{2000}$
$(5!)^{2000} \equiv 1 (mod7)$
$6^2 \equiv 36(mod7) \equiv 1(mod7)$
$6^{2000}\equiv 36(mod7) \equiv 1(mod7)$
$(6!)^{2000} \equiv 1(mod7)$
$6(6!)^{2000}\equiv 6(mod7)$
เศษ 6

ลองทำตามวิธีคุณอาbankerสอนให้ทำ ย่นเวลาเยอะเลยครับ....

[poper]

ไม่เข้าใจว่าคุณกิตติทำไมถึงต้องทำยาวขนาดนั้นอ่ะครับ
ข้อ 2 ตามที่ผมเข้าใจคือ 7 หาร ${(120)}^{2000}$ จะเหลือเศษเท่ากับ 7 หาร ${(7(17)+1)}^{2000}$
ดังนั้นก็จะเท่ากับเศษที่ได้จากการหารด้วย $1^{2000}$ ซึ่งก็คือ 1 แสดงว่า ${(5!)}^{2000}≡1(mod7)$ ไม่ใช่เหรอครับ
วิธีผมมีอะไรผิดรึป่าวครับ
(เอ่อ.. เครื่องหมาย≡พิมไงอ่ะครับ ขี้เกียจก๊อปง่ะ)

[กิตติ]

ก็ลองทำตามทฤษฎีบทที่มีให้ดูครับ จริงๆจะแยกเป็น$12\times 10$ก็ได้ แล้วแต่ถนัดครับ จะใช้เป็น$24\times 5$ก็แล้วแต่ถนัด
$12^2 \equiv 144 (mod 7) \equiv 4(mod 7)$
$12^3 \equiv 48 (mod 7) \equiv 6(mod 7)$
$12^4 \equiv 72 (mod 7) \equiv 2(mod 7)$
$12^5 \equiv 24 (mod 7) \equiv 3(mod 7)$
$12^6 \equiv 36 (mod 7) \equiv 1(mod 7)$
$12^{2000} \equiv 12^2 (mod 7) \equiv 4(mod 7)$

$10^2 \equiv 100 (mod 7) \equiv 2(mod 7)$
$10^3 \equiv 20 (mod 7) \equiv 6(mod 7)$
$10^4 \equiv 60 (mod 7) \equiv 4(mod 7)$
$10^5 \equiv 40 (mod 7) \equiv 5(mod 7)$
$10^6 \equiv 50 (mod 7) \equiv 1(mod 7)$
$2000=6(333)+2$
$10^{2000} \equiv 10^2 (mod 7) \equiv 2(mod 7)$
$12^{2000} \times 10^{2000}\equiv 4\times 2(mod 7) \equiv 1(mod 7)$
$5(5!)^{2000}\equiv 5(mod 7)$
ก็ได้คำตอบเท่ากันนี่ครับ

สัญลักษณ์$\equiv $ อยู่ในกลุ่มเดียวกับ$\leqslant \not= \approx $

[poper]

ขอบคุณครับ วิธีที่ผมทำไม่ผิดใช่มั้ยครับ
ถ้าจำผิดๆไปล่ะแย่เลย

[catengland]

คุณ banker เอามาจากเล่มไหนของ อ.ดำรงค์ ทิพย์โยธา ครับ
คณิตศาสตร์ปรนัยรึเปล่า แนะนำผมหน่อยนะคร้าบบบบบบบบบบ

[banker]

คณิตศาสตร์ปรนัยเล่ม 19 ครับ

3297

ดูเหมือนเล่มนี้จะยกเป็นรางวัล math contest ไปแล้วครับ

รอ modertor ประกาศว่าใครจะเป็นผู้ได้รับ :D

[TuaZaa08]

คณิตศาสตร์ปรนัยเล่ม 19 ครับ

3297

ดูเหมือนเล่มนี้จะยกเป็นรางวัล math contest ไปแล้วครับ

รอ modertor ประกาศว่าใครจะเป็นผู้ได้รับ :D

*0* อยากได้

ซื้อที่ไหนได้มั้งเนี่ย

[กิตติ]

เข้าไปในเวปไซด์ศูนย์หนังสือจุฬา...น่าจะมีอยู่
ผมเพิ่งซื้อที่ดวงกมลเชียงใหม่เมื่อปลายเดือนที่แล้ว หนังสือปกเยินมีแต่รอยขูดขีด ก็ซื้อครับ 160 บาท..เห็นมีอยู่2เล่ม
น่าอ่านครับ

[คusักคณิm]

เจอที่ห้องสมุดโรงเรียน แต่บัตรสมาชิกหาย== อดเลย ToT

[poper]

รบกวนขอโจทย์อีกได้มั้ยครับอยากฝึกทำอ่ะครับ

[banker]

รบกวนขอโจทย์อีกได้มั้ยครับอยากฝึกทำอ่ะครับ

1. จงหาเศษจากการหาร $2^{20}$ ด้วย $41$

2. จงหาเศษจากการหาร $7^{10}$ ด้วย $51$

3. จงหาเศษจากการหาร $10^{49}$ ด้วย $7$

ผมก็ยังไม่ได้ทำ ลองดูนะครับ

[Siren-Of-Step]

1. จงหาเศษจากการหาร $2^{20}$ ด้วย $41$

2. จงหาเศษจากการหาร $7^{10}$ ด้วย $51$

3. จงหาเศษจากการหาร $10^{49}$ ด้วย $7$

ผมก็ยังไม่ได้ทำ ลองดูนะครับ

ข้อ 1
เพราะว่า $2^{40} \equiv 1 \pmod{41}$
จะได้ว่า $2^{20} \equiv 1 \pmod{41}$

ข้อ 2
เพราะว่า $7^{2} \equiv -2 \pmod{51}$
$7^{10} \equiv -2^5 \equiv 19 \pmod{51}$

ข้อ 3
$ 10^{6} \equiv 1 \pmod{7}$
$10^{49} \equiv 6 \pmod{7}$

[กิตติ]

ข้อ 3 $10^{7-1}\equiv 1(mod 7)$
$(10^6)^8\equiv 1(mod 7)$
$10^{48}\equiv 1(mod 7)$
$10\equiv 3(mod 7)$
$10^{49}\equiv 3(mod 7)$
ไม่รู้ว่าผมจะคิดผิดหรืองงเองครับ...ดึกแล้วชักมึน

[banker]

ข้อ 3 $10^{7-1}\equiv 1(mod 7)$
$(10^6)^8\equiv 1(mod 7)$
$10^{48}\equiv 1(mod 7)$
$10\equiv 3(mod 7)$
$10^{49}\equiv 3(mod 7)$
ไม่รู้ว่าผมจะคิดผิดหรืองงเองครับ...ดึกแล้วชักมึน

ถูกแล้วครับ :great:

[poper]

ข้อ 1 ทำแบบนี้ได้มั้ยครับ
$2^{20}=32^4={(41-9)}^4$
$9^4=81^2={(41(2)-1)}^2$
ดังนั้น $2^{20}\equiv 1(mod41)$
ข้อ 2
$7^{10}=49^5={(51-2)}^5$
$-2^5=-32=-(51-19)=-51+19$ ตอบเศษ 19
ข้อ 3 ก็ใช้ $a^{p-1}\equiv 1(modp)$
ถูกมั้ยครับผม

[banker]

ถูกครับ

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

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

[poper]

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

[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$

[Siren-Of-Step]

ถูกแล้วครับ :great:

สะเพร่าเองซะงั้น :please::nooo::cry:

[Siren-Of-Step]

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

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$ เหลือเศษเท่าไร

ขอบคุณครับ

[กิตติ]

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$

ถูกต้องครับ :great:

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

$ \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]

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]

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$

[กิตติ]

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$ ได้

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


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

[กิตติ]

ที่คุณอา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 เป็นแล้ว ^^

[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}$

[กิตติ]

($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 ครับ ยังไม่มีใครเฉลย :kaka:

ข้อ 15 วันแรก

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

[~ArT_Ty~]

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

ข้อ 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~]

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

แก้แล้วครับ

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

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

[หยินหยาง]

แก้แล้วครับ

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

ผิดตรงไหนช่วยบอกด้วยนะครับ :please::please::please:
ไม่ต้องบอกครับ ก็แก้แล้วนี่ครับ :great:

[กิตติ]

จงหาจำนวนเต็ม $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$
ไม่รู้ว่าผมงงตรงไหนหรือเปล่า.....

[กะทิบูด]

ตกลง ตอบข้อไหน ครับ ^^

[Xx GAMMA xX]

$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$
ไม่รู้ว่าผมงงตรงไหนหรือเปล่า.....

ผมคิดว่าตรงนี้mไม่จำต้องเป็นจน.เต็มก็ได้นะครับ
เพราะสมมติm=1/4 nก็เป็นจน.เต็มเหมือนกันใช่ไหมครับ

[กิตติพงศ์]

$m$ต้องเป็นจำนวนเต็มครับ เพราะเราต้องการรู้ว่าต้องทบไปกี่รอบ
$m$ เป็นจำนวนรอบการนำ$3^{156}$ ไปคูณตามวิธีของการใช้$mod$
$3^{159} \equiv 27 \pmod{169} $
$3^{156} \equiv 1 \pmod{169} $
$3^{159+156} \equiv 27 \pmod{169} $
$3^{159+2(156)} \equiv 27 \pmod{169} $
$3^{159+3(156)} \equiv 27 \pmod{169} $
$3^{159+m(156)} \equiv 27 \pmod{169}$
ตามนี้ครับ

[กิตติ]

ความเห็น#78เมื่อกี้ผมเองครับ พอดีลองเอาusernameของลูกชายมาลงดูว่าใช้ได้ไหม

[poper]

โอ้ว...
มีทายาทผู้เยี่ยมยุทธมาสืบทอดแล้วครับ:great:

[Onasdi]

แต่เหมือนว่าคุณกิตติจะใช้ $3^a\equiv 3^b \pmod{m}~\Rightarrow~ a=b$ ซึ่งไม่จำเป็นครับ

[กิตติ]

ที่ผมใช้น่าจะเป็นแบบนี้คือ ผมใช้$3^{156} \equiv 1 \pmod{169} $ ไปคูณกับ $3^{159} \equiv 27 \pmod{169} $ ตามที่ความรู้ข้างต้น ผมต้องการรู้ว่าต้องการคูณไปกี่ครั้ง
$3^{159+156m} \equiv 27 \pmod{169} $แล้วเทียบกับสิ่งที่ผมแปลงจากโจทย์คือ
$3^{3n+3}\equiv 27 \pmod{169}$ แล้วผมก็จับให้$3^{159+156m}=3^{3n+3}$ซึ่งเป็นพจน์ตัวถูกหารด้วย 169เหมือนกัน
ก็ได้$159+156m=3n+3$
ไม่รู้ว่าตรงไหนที่ผมเข้าใจผิดบ้าง ช่วยชี้แนะด้วยครับ

[กิตติ]

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

[Onasdi]

ที่ผมใช้น่าจะเป็นแบบนี้คือ ผมใช้$3^{156} \equiv 1 \pmod{169} $ ไปคูณกับ $3^{159} \equiv 27 \pmod{169} $ ตามที่ความรู้ข้างต้น ผมต้องการรู้ว่าต้องการคูณไปกี่ครั้ง
$3^{159+156m} \equiv 27 \pmod{169} $แล้วเทียบกับสิ่งที่ผมแปลงจากโจทย์คือ
$3^{3n+3}\equiv 27 \pmod{169}$ แล้วผมก็จับให้$3^{159+156m}=3^{3n+3}$ซึ่งเป็นพจน์ตัวถูกหารด้วย 169เหมือนกัน
ก็ได้$159+156m=3n+3$
ไม่รู้ว่าตรงไหนที่ผมเข้าใจผิดบ้าง ช่วยชี้แนะด้วยครับ
ตรงสีแดงสรุปไม่ได้ครับ ตัวอย่างเช่น
$3^{159} \equiv 27 \pmod{169}$ และ $3^{3} \equiv 27 \pmod{169}$ แต่ $3^{159}\ne 3^3$

แต่ค่าที่คุณกิตติหามา (1976) เป็นค่าที่ใช้ได้นะครับ ทั้งนี้เพราะว่า
$3^{3n+3}=3^{159+156m}~\Rightarrow~ 3^{3n+3}\equiv 3^{159+156m}\equiv 27 \pmod{169}$
แต่เรายังสรุปไม่ได้ว่ามันเป็นค่าที่มากที่สุดแล้ว

ป.ล. เห็นคุณกิตติสอนลูก เลยอยากแนะนำบทความนี้ (http://www.maa.org/devlin/LockhartsLament.pdf)ครับ เกี่ยวกับระบบการศึกษาวิชาคณิตศาสตร์ครับ แต่มันเป็นภาษาอังกฤษนะครับ

[หยินหยาง]

ท่านกิตติเป็นบุคคลที่น่าได้รับการช่วยเหลือ ผมเลยอยากจะเสนอความเห็นบางอย่าง แต่ไม่กล้าแนะนำบทความแบบท่าน Onasdi เพราะไม่มีเด็ดๆแบบนั้น :D แต่มีไอเดียไม่รู้จะถูกใจหรือไม่ ไม่ยากเพราะใช้ความสามารถในวิชาชีพครับ ลองคุยกับลูกว่าพ่อมีทางเลือกให้ลูก 2 อย่างคือ
1.ลูกจะขยันหาความรู้ใส่ตัวเอง หรือ
2.ลูกจะให้พ่อเอาความรู้ใส่ตัวลูก
ถ้าลูกเลือกอย่างหลังต้องบอกลูกว่า ลูกต้องทนเจ็บนิดหนึ่งเพราะพ่อต้องฉีดความรู้ใส่สมองลูกทุกวันจนกว่าลูกจะเก่ง :happy::)

[กิตติ]

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

ขอบคุณมากครับคุณOnasdi สำหรับบทความ ผมคงไม่ได้สอนลูกลูกจริงๆจังๆ ทำตัวเป็นที่ปรึกษามากกว่า เวลาทำโจทย์ที่โรงเรียนกับที่เรียนพิเศษไม่ได้
พอดีผมเข้าใจตามวิธีการหาเศษจากการหารตามตัวอย่างที่ว่า $10^{100}$หารด้วย $17$ เหลือเศษเท่าไหร่
เราก็หาได้ว่า$10^{16} \equiv 1 \pmod{17} $ แล้วเราก็ได้รอบของการหาร
$100 =6(16)+4$
$10^{6(16)+4} = 10^4 \equiv ? \pmod{17} $
$10^4 \equiv 4 \pmod{17} $
ผมก็เลยทำแบบข้างต้น
ถ้าเราเริ่มจาก$3^3 \equiv 27 \pmod{169} $ แล้วคูณด้วย$3^{156} \equiv 1 \pmod{169} $
แบบเดียวกับที่ผมทำได้ไหม
ผมยังงงๆอยู่ รบกวนช่วยบอกคำตอบให้หน่อยครับ จะถือว่าเป็นวิทยาทานถ้าช่วยแสดงวิธีทำหน่อยครับ....:please::please::please:
คืนนี้ผมขอตัวก่อนแล้วครับ เจ้าตัวเล็กเริ่มงอแงแล้วครับ เมื่อคืนก็ช่วยแฟนอุ้มลูกตั้งแต่สองทุ่มยันตีสอง วันนี้ไม่รู้ว่าจะงอแงถึงกี่โมง
ยังไงก็ขอขอบคุณทุกความเห็นที่ช่วยชี้ความกระจ่างให้ครับ

[Onasdi]

คือถูกแล้วครับที่บอกว่า $3^{3\times1976+3} = 3^{156\times 38+3} \equiv \left(3^{156}\right)^38\cdot 3^3 \equiv 27 \pmod{169}$
นั่นก็คือ $n=1976$ ใช้ได้ และเป็นค่าที่มากที่สุดที่ได้มาจากวิธีการหาแบบที่หามา
แต่อาจจะมีวิธีการหาแบบอื่นที่ทำให้เราได้ $n$ ที่มากกว่านี้ก็ได้ครับ ยังไม่มีเหตุผลว่าจะไม่มี

สำหรับวิธี ผมเองก็ยังไม่รู้ว่าจะทำยังไงครับ ท่านไหนคิดออกรบกวนแสดงวิธีทำเลยครับ

เท่าที่ผมคิดคือเหมือนว่าจะต้องหา order ของ 3 mod 169 ออกมา
นั่นก็คือหาจำนวนเต็มบวก $d$ ที่น้อยที่สุดที่ทำให้ $3^d \equiv 1 \pmod{169}$ มันดูน่าจะเหนื่อยใช้ได้ครับ

[กิตติ]

แสดงจากที่เราหาจากEuler's theorem
$a^{\phi(n)}\equiv 1 \pmod{n} $ .....แสดงว่า$\phi(n)$ ยังไม่ใช่ค่าที่น้อยที่สุดที่ทำให้การหารด้วย$n$ เหลือเศษ 1 หรือเปล่าครับ
อยากได้ความรู้เรื่องนี้ครับ รบกวนท่านที่รู้เล่าให้ฟังกับชี้จุดให้เข้าใจด้วยครับ

[คนอยากเก่ง]

ขอบคุณมากครับ

[Onasdi]

แสดงจากที่เราหาจากEuler's theorem
$a^{\phi(n)}\equiv 1 \pmod{n} $ .....แสดงว่า$\phi(n)$ ยังไม่ใช่ค่าที่น้อยที่สุดที่ทำให้การหารด้วย$n$ เหลือเศษ 1 หรือเปล่าครับ
อยากได้ความรู้เรื่องนี้ครับ รบกวนท่านที่รู้เล่าให้ฟังกับชี้จุดให้เข้าใจด้วยครับ
โดยทั่วไปแล้ว $\phi(n)$ ยังไม่ใช่ค่าที่น้อยที่สุดครับ แต่ก็มีกรณีที่ใช่ครับ

$a=2,~n=7$
$2^1 \equiv 2 \pmod{7}$
$2^2 \equiv 4 \pmod{7}$
$2^3 \equiv 1 \pmod{7}$
แต่ $\phi(7)=6$
===============
$a=3,~n=5$
$3^1 \equiv 3 \pmod{5}$
$3^2 \equiv 4 \pmod{5}$
$3^3 \equiv 2 \pmod{5}$
$3^4 \equiv 1 \pmod{5}$
และ $\phi(5)=4$

[กิตติ]

ผมคงต้องกลับไปดูเรื่องของEuler's theoremให้เข้าใจมากกว่าตอนนี้ก่อนแล้วจะรบกวนถามครับ
ขอบคุณครับคุณOnasdiที่ยกตัวอย่างให้เห็น

[Siren-Of-Step]

โดยทั่วไปแล้ว $\phi(n)$ ยังไม่ใช่ค่าที่น้อยที่สุดครับ แต่ก็มีกรณีที่ใช่ครับ

$a=2,~n=7$
$2^1 \equiv 2 \pmod{7}$
$2^2 \equiv 4 \pmod{7}$
$2^3 \equiv 1 \pmod{7}$
แต่ $\phi(7)=6$
===============
$a=3,~n=5$
$3^1 \equiv 3 \pmod{5}$
$3^2 \equiv 4 \pmod{5}$
$3^3 \equiv 2 \pmod{5}$
$3^4 \equiv 1 \pmod{5}$
และ $\phi(5)=4$
เราจะหาตัวน้อยสุดได้ไหมครับ ซึ่ง $a^n \equiv 1 \pmod{m}$

[Onasdi]

เราจะหาตัวน้อยสุดได้ไหมครับ ซึ่ง $a^n \equiv 1 \pmod{m}$
ผมคิดว่าไม่มีวิธีทั่วไปนะครับ ไม่แน่ใจเหมือนกัน

[Siren-Of-Step]

ถามหน่อยครับ $a^{\phi (n)} \equiv 1 \pmod{n}$
$a,n$ ต้องเป็น co-prime ใช่ปะครับ :please:

[Onasdi]

ถามหน่อยครับ $a^{\phi (n)} \equiv 1 \pmod{n}$
$a,n$ ต้องเป็น co-prime ใช่ปะครับ :please:
ใช่แล้วครับ นั่นเป็นเงื่อนไขของทฤษฎี

ถ้า $(a,n)\ne 1$ จะได้ว่ามีจำนวนเฉพาะ $p$ ที่หารทั้ง $a$ และ $n$
ดังนั้น $p\not|a^{\phi (n)}-1$ ทำให้ $n\not|a^{\phi (n)}-1$
นั่นคือ $a^{\phi (n)} \not\equiv 1 \pmod{n}$

[Siren-Of-Step]

มีทฤษฎี/เทคนิค อย่างอื่นไหมครับ ที่ช่วยในการทำโจทย์เร็วขึ้น

[Onasdi]

น่าจะมีเยอะครับ ต้องทำโจทย์เยอะๆถึงได้พวกเทคนิคครับ

เทคนิคนึงที่คิดออกคือการแยกตัวประกอบของตัวหาร
เช่นถ้าเราจะหา $n$ ที่น้อยๆที่ทำให้ $7^{n} \equiv 1 \pmod{15}$
เราก็อาจจะแยก $15=3\times 5$ แล้วทำ mod 3 กับ mod 5 ตามนี้ครับ

$7^{4} \equiv 1 \pmod{5}$ และ
$7^{2} \equiv 1 \pmod{3}$ จึงได้ $7^{4} \equiv 1 \pmod{3}$
ดังนั้น $7^{4} \equiv 1 \pmod{3\times 5}$

จะเห็นว่าวิธีนี้ดีกว่าการใช้ Euler's theorem ตรงๆ
เพราะถ้าใช้ตรงๆจะได้ $\phi(15)=\phi(3)\phi(5)=8$
ดังนั้น $7^{8} \equiv 1 \pmod{15}$

[กิตติ]

จริงๆผมน่าจะเอ๊ะใจตามที่คุณOnasdi ได้แสดงให้เห็นในกระทู้ก่อนๆแล้ว ในที่เขียนว่า
$7^{4} \equiv 1 \pmod{5}$ และ
$7^{2} \equiv 1 \pmod{3}$ จึงได้ $7^{4} \equiv 1 \pmod{3}$
ดังนั้น $7^{4} \equiv 1 \pmod{3\times 5}$
ผมก็เคยสงสัยว่าเราจะสรุปแบบนั้นได้หรือเปล่า
สมมุติเราหาเศษจากการหาร$A^k$ด้วย$B*C$
เราแยกออกเป็น$\frac{A^m}{B} \times \frac{A^n}{C}$ เมื่อ$m+n=k$
$A^m = BX+r $ เมื่อ$r$ เป็นเศษ....คือ$A^m \equiv r \pmod{B} $
$A^n = CY+s $ เมื่อ$s$ เป็นเศษ....คือ$A^n \equiv s \pmod{C} $
$A^k=(BX+r)(CY+s ) =BCXY+rCY+sBX+rs $
เศษจากการหารคือ$rCY+sBX+rs$
ในกรณีที่เป็นตัวอย่าง
$7^4 =49*49 =2401 =3(800)+1$
$7^4 =49*49 =2401 =5(480)+1$
$B=3,C=5$
$X=800,Y=480,r=1,s=1$
เศษที่เกิดขึ้นคือ $CY+BX+1 = 5(480)+3(800)+1$
โชคดีที่$480$หารด้วย$3$ลงตัว และ$300$หารด้วย$5$ลงตัว
จึงเหลือเศษเป็น $1$ อย่างเราต้องการ
ถ้าเป็นกรณีโดยทั่วไปที่ไม่ได้ตรงกันแบบนี้ มันน่าจะสรุปแบบนั้นไม่ได้ โดยเฉพาะถ้า$r,s$ ไม่ได้เป็น $1$
ไม่รู้ว่าผมเข้าใจตรงไหนผิดหรือเปล่า.....

[กิตติ]

ลองให้$A^k$ หารด้วย$M$ และ$M=BC$ดู
$A^k = BX+r$.... $A^k \equiv r \pmod{B} $
$A^k = CY+s$.... $A^k \equiv s \pmod{C} $
$A^k = ZM+t$.... $A^k \equiv t \pmod{M} $
เมื่อ$X,Y,Z$ เป็นผลหารและ $r,s,t$ เป็นเศษ
ดังนั้น $BX+r = CY+s = ZM+t$
ถ้าให้เศษเท่ากันหมดคือ $r=s=t=1$ จะยุบเหลือ
$BX = CY = ZM$
$\frac{B}{C} =\frac{Y}{X} $
ดังนั้นเราจะสรุปได้ว่า
ถ้า $A^k \equiv 1 \pmod{B} $
และ $A^k \equiv 1 \pmod{C} $
แล้ว $A^k \equiv 1 \pmod{M=B\times C} $
ได้เมื่อ $\frac{B}{C} =\frac{Y}{X} $
ผมลองคิดต่อเล่นๆเท่านั้น....

[Onasdi]

จริงๆผมน่าจะเอ๊ะใจตามที่คุณOnasdi ได้แสดงให้เห็นในกระทู้ก่อนๆแล้ว ในที่เขียนว่า

ผมก็เคยสงสัยว่าเราจะสรุปแบบนั้นได้หรือเปล่า
สมมุติเราหาเศษจากการหาร$A^k$ด้วย$B*C$
เราแยกออกเป็น$\frac{A^m}{B} \times \frac{A^n}{C}$ เมื่อ$m+n=k$
$A^m = BX+r $ เมื่อ$r$ เป็นเศษ....คือ$A^m \equiv r \pmod{B} $
$A^n = CY+s $ เมื่อ$s$ เป็นเศษ....คือ$A^n \equiv s \pmod{C} $
$A^k=(BX+r)(CY+s ) =BCXY+rCY+sBX+rs $
เศษจากการหารคือ$rCY+sBX+rs$
ในกรณีที่เป็นตัวอย่าง
$7^4 =49*49 =2401 =3(800)+1$
$7^4 =49*49 =2401 =5(480)+1$
$B=3,C=5$
$X=800,Y=480,r=1,s=1$
เศษที่เกิดขึ้นคือ $CY+BX+1 = 5(480)+3(800)+1$
โชคดีที่$480$หารด้วย$3$ลงตัว และ$300$หารด้วย$5$ลงตัว
จึงเหลือเศษเป็น $1$ อย่างเราต้องการ
ถ้าเป็นกรณีโดยทั่วไปที่ไม่ได้ตรงกันแบบนี้ มันน่าจะสรุปแบบนั้นไม่ได้ โดยเฉพาะถ้า$r,s$ ไม่ได้เป็น $1$
ไม่รู้ว่าผมเข้าใจตรงไหนผิดหรือเปล่า.....
ที่ผมทำไม่ใช่ $k=m+n$ ครับ เพราะว่า $m=n=k=4$
สิ่งที่ผมใช้คือ $$ถ้า\quad X \equiv Y \pmod{B}\quad และ\quad X \equiv Y \pmod{C} \quad แล้ว \quad X \equiv Y \pmod{ค.ร.น.[B,C]}$$ลองดูครับว่าทำไมถึงจริง

[-SIL-]

ตัวอย่างที่ 6.

เศษเหลือจากการหาร $7^{2541}$ ด้วย $4$ เท่ากับเท่าใด


วิธีทำ
$ \ \ \ \ \ \ \ \ 7^{2541}= (4+3)^{2541}$

$ \ \ \ \ \ \ \ \ 3^{2541} = (3^3)^{847} =(27)^{847} =(6(4)+3)^{847}$

$ \ \ \ \ \ \ \ \ 3^{847} = (3^7)^{121} =(2187)^{121} =(546(4)+3)^{121}$

$ \ \ \ \ \ \ \ \ 3^{121} =(3^{11})^{11} = (177147)^{11}

= (44286(4)+3)^{11}$

$ \ \ \ \ \ \ \ \ 3^{11} = 177147$ หารด้วย $4$ เหลือเศษ $3$


เศษจากการหาร $7^{2541}$ ด้วย $4$
= เศษจากการหาร $3^{2541}$ ด้วย $4$
= เศษจากการหาร $3^{847}$ ด้วย $4$
= เศษจากการหาร $3^{121}$ ด้วย $4$
= เศษจากการหาร $3^{11}$ ด้วย $4$
= $3$



อีกมุมมองนึงครับ (ใช้พหุคูณ:happy:)
$7^{2541} = (8-1)^{2541} = 8k-1 = 4n+3$

[กิตติ]

$$ถ้า\quad X \equiv Y \pmod{B}\quad และ\quad X \equiv Y \pmod{C} \quad แล้ว \quad X \equiv Y \pmod{ค.ร.น.[B,C]}$$

ตรงนี้น่าสนใจมากเลยครับ ผมลองพิสูจน์ดู
$\quad X \equiv Y \pmod{B}\quad $ ดังนั้น $\quad X= MB+Y \quad$
$\quad X \equiv Y \pmod{C} \quad $ ดังนั้น $\quad X= NC+Y \quad$
ถ้า ค.ร.น. ของ$B,C$ คือ $D$ จะได้ว่า $\quad D= BP \quad ,\quad D=CQ \quad $
ดังนั้น$\quad X=\dfrac{MD}{P}+Y \quad = \dfrac{ND}{Q}+Y \quad$

ถ้า$\quad \dfrac{M}{P} และ \quad ,\quad \dfrac{N}{Q} \quad$ เป็นจำนวนเต็ม

เราเลยเขียนได้ว่า $\quad X \equiv Y \pmod{ค.ร.น.[B,C] = D} \quad$
ผมเข้าใจถูกไหมครับ.....

[Onasdi]

ถ้า$\quad \dfrac{M}{P} และ \quad ,\quad \dfrac{N}{Q} \quad$ เป็นจำนวนเต็ม
อันนี้เป็นสมมติฐานหรือว่าสรุปได้แล้วครับ?

เปลี่ยน mod เป็นการหารลงตัว ก็จะเห็นได้ด้วย $B|Z,~C|Z~\Rightarrow~[B,C]|Z$

[กิตติ]

จริงด้วยสิครับ....เปลี่ยน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 จะเท่กว่าครับ:D

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

φ(1000)=400

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

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

[PGMwindow]

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

[Onasdi]

φ(1000)=400

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

ผมลองดูแล้วตามไม่ทันเลย
มันคือ http://en.wikipedia.org/wiki/Euler's_totient_function#Computing_Euler.27s_function ครับ
เค้ากำลังใช้ทฤษฎีนี้อยู่ครับ http://en.wikipedia.org/wiki/Euler's_theorem

[IloveMathPK]

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

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

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

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

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

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

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

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

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

[polsk133]

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

[lookket]

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

[kongp]

วิชาทฤษฏีจำนวน ไม่ใช่แค่หาเศษนะครับ แต่เป็นการวิเคราะห์ระบบตัวเลข เพื่อให้คำนวนได้แม่นยำและรวดเร็ว ดังนั้น ผลหารก็สำคัญไม่น้อย น่าจะออกเป็นข้อสอบบ้าง แต่ก้นั้นถามหาเศษเหลือก็คงเพราะเป็นปัญหาคณิตศาสตร์มากกว่านั่นเอง จริงไหมครับ

[Gu_ChoewIndY]

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

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

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

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

เขียนในรูปเศษส่วน จะได้ $\frac{289}{13} = \frac{22(13) +3}{13} = \frac{22(13) }{13} + \frac{3}{13}$

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


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

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

จงหาเศษเหลือจากการหาร $3^{100}$ ด้วย $7$

เศษเหลือจาการหาร $17^{1000}$ ด้วย $13$ เป็นเท่าไร

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

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

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

[banker]

งงเหมือนกัน ว่างงอะไร

[Built]

ยากจังคะ กำลังเริ่มมองหา time machine ใช้อยู่ เพราะลูกชายขึ้นป.4 แล้ว

[เจมี่]

ตัวอย่างที่ 1

เศษเหลือที่ได้จากการหาร 2^100 ด้วย 5 เท่ากับเท่าใด

ไม่ได้ยากอะไรเลย
2^100 ≡ ? (mod 5)

2 ≡ 2 (mod 5)

2^2 ≡ 4 (mod 5)

2^3 ≡ 3 (mod 5)

〖〖(2〗^2)〗^50 ≡ 4^50(mod 5)

4^50 ≡ ? (mod 5)

4 ≡ 4 (mod 5)

4^2 ≡ 1 (mod 5) ( 16 หาร 5 เหลือเศษ 1)

〖〖(4〗^2)〗^25 ≡ 1^25(mod 5)

ตอบ เหลือ เศษ 1