Come risolvere 1990 IMO Q3

Aug 16 2020

Per la mia lezione su ordinazione, uno degli esercizi che il mio insegnante mi ha dato è stata la domanda 3 del documento IMO del 1990:

Trova tutti i numeri interi $n>1$ tale che $\frac{2^n+1}{n^2}$ è un numero intero.

Il mio tentativo:


abbiamo $$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}$$ O $\text{ord}_{n^2}(2)=1$, $\text{ord}_{n^2}(2)=2$, $\text{ord}_{n^2}(2)=d$ dove $d|n$, o $\text{ord}_{n^2}(2)=2d$ dove $d|n$ ma $2d\nmid n$.

Se $\text{ord}_{n^2}(2)=1$, $2^1\equiv1\pmod{n^2}$, poi $n^2=1\Rightarrow n=1$. Ciò contraddice i requisiti per$n$.

Se $\text{ord}_{n^2}(2)=2$, $2^2\equiv1\pmod{n^2}$, poi $n^2=1$ o $3$ così $n$ è $1$ o $\sqrt3$. Ciò contraddice anche i requisiti per$n$.

Se $\text{ord}_{n^2}(2)=d$ allora esiste un numero intero $k$ tale che $dm=n$. Poi$2^n=2^{dm}=\left(2^d\right)^m\equiv1^m=1\pmod{n^2}$. Questo contraddice$2^n\equiv-1$ che abbiamo mostrato in precedenza.

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

Dal teorema di Eulero $2^{\phi(n^2)}\equiv1\pmod{n^2}$, così $2d|\phi(n^2)$. Come$\phi(n)=n\prod_{p|n}\frac{p-1}p=nk$ dove $k=\prod_{p|n}\frac{p-1}p$, e $n$ e $n^2$ condividiamo gli stessi fattori primi, abbiamo $$\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)$$

Continuando,

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

Dove $dm=n$. Questo significa neanche$m$ è pari (il che implica $n$ è pari) o $\phi(n)$ è anche.


Sfortunatamente, sono ancora lontano dal risolvere il problema. È chiaro questo spettacolo$n$ è pari o $\phi(n)$ non è nemmeno sufficiente per dimostrarlo $\frac{2^n+1}{n^2}$ è un numero intero (i controesempi includono $n=4$ e $n=5$). Ci sono infiniti numeri che soddisfano le condizioni che ho stabilito. Tuttavia, non sono sicuro di come procedere, quindi desidero assistenza per completare la domanda.

Risposte

Yesit'sme Aug 16 2020 at 11:34

$\textbf{Hint:}$Considera il più piccolo primo divisore di $n$.

Quindi utilizzare il lemma "sollevamento esponente".

Quindi considera di nuovo il secondo numero primo più piccolo di $n$

In un primo momento si consideri il più piccolo primo divisore diciamo $p$ di $n$Non può essere $2$. Poi,$2^{2n}=1 \pmod {p}$, ma anche da FLT $2^{p-1}=1 \pmod {p}$.

Questi due insieme lo implicano $2^{gcd(p-1,2n)}=1 \pmod {p}$.Ma ora, $gcd(p-1,2n)=2$ da allora, qualsiasi altro numero primo di $n$ sarebbe più grande di $p-1$.Questo implica che $3$ deve essere il numero primo più piccolo di $n$ .da $2^2=1 \pmod{p}$ da sopra.

Ora deduci usando quell'aumento del lemma esponente di cui è la più alta potenza $3$ dividendo $n$ è $1$Quindi, considera il numero primo più piccolo di $n/3$.

Usa un argomento simile come sopra per mostrare che deve essere $7$.Ma dal fatto che $3 \mid n$ dimostrare che ciò non può accadere, quindi l'unica soluzione sarebbe $n=3$

(i dettagli sono impegnati da quando l'ho scritto per servirlo come suggerimento)

Per una soluzione dettagliata, vedere qui: aops