n tale che esista m

[Luca Milanese]

Questo problema fu postato sul forum un po' di anni fa, ma nessuno rispose mai con una soluzione completa. L'ho trovato davvero istruttivo, quindi ve lo ripropongo:
Determinare tutti gli n interi positivi tali che esista m intero per cui [math]2^n-1 | m^2+9.
Buon lavoro^3.

[Luca Milanese]

Lascio un hint:

Testo nascosto:

Cosa si può dire dei divisori primi di un numero della forma [math]a^2+b^2?

[Luca Milanese]

UP!

[Maionsss]

UP!

n potenza di 2?

[Luca Milanese]

Giusto! Vai con la dimostrazione.

[Maionsss]

Testo nascosto:

Dimostro innanzitutto che non esiste $ x >1$ dispari tale che $ x|n $. Supponiamo per assurdo che esista un tale $x$ , allora avremmo : $ x \ge3$ e quindi $2^{x} -1 \equiv3 \pmod{4}$ e ciò ci assicura che esiste $p\in \mathbb{P}$ con $p \equiv3\pmod{4}$ tale che $p|2^{x} -1$. Poiché $2^{x}-1 | 2^{n} -1 | m^{2} +3^{2}$ abbiamo che $p| m^{2} + 3^{2}$ che , insieme a $p\equiv3\pmod{4} $ ci dice (per un fatto abbastanza noto) che $p|3$ quindi $p=3$; siamo giunti ad un assurdo in quanto $3\not| 2^{x} -1\equiv1\pmod3$
Mostriamo ora che detto $n=2^{k} \exists m \in\mathbb{Z} : 2^{2^{k}} -1| m^{2} +9$. Procedo per induzione su $k$ :
Passo base) Per $k=1$ basta prendere $m \equiv0\pmod{3}$.
Passo induttivo) Osserviamo innanzitutto che posso scrivere $ 2^{2^{k+1}}-1=(2^{2^{k}} +1)(2^{2^{k}}-1)$. Ora, esiste $a$ intero tale che $2^{2^{k}}-1 | a^{2}+9$ per ipotesi induttiva , mentre mi basta prendere $b=3 \times (2^{2^{k-1}})$ per avere $2^{2^{k}} +1| b^{2}+9$. Utilizziamo infine il Teorema Cinese del Resto per dire che $\exists m: m\equiv{a}\pmod{2^{2^{k}}-1} \land m\equiv{b}\pmod{2^{2^{k}}+1}$ perché $ M.C.D.(2^{2^{k}}+1, 2^{2^{k}}-1)=M.C.D.(2^{2^{k}}+1,2)=1$ $ $

Ho dato una risistemata alla seconda parte, ora dovremmo esserci

[Luca Milanese]

mi basta prendere $b=3 \times (2^{2^{k}} +1)$ per avere $2^{2^{k}} +1| b^{2}+9$.

Questo passaggio non mi torna, puoi spiegare meglio?

[Maionsss]

Ah sisi ho sbagliato a scrivere... Provvedo subito

[Luca Milanese]

Direi che ora va bene.