Jak rozwiązać 1990 IMO Q3

Aug 16 2020

W przypadku mojej lekcji na zamówienie, jednym z ćwiczeń, które dał mi mój nauczyciel, było pytanie 3 z artykułu IMO z 1990 roku:

Znajdź wszystkie liczby całkowite $n>1$ takie że $\frac{2^n+1}{n^2}$ jest liczbą całkowitą.

Moja próba:


Mamy $$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}$$ Zarówno $\text{ord}_{n^2}(2)=1$, $\text{ord}_{n^2}(2)=2$, $\text{ord}_{n^2}(2)=d$ gdzie $d|n$lub $\text{ord}_{n^2}(2)=2d$ gdzie $d|n$ ale $2d\nmid n$.

Gdyby $\text{ord}_{n^2}(2)=1$, $2^1\equiv1\pmod{n^2}$, następnie $n^2=1\Rightarrow n=1$. Jest to sprzeczne z wymaganiami$n$.

Gdyby $\text{ord}_{n^2}(2)=2$, $2^2\equiv1\pmod{n^2}$, następnie $n^2=1$ lub $3$ więc $n$ jest $1$ lub $\sqrt3$. Jest to również sprzeczne z wymaganiami$n$.

Gdyby $\text{ord}_{n^2}(2)=d$ wtedy istnieje liczba całkowita $k$ takie że $dm=n$. Następnie$2^n=2^{dm}=\left(2^d\right)^m\equiv1^m=1\pmod{n^2}$. To zaprzecza$2^n\equiv-1$ które pokazaliśmy wcześniej.

W związku z tym $$\text{ord}_{n^2}(2)=2d$$

Według twierdzenia Eulera $2^{\phi(n^2)}\equiv1\pmod{n^2}$, więc $2d|\phi(n^2)$. Tak jak$\phi(n)=n\prod_{p|n}\frac{p-1}p=nk$ gdzie $k=\prod_{p|n}\frac{p-1}p$, i $n$ i $n^2$ mają te same czynniki pierwsze $$\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)$$

Kontynuacja,

$$2d|\phi(n^2)\Rightarrow2d|n\phi(n)\Rightarrow2|m\phi(n)$$

Gdzie $dm=n$. To znaczy albo$m$ jest parzysta (co implikuje $n$ jest parzysta) lub $\phi(n)$ jest równa.


Niestety nadal daleko mi do rozwiązania problemu. To jasne, że widać$n$ jest równa lub $\phi(n)$ to nawet nie wystarczy, aby to wykazać $\frac{2^n+1}{n^2}$ jest liczbą całkowitą (kontrprzykłady obejmują $n=4$ i $n=5$). Istnieje nieskończenie wiele liczb spełniających określone przeze mnie warunki. Nie jestem jednak pewien, jak postępować, dlatego chciałbym uzyskać pomoc w dokończeniu pytania.

Odpowiedzi

Yesit'sme Aug 16 2020 at 11:34

$\textbf{Hint:}$Rozważmy najmniejszy pierwszy dzielnik $n$.

Następnie użyj lematu „podnoszenie wykładnika”.

Następnie ponownie rozważ drugą najmniejszą liczbę pierwszą $n$

Najpierw rozważmy najmniejszy pierwszy dzielnik $p$ z $n$To niemożliwe $2$. Następnie,$2^{2n}=1 \pmod {p}$, ale także przez FLT $2^{p-1}=1 \pmod {p}$.

Te dwa razem oznaczają, że $2^{gcd(p-1,2n)}=1 \pmod {p}$.Ale teraz, $gcd(p-1,2n)=2$ ponieważ każda inna liczba pierwsza z $n$ byłby większy niż $p-1$.To daje do zrozumienia ze $3$ musi być najmniejszą liczbą pierwszą $n$ .od $2^2=1 \pmod{p}$ z góry.

Teraz wywnioskuj, używając lematu podnoszącego wykładnik, który ma najwyższą moc $3$ działowy $n$ jest $1$Następnie rozważ najmniejszą liczbę pierwszą z $n/3$.

Użyj podobnego argumentu jak powyżej, aby pokazać, że tak musi być $7$Ale z tego faktu $3 \mid n$ pokaż, że to nie może się zdarzyć, więc jedynym rozwiązaniem byłoby $n=3$

(szczegóły są pomijane, ponieważ napisałem to, aby służyć jako podpowiedź)

Szczegółowe rozwiązanie znajduje się tutaj: aops