เคยออกเป็นข้อสอบค่ายอยู่นะครับ ลองไปเปิดหาข้อสอบค่ายปีเก่าๆในนี้ดู
วิธีทำเหมือนข้างบนแหละครับ แต่เอามาเขียนอีกแบบ
Lemma ที่ useful ตัวนึง
ถ้า $p|x^k-y^k$ และ $p|x^l-y^l$ โดยที่ $\gcd(x,y) = 1$ แล้ว $p|x^{\gcd(k,l)}-y^{\gcd(k,l)}$
ต่อมาครับ สมมติว่ามี $n$ ซึ่ง $n | 3^n-2^n$
1) สมมติ $p$ เป็นจำนวนเฉพาะที่น้อยที่สุดที่ $p|n$ (Keyword คือบรรทัดนี้ครับ)
2) จะได้ $p | 3^n-2^n$ และ $p| 3^{p-1} - 2^{p-1}$ ดังนั้น $p| 3^{\gcd(p-1,n)} - 2^{\gcd(p-1,n)}$
3) แต่ $\gcd (p-1,n)$ เป็นจำนวนที่หาร $n$ ลงตัวและน้อยกว่า $p$ ด้วย ดังนั้นมีสองกรณี
ถ้า $\gcd(p-1,n) \neq 1$ แสดงว่ามีจำนวนเฉพาะอื่นที่น้อยกว่า $p$ และหาร $n$ ลงตัว
ถ้า $\gcd(p-1,n) = 1$ แปลว่า $p | 1$ เลยขัดแย้งครับ
__________________
----/---~Alice~ จงรับรู้ไว้ ชื่อแห่งสีสันหนึ่งเดียวที่แสดงผล
---/---- ~Blue~ นี่คือ สีแห่งความหลังอันกว้างใหญ่ของเว็บบอร์ดนี้
29 เมษายน 2018 19:52 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ Thgx0312555
|