Congruence in POSN book

[Metamorphosis]

ให้ $p$ เป็นจำนวนเฉพาะและ $h+k=p-1$ เมื่อ $h,k \geqslant 0$ พิสูจน์

$$h!k!+(-1)^h \equiv 0 \pmod{p}$$

ถ้า $p$ เป็นจำนวนเฉพาะ จงพิสูจน์ว่า $(p-1)!+1 = p^k$ สำหรับ บางจำนวนเต็ม $k$ ก็ต่อเมื่อ $p=2,3,5$

[PP_nine]

ข้อแรกเป็นจริงเฉพาะจำนวนเฉพาะคี่นะครับ

พิสูจน์โดยการเปลี่ยน $k=p-1-h$ แล้วกระจายแฟคทอเรียลออกมาก็จบแล้วครับ

ส่วนข้อสองก็เริ่มจากพิสูจน์ว่า $p=2,3,5$ ใช้ได้

ต่อไปสมมติว่ามีจำนวนเฉพาะ $p \ge 7$ ที่ทำให้มีจำนวนนับ $k$ ซึ่งสอดคล้องสมการ

ชัดเจนว่า $(p-1)!+1>p$ แสดงว่า ถ้ามีจำนวนนับ $k$ ดังกล่าวแล้ว $k \ge 2$

จากนั้นก็พิจารณาคอนกรูเอนซ์ $(p-1)! \equiv -1 \pmod{p^2}$

และก็ใช้ Inverse Modulo แก้นิดหน่อย

hint#2

$a$ จะมี inverse modulo $n$ iff $(a,n)=1$

แล้ววิธีทำก็เหมือนกับการพิสูจน์ Wilson's Theorem ทุกประการ (โดยใช้ inverse) เพื่อหาข้อขัดแย้ง

[PP_nine]

วันนี้เพิ่งเปิดไปเจอเฉลยแบบธรรมดา เลยมาเฉลยให้ เพราะน่าจะเข้าใจง่ายกว่าแบบ inverse

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

ถ้า $p$ เป็นจำนวนเฉพาะ จงพิสูจน์ว่า $(p-1)!+1 = p^k$ สำหรับ บางจำนวนเต็ม $k$ ก็ต่อเมื่อ $p=2,3,5$

$(\Leftarrow )$ แสดงได้ไม่ยากว่า $p=2,3,5$ สอดคล้องสมการดังกล่าวสำหรับบางจำนวนนับ $k$

$(\Rightarrow )$ สมมติว่ามีจำนวนเฉพาะ $p>5$ ที่ทำให้มีจำนวนนับ $k$ ซึ่งสอดคล้องสมการดังกล่าว

ดังนั้น $(p-1)!=p^k-1$

$(p-2)!=p^{k-1}+p^{k-2}+\cdots+1$

$(p-2)!=(p^{k-1}-1)+(p^{k-2}-1)+\cdots+(p-1)+k$

$\therefore (p-2)! \equiv k \pmod{p-1}$

เนื่องจาก $p$ เป็นจำนวนเฉพาะคี่ แสดงว่ามีบางจำนวนนับ $m$ ซึ่ง $p-1=2m$

ชัดเจนว่า $2 \cdot m|(p-2)!$ และ $2 \cdot m|(p-1)$

ดังนั้น $2m|k$ หรือก็คือ $(p-1)|k$ เช่นกัน

พิจารณาสมการเดิม, $(p-1)(p-2) \cdots (3)(2)(1) = \underbrace{p \cdot p \cdots p}_{k} -1$

ชัดเจนว่าเป็นไปไม่ได้ที่ $k \ge p=1$ ไม่เช่นนั้นจะทำให้ $p^{k}-1>(p-1)(p-2)\cdots(3)(2)(1)$ สำหรับทุก $p>5$

ดังนั้น $k<p-1$ ขัดแย้งกับที่ $(p-1)|k$

[polsk133]

อินเวอสมอดุโลอ่านจากไหนหรอครับ

[PP_nine]

ลองดูในนี้เป็นแนวเอาครับ (จริงๆสามารถขยายไปยังมอดุโลที่ไม่ใช่จำนวนเฉพาะก็ได้ครับ)

Inverse modulo

ถ้าขยายไปยังมอดุโลจำนวนนับ $n$ ใดๆแล้ว

$a$ จะมี inverse modulo $n$ ได้ก็ต่อเมื่อ $(a,n)=1$