Bagaimana mengatasi 1990 IMO Q3
Untuk pelajaran saya tentang pesanan, salah satu latihan yang diberikan guru saya adalah Pertanyaan 3 dari makalah IMO 1990:
Temukan semua bilangan bulat $n>1$ seperti yang $\frac{2^n+1}{n^2}$ adalah bilangan bulat.
Upaya saya:
Kita punya $$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}$$ Antara $\text{ord}_{n^2}(2)=1$, $\text{ord}_{n^2}(2)=2$, $\text{ord}_{n^2}(2)=d$ dimana $d|n$, atau $\text{ord}_{n^2}(2)=2d$ dimana $d|n$ tapi $2d\nmid n$.
Jika $\text{ord}_{n^2}(2)=1$, $2^1\equiv1\pmod{n^2}$, kemudian $n^2=1\Rightarrow n=1$. Ini bertentangan dengan persyaratan untuk$n$.
Jika $\text{ord}_{n^2}(2)=2$, $2^2\equiv1\pmod{n^2}$, kemudian $n^2=1$ atau $3$ begitu $n$ adalah $1$ atau $\sqrt3$. Ini juga bertentangan dengan persyaratan untuk$n$.
Jika $\text{ord}_{n^2}(2)=d$ lalu ada integer $k$ seperti yang $dm=n$. Kemudian$2^n=2^{dm}=\left(2^d\right)^m\equiv1^m=1\pmod{n^2}$. Ini bertentangan$2^n\equiv-1$ yang kami tunjukkan sebelumnya.
Karena itu $$\text{ord}_{n^2}(2)=2d$$
Dengan Teorema Euler $2^{\phi(n^2)}\equiv1\pmod{n^2}$, jadi $2d|\phi(n^2)$. Sebagai$\phi(n)=n\prod_{p|n}\frac{p-1}p=nk$ dimana $k=\prod_{p|n}\frac{p-1}p$, dan $n$ dan $n^2$ berbagi faktor prima yang sama, kita punya $$\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)$$
Melanjutkan,
$$2d|\phi(n^2)\Rightarrow2d|n\phi(n)\Rightarrow2|m\phi(n)$$
Dimana $dm=n$. Ini berarti baik$m$ adalah genap (yang menyiratkan $n$ genap) atau $\phi(n)$ genap.
Sayangnya, saya masih jauh dari benar-benar menyelesaikan masalah. Itu jelas menunjukkan itu$n$ adalah genap atau $\phi(n)$ Bahkan tidak cukup untuk menunjukkan itu $\frac{2^n+1}{n^2}$ adalah bilangan bulat (counterexamples include $n=4$ dan $n=5$). Ada banyak angka tak terhingga yang memenuhi syarat yang saya berikan. Namun, saya tidak yakin bagaimana melanjutkannya, jadi saya membutuhkan bantuan untuk menyelesaikan pertanyaan ini.
Jawaban
$\textbf{Hint:}$Pertimbangkan pembagi prima terkecil dari $n$.
Kemudian gunakan lemma "mengangkat eksponen".
Kemudian pertimbangkan lagi bilangan prima terkecil kedua dari $n$
Pertama-tama perhatikan pembagi prima terkecil katakanlah $p$ dari $n$Tidak mungkin $2$. Kemudian,$2^{2n}=1 \pmod {p}$, tetapi juga dengan FLT $2^{p-1}=1 \pmod {p}$.
Keduanya bersama-sama menyiratkan itu $2^{gcd(p-1,2n)}=1 \pmod {p}$.Tapi sekarang, $gcd(p-1,2n)=2$ sejak, bilangan prima lainnya dari $n$ akan lebih besar dari $p-1$.Ini menyiratkan itu $3$ harus menjadi bilangan prima terkecil dari $n$ .sejak $2^2=1 \pmod{p}$ dari atas.
Sekarang simpulkan dengan mengangkat eksponen lemma dengan pangkat tertinggi $3$ pemisah $n$ adalah $1$Kemudian, pertimbangkan bilangan prima terkecil dari $n/3$.
Gunakan argumen serupa seperti di atas untuk menunjukkan bahwa itu harus $7$Tapi dari fakta itu $3 \mid n$ menunjukkan bahwa itu tidak mungkin terjadi. Jadi, satu-satunya solusi adalah $n=3$
(detail dihapus sejak saya menulisnya untuk dijadikan petunjuk)
Untuk solusi rinci, lihat di sini: aops