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

[กิตติ]

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

[Siren-Of-Step]

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

โดยทั่วไปแล้ว $\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]

ข้อความเดิมเขียนโดยคุณ Siren-Of-Step

เราจะหาตัวน้อยสุดได้ไหมครับ ซึ่ง $a^n \equiv 1 \pmod{m}$

ผมคิดว่าไม่มีวิธีทั่วไปนะครับ ไม่แน่ใจเหมือนกัน

[Siren-Of-Step]

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

[Onasdi]

ข้อความเดิมเขียนโดยคุณ Siren-Of-Step

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

ใช่แล้วครับ นั่นเป็นเงื่อนไขของทฤษฎี

ถ้า $(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-]

ข้อความเดิมเขียนโดยคุณ 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$

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

[กิตติ]

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

$$ถ้า\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ไปเป็นการหารลงตัว
เข้าใจแล้วครับ วันนี้ได้ความรู้เพิ่มอีกอย่างหนึ่งแล้ว
ขอบคุณครับ

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

คุณกิติครับ คุณหาหนังสือจากไหนหรอครับ

ผมอยากหาลองมาอ่านดูตอนที่ผมยังไม่เก่งเลย

ขอบคุณครับ