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

[กะทิบูด]

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

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

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

[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}$
แต่เรายังสรุปไม่ได้ว่ามันเป็นค่าที่มากที่สุดแล้ว

ป.ล. เห็นคุณกิตติสอนลูก เลยอยากแนะนำบทความนี้ครับ เกี่ยวกับระบบการศึกษาวิชาคณิตศาสตร์ครับ แต่มันเป็นภาษาอังกฤษนะครับ

[หยินหยาง]

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

[กิตติ]

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

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

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