ข้อนี้เคยทำเมื่อนานมากๆแล้ว ยากอยู่นะไม่คิดว่า อ.จะออกคัดค่าย 3
มีเรื่องที่ควรรู้ไว้คือ เรื่อง order ที่น่าจะสอนตามค่าย 3 ลองหาอ่านตาม Text ดูก็ได้ครับ
เดี๋ยวพิมพ์นิยาม order สั้นๆให้นะครับ
Let n be the positive integer such that n>1 and integer a such that (a,n)=1
the smallest positive integer d that $n|a^d-1$ is called the order of a modulo n
หรือเขียนแทนด้วย $o_n(a)$ สมบัติที่สำคัญของ order ที่ควรรู้คือ
1. if $a^m\equiv1(mod n)$,then $o_n(a)|m$
2. $o_n(a)|\phi(n)$ ซึ่งพิสูจน์ได้ไม่ยากครับ
กลับมาที่ข้อนี้
Let p be the smallest prime such that $p|n$
Consider number a such that $2a\equiv 1 (mod p)$
From $3^n\equiv2^n(modp)$ $(3a)^n\equiv1(mod p)$
Let d=$o_p(3a)$ so $d|p-1$ and $d|n$
เนื่องจาก $d<p$ และ p เป็นจำนวนเฉพาะที่เล็กที่สุดซึ่ง $p|n$ ทำให้ได้ว่า $d=1$
จากสมบัติของ order ทำให้ได้ว่า $3a\equiv1(modp)$ และจาก $2a\equiv 1 (mod p)$
ทำให้ได้ว่า $p|a$ ซึ่งขัดแย้งกับ $2a\equiv 1 (mod p)$
ปล.เดี๋ยวนี้ค่าย 2 ได้สอนเรื่อง order รึเปล่าครับอยากรู้