Bagaimana mengatasi 1990 IMO Q3

Aug 16 2020

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

Yesit'sme Aug 16 2020 at 11:34

$\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