วิธีแก้ 1990 IMO Q3
สำหรับบทเรียนตามลำดับหนึ่งในแบบฝึกหัดที่ครูให้ฉันคือคำถามที่ 3 ของเอกสาร IMO ปี 1990:
ค้นหาจำนวนเต็มทั้งหมด $n>1$ ดังนั้น $\frac{2^n+1}{n^2}$ เป็นจำนวนเต็ม
ความพยายามของฉัน:
เรามี $$n^2|2^n+1\Rightarrow2^n+1\equiv0\pmod{n^2}\Rightarrow2^n\equiv-1\pmod{n^2}\Rightarrow2^{2n}\equiv1\pmod{n^2}$$ ทั้ง $\text{ord}_{n^2}(2)=1$, $\text{ord}_{n^2}(2)=2$, $\text{ord}_{n^2}(2)=d$ ที่ไหน $d|n$, หรือ $\text{ord}_{n^2}(2)=2d$ ที่ไหน $d|n$ แต่ $2d\nmid n$.
ถ้า $\text{ord}_{n^2}(2)=1$, $2^1\equiv1\pmod{n^2}$แล้ว $n^2=1\Rightarrow n=1$. สิ่งนี้ขัดแย้งกับข้อกำหนดสำหรับ$n$.
ถ้า $\text{ord}_{n^2}(2)=2$, $2^2\equiv1\pmod{n^2}$แล้ว $n^2=1$ หรือ $3$ ดังนั้น $n$ คือ $1$ หรือ $\sqrt3$. สิ่งนี้ยังขัดแย้งกับข้อกำหนดสำหรับ$n$.
ถ้า $\text{ord}_{n^2}(2)=d$ จากนั้นมีจำนวนเต็ม $k$ ดังนั้น $dm=n$. แล้ว$2^n=2^{dm}=\left(2^d\right)^m\equiv1^m=1\pmod{n^2}$. สิ่งนี้ขัดแย้ง$2^n\equiv-1$ ซึ่งเราแสดงให้เห็นก่อนหน้านี้
ดังนั้น $$\text{ord}_{n^2}(2)=2d$$
โดย Euler's Theorem $2^{\phi(n^2)}\equiv1\pmod{n^2}$ดังนั้น $2d|\phi(n^2)$. เช่น$\phi(n)=n\prod_{p|n}\frac{p-1}p=nk$ ที่ไหน $k=\prod_{p|n}\frac{p-1}p$และ $n$ และ $n^2$ แบ่งปันปัจจัยสำคัญเดียวกันที่เรามี $$\phi(n^2)=n^2\prod_{p|n}\frac{p-1}p=n\left(n\prod_{p|n}\frac{p-1}p\right)=n(nk)=n\phi(n)$$
ดำเนินการต่อ
$$2d|\phi(n^2)\Rightarrow2d|n\phi(n)\Rightarrow2|m\phi(n)$$
ที่ไหน $dm=n$. ซึ่งหมายความว่าอย่างใดอย่างหนึ่ง$m$ เป็นคู่ (ซึ่งหมายความว่า $n$ เป็นคู่) หรือ $\phi(n)$ เป็นคู่
น่าเสียดายที่ฉันยังห่างไกลจากการแก้ปัญหาอย่างแท้จริง มันชัดเจนว่าแสดง$n$ เป็นคู่หรือ $\phi(n)$ แม้จะไม่เพียงพอที่จะแสดงให้เห็นว่า $\frac{2^n+1}{n^2}$ เป็นจำนวนเต็ม (ตัวอย่างเช่น $n=4$ และ $n=5$). มีตัวเลขมากมายที่ตรงตามเงื่อนไขที่ฉันวางไว้ อย่างไรก็ตามฉันไม่แน่ใจว่าจะต้องดำเนินการอย่างไรดังนั้นฉันจึงต้องการความช่วยเหลือในการจบคำถาม
คำตอบ
$\textbf{Hint:}$พิจารณาตัวหารเฉพาะที่เล็กที่สุดของ $n$.
จากนั้นใช้เลมมา "กำลังยกกำลัง"
จากนั้นพิจารณาไพรม์ที่เล็กที่สุดอันดับสองของ $n$
ในตอนแรกให้พิจารณาตัวหารเฉพาะที่เล็กที่สุดพูด $p$ ของ $n$. มันไม่ได้ $2$. จากนั้น$2^{2n}=1 \pmod {p}$แต่ยังโดย FLT $2^{p-1}=1 \pmod {p}$.
ทั้งสองรวมกันเป็นนัยว่า $2^{gcd(p-1,2n)}=1 \pmod {p}$.แต่ตอนนี้, $gcd(p-1,2n)=2$ ตั้งแต่ไพรม์อื่น ๆ ของ $n$ จะใหญ่กว่า $p-1$นี่หมายความว่า $3$ จะต้องเป็นไพรม์ที่เล็กที่สุดของ $n$ .ตั้งแต่ $2^2=1 \pmod{p}$ จากข้างบน.
ตอนนี้อนุมานโดยใช้ว่าการยกคำขยายเลขชี้กำลังที่มีอำนาจสูงสุด $3$ หาร $n$ คือ $1$จากนั้นพิจารณาไพรม์ที่เล็กที่สุดของ $n/3$.
ใช้อาร์กิวเมนต์ที่คล้ายกันข้างต้นเพื่อแสดงว่าจะต้องเป็น $7$. แต่จากข้อเท็จจริงที่ว่า $3 \mid n$ แสดงว่ามันไม่สามารถเกิดขึ้นได้ดังนั้นทางออกเดียวก็คือ $n=3$
(รายละเอียดเป็นสิ่งที่จำเป็นเนื่องจากฉันเขียนไว้เพื่อใช้เป็นคำใบ้)
สำหรับวิธีแก้ปัญหาโดยละเอียดดูที่นี่: aops