Wie man 1990 IMO Q3 löst

Question

Für meine Unterrichtsstunde war eine der Übungen, die mir mein Lehrer gab, Frage 3 des IMO-Papiers von 1990:

Finde alle ganzen Zahlen $n>1$ so dass $\frac{2^n+1}{n^2}$ ist eine ganze Zahl.

Mein Versuch:

---

Wir haben $$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}$$ Entweder $\text{ord}_{n^2}(2)=1$, $\text{ord}_{n^2}(2)=2$, $\text{ord}_{n^2}(2)=d$ wo $d|n$, oder $\text{ord}_{n^2}(2)=2d$ wo $d|n$ aber $2d\nmid n$.

Wenn $\text{ord}_{n^2}(2)=1$, $2^1\equiv1\pmod{n^2}$, dann $n^2=1\Rightarrow n=1$. Dies widerspricht den Anforderungen für$n$.

Wenn $\text{ord}_{n^2}(2)=2$, $2^2\equiv1\pmod{n^2}$, dann $n^2=1$ oder $3$ damit $n$ ist $1$ oder $\sqrt3$. Dies widerspricht auch den Anforderungen für$n$.

Wenn $\text{ord}_{n^2}(2)=d$ dann existiert eine ganze Zahl $k$ so dass $dm=n$. Dann$2^n=2^{dm}=\left(2^d\right)^m\equiv1^m=1\pmod{n^2}$. Dies widerspricht$2^n\equiv-1$ was wir früher gezeigt haben.

Deshalb $$\text{ord}_{n^2}(2)=2d$$

Nach dem Satz von Euler $2^{\phi(n^2)}\equiv1\pmod{n^2}$, damit $2d|\phi(n^2)$. Wie$\phi(n)=n\prod_{p|n}\frac{p-1}p=nk$ wo $k=\prod_{p|n}\frac{p-1}p$, und $n$ und $n^2$ teilen die gleichen Primfaktoren, die wir haben $$\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)$$

Auch weiterhin,

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

Wo $dm=n$. Dies bedeutet entweder$m$ ist gerade (was impliziert $n$ ist gerade) oder $\phi(n)$ ist gerade.

---

Leider bin ich noch weit davon entfernt, das Problem tatsächlich zu lösen. Es ist klar, dass zeigen$n$ ist gerade oder $\phi(n)$ ist sogar nicht ausreichend, um das zu zeigen $\frac{2^n+1}{n^2}$ ist eine ganze Zahl (Gegenbeispiele umfassen $n=4$ und $n=5$). Es gibt unendlich viele Zahlen, die die von mir festgelegten Bedingungen erfüllen. Ich bin mir jedoch nicht sicher, wie ich vorgehen soll, daher möchte ich Unterstützung bei der Beantwortung der Frage.

Answer 1

$\textbf{Hint:}$Betrachten Sie den kleinsten Primteiler von $n$.

Verwenden Sie dann das Lemma "Heben des Exponenten".

Betrachten Sie dann noch einmal die zweitkleinste Primzahl von $n$

Betrachten Sie zunächst den kleinsten Primteiler sagen $p$ von $n$Es kann nicht sein $2$. Dann,$2^{2n}=1 \pmod {p}$, aber auch von FLT $2^{p-1}=1 \pmod {p}$.

Diese beiden zusammen implizieren das $2^{gcd(p-1,2n)}=1 \pmod {p}$.Aber jetzt, $gcd(p-1,2n)=2$ da jede andere Primzahl von $n$ wäre größer als $p-1$Dies impliziert das $3$ muss die kleinste Primzahl von sein $n$ .schon seit $2^2=1 \pmod{p}$ von oben.

Leiten Sie nun daraus das Exponenten-Lemma ab, das die höchste Potenz von $3$ Teilen $n$ ist $1$Betrachten Sie dann die kleinste Primzahl von $n/3$.

Verwenden Sie ein ähnliches Argument wie oben, um zu zeigen, dass es sein muss $7$Aber von der Tatsache, dass $3 \mid n$ zeigen, dass das nicht passieren kann. Also wäre die einzige Lösung $n=3$

(Details werden weggelassen, da ich es geschrieben habe, um es als Hinweis zu dienen)

Eine detaillierte Lösung finden Sie hier: aops