BST 2009/2 (ITA)

[Karl Zsigmondy]

Trovare tutti gli n interi positivi per cui esiste m intero positivo tali che:
$ \displaystyle\frac{4^n-1}{3} \mid (49m^2 + 1). $

L'ho postato perché si sfrutta un'idea (o tecnica, come la si vuole chiamare) abbastanza interessante. O almeno nella mia dimostrazione. Si accettano anche spunti.

EDIT: piccola modifica di leggibilità. ma_go

[Tess]

Il 49 è messo lì per bellezza?

[xXStephXx]

Per ora so solo che la parte che sta a sinistra corrisponde alla somma delle potenze di 4 con esponente che va da 0 a n-1.

[Karl Zsigmondy]

Il 49 è messo lì per bellezza?

Poteva esserci anche 121.

[stergiosss]

Ecco, qui si che un hint mi farebbe comodo

[paga92aren]

Riscrivo il testo come $4^n-1|3((7m)^2+1)$ quindi $9\nmid 4^n-1$ da cui $3\nmid n$.
Prendo un primo $p\not=3$ tale che $p|4^n-1$ allora $(7m)^2\equiv -1\mod p$ quindi ord$_p(7m)=4|p-1$ da cui $p\equiv 1 \mod 4$.
Inoltre $2^{2n}-1=(2^n+1)(2^n-1)$ se $n$ dispari $3|2^n+1$ quindi $2^n-1$ ha fattori primi solo congrui a 1 modulo 4 quindi $2^n-1\equiv 1\mod 4$ quindi $n=1$.
Altrimenti $n=2n'$ e $2^{4n'}-1=(2^{2n'}+1)(2^{2n'}-1)$ e ripeto il ragionamento sul secondo fattore. Conclusione $n=2^k$.
Infine verifico che esiste $m$ per ogni $k$: per ogni $p|\frac{2^{2^k}-1}{3}$ vale che $p\equiv 1 (4)$ e basta verificare che -1 è un residuo modulo $p$ che è vero per la reciprocità quadratica (esiste l'inverso modulo $p$ per aggiustare il 7 e si conclude col teorema cinese del resto), quindi esiste $m$ opportuno.

[Karl Zsigmondy]

Perfetto! Un modo leggermente più veloce per escludere le non potenze di 2 era sfruttare il fatto che se d dispari divide n allora $ (4^d - 1) \mid (4^n-1) $, e da lì trattare WLOG il caso dispari come hai fatto tu. Anche se hai fatto a livello di idea la stessa cosa.