[จูกัดเหลียง]

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

เห็นว่าเป็นกระทู้เตรียม TMO ขอใส่เต็มเลยละกัน (ใครเพิ่งจบค่าย 1 ก็อย่าเพิ่งท้อล่ะครับ ^^)
4. สำหรับจำนวนเต็ม $a$ และจำนวนนับ $n \ge 2$ พิสูจน์ว่า $a$ มี inverse modulo $n$ ก็ต่อเมื่อ $(a,n)=1$ เท่านั้น

ลองมั่วๆไปก่อนนะครับ

ขาไป ให้ $a\in\mathbb{N}$ เเละ $n\ge 2\in\mathbb{N}$ ที่ทำให้ $a$ มีอินเวิร์ส
นั่นคือ มี $b\in\mathbb{I}$ ที่ $ab\equiv 1 \pmod n\therefore nx=ab-1 \exists x\in\mathbb{I}$
จัดรูป จะได้ว่า $ab+n(-x)=1\therefore (a,n)=1$

ขากลับ ให้ $(a,n)=1\therefore ax+ny=1 \rightarrow n|{ab-1}\rightarrow ab\equiv 1 \pmod n$ จึงมี $b\in\mathbb{I}$ ที่เป็นอินเวอร์สของเอ ในมอดุโล $n$

ปล.ขอบคุณข้อสอบนะครับ ( เเล้วก็เช็คความมั่วของผมหน่อยครับ ) เเล้วก็ ข้อสองที่เป็นวงเล็บปีกกาคือไรอ่ะครับ