|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#91
|
||||
|
||||
ผมคงต้องกลับไปดูเรื่องของEuler's theoremให้เข้าใจมากกว่าตอนนี้ก่อนแล้วจะรบกวนถามครับ
ขอบคุณครับคุณOnasdiที่ยกตัวอย่างให้เห็น
__________________
"ถ้าเราล้มบ่อยๆ ในที่สุดเราจะรู้ว่าถ้าจะล้ม ล้มท่าไหนจะเจ็บน้อยที่สุด และรู้อีกว่าต่อไปทำยังไงจะไม่ให้ล้มอีก ดังนั้นจงอย่ากลัวที่จะล้ม"...อาจารย์อำนวย ขนันไทย ครั้งแรกในชีวิตที่สอบคณิตสมาคมคณิตศาสตร์เมื่อปี2533...ผมได้แค่24คะแนน(จากร้อยคะแนน) |
#92
|
||||
|
||||
อ้างอิง:
01 ตุลาคม 2010 18:59 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ Siren-Of-Step |
#93
|
||||
|
||||
ผมคิดว่าไม่มีวิธีทั่วไปนะครับ ไม่แน่ใจเหมือนกัน
|
#94
|
||||
|
||||
ถามหน่อยครับ $a^{\phi (n)} \equiv 1 \pmod{n}$
$a,n$ ต้องเป็น co-prime ใช่ปะครับ
__________________
Fortune Lady
|
#95
|
||||
|
||||
อ้างอิง:
ถ้า $(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}$ |
#96
|
||||
|
||||
มีทฤษฎี/เทคนิค อย่างอื่นไหมครับ ที่ช่วยในการทำโจทย์เร็วขึ้น
__________________
Fortune Lady
|
#97
|
||||
|
||||
น่าจะมีเยอะครับ ต้องทำโจทย์เยอะๆถึงได้พวกเทคนิคครับ
เทคนิคนึงที่คิดออกคือการแยกตัวประกอบของตัวหาร เช่นถ้าเราจะหา $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}$ 03 ตุลาคม 2010 03:11 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ Onasdi |
#98
|
||||
|
||||
จริงๆผมน่าจะเอ๊ะใจตามที่คุณ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$ ไม่รู้ว่าผมเข้าใจตรงไหนผิดหรือเปล่า.....
__________________
"ถ้าเราล้มบ่อยๆ ในที่สุดเราจะรู้ว่าถ้าจะล้ม ล้มท่าไหนจะเจ็บน้อยที่สุด และรู้อีกว่าต่อไปทำยังไงจะไม่ให้ล้มอีก ดังนั้นจงอย่ากลัวที่จะล้ม"...อาจารย์อำนวย ขนันไทย ครั้งแรกในชีวิตที่สอบคณิตสมาคมคณิตศาสตร์เมื่อปี2533...ผมได้แค่24คะแนน(จากร้อยคะแนน) 03 ตุลาคม 2010 10:23 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ กิตติ |
#99
|
||||
|
||||
ลองให้$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} $ ผมลองคิดต่อเล่นๆเท่านั้น....
__________________
"ถ้าเราล้มบ่อยๆ ในที่สุดเราจะรู้ว่าถ้าจะล้ม ล้มท่าไหนจะเจ็บน้อยที่สุด และรู้อีกว่าต่อไปทำยังไงจะไม่ให้ล้มอีก ดังนั้นจงอย่ากลัวที่จะล้ม"...อาจารย์อำนวย ขนันไทย ครั้งแรกในชีวิตที่สอบคณิตสมาคมคณิตศาสตร์เมื่อปี2533...ผมได้แค่24คะแนน(จากร้อยคะแนน) |
#100
|
||||
|
||||
อ้างอิง:
สิ่งที่ผมใช้คือ $$ถ้า\quad X \equiv Y \pmod{B}\quad และ\quad X \equiv Y \pmod{C} \quad แล้ว \quad X \equiv Y \pmod{ค.ร.น.[B,C]}$$ลองดูครับว่าทำไมถึงจริง |
#101
|
||||
|
||||
อ้างอิง:
$7^{2541} = (8-1)^{2541} = 8k-1 = 4n+3$
__________________
เวลาที่เหลืออยู่มีวิธีการใช้สองแบบ คือ ทางที่เรียบง่ายไม่มีอะไร กับอีกทาง ที่ทุกอย่างล้วนมหัศจรรย์ |
#102
|
||||
|
||||
อ้างอิง:
$\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$ ผมเข้าใจถูกไหมครับ.....
__________________
"ถ้าเราล้มบ่อยๆ ในที่สุดเราจะรู้ว่าถ้าจะล้ม ล้มท่าไหนจะเจ็บน้อยที่สุด และรู้อีกว่าต่อไปทำยังไงจะไม่ให้ล้มอีก ดังนั้นจงอย่ากลัวที่จะล้ม"...อาจารย์อำนวย ขนันไทย ครั้งแรกในชีวิตที่สอบคณิตสมาคมคณิตศาสตร์เมื่อปี2533...ผมได้แค่24คะแนน(จากร้อยคะแนน) |
#103
|
||||
|
||||
อ้างอิง:
เปลี่ยน mod เป็นการหารลงตัว ก็จะเห็นได้ด้วย $B|Z,~C|Z~\Rightarrow~[B,C]|Z$ |
#104
|
||||
|
||||
จริงด้วยสิครับ....เปลี่ยนmodไปเป็นการหารลงตัว
เข้าใจแล้วครับ วันนี้ได้ความรู้เพิ่มอีกอย่างหนึ่งแล้ว ขอบคุณครับ
__________________
"ถ้าเราล้มบ่อยๆ ในที่สุดเราจะรู้ว่าถ้าจะล้ม ล้มท่าไหนจะเจ็บน้อยที่สุด และรู้อีกว่าต่อไปทำยังไงจะไม่ให้ล้มอีก ดังนั้นจงอย่ากลัวที่จะล้ม"...อาจารย์อำนวย ขนันไทย ครั้งแรกในชีวิตที่สอบคณิตสมาคมคณิตศาสตร์เมื่อปี2533...ผมได้แค่24คะแนน(จากร้อยคะแนน) |
#105
|
||||
|
||||
คุณกิติครับ คุณหาหนังสือจากไหนหรอครับ
ผมอยากหาลองมาอ่านดูตอนที่ผมยังไม่เก่งเลย ขอบคุณครับ |
|
|