OliForum Matematico

FATTO1:
diciamo che $4^n-1=3k$ (ovviamente $k\in\mathbb{N}$). Allora $$\exists\ \ \ \ \mathbb{P}\ni p\equiv 3\pmod{4}:\ \ p\mid k\Longleftrightarrow\nexists \ \ \ \ j\in\mathbb{N}:\ \ n=2^j.$$
Dimostrazione freccia "$\Longleftarrow$":
se $n$ non è potenza di $2$ allora $n=2^{v_2\left(n\right)}d$ dove $d>1$.
Allora possiamo dire che $$4^n-1=3k=3\left(2^d-1\right)\prod_{i=0}^{v_2\left(n\right)}\left(2^{2^id}+1\right).$$A questo punto il fatto che $d>1$ e che $d$ sia dispari ci dicono che $2^d-1\equiv 3\pmod{4}$ e che $3\not\mid 2^d-1$ e questo ci assicura l'esistenza di un primo congruo $3\pmod 4$ che divida $k$.
Dimostrazione freccia "$\Longleftarrow$":
supponiamo per assurdo che $n=2^j$ ma che tuttavia esista un primo $p\equiv 3\pmod{4}$ che divide $k$.
Allora $ord_p\left(4\right)\mid 2^j$. Ma sappiamo anche che $ord_p\left(4\right)\mid p-1$. Poiché tuttavia $v_2\left(p-1\right)=1$ (per come abbiamo definito $p$), concludiamo che $ord_p\left(4\right)\leq 2$.
Quindi si vede facilmente che i valori che può assumere $p$ sono solo $3$ e $5$. D'altronde $5$ lo escludiamo essendo congruo $1\pmod{4}$.
Nel caso in cui $p=3$ invece si avrebbe che $9\mid 4^n-1$ il che comporterebbe che $ord_9\left(4\right)\mid n$ quindi che $3\mid 2^j$ che è chiaramente assurdo.


FATTO2:
$$\forall m\in\mathbb{Z}^+\ \ \ \ \nexists\ \ \ \ \mathbb{P}\ni p\equiv 3\pmod4:\ \ \ \ p\mid 49m^2+1.$$
Infatti si dovrebbe avere che $49m^2\equiv -1\pmod{p}$.
Tuttavia $\left(\frac{-1}{q}\right)=-1$ essendo $q$ congruo $3\pmod4$, e questo non è possibile perché $49m^2$ è un quadrato perfetto.


FATTO3:
se nella scomposizione di un numero $a$ i fattori primi sono tutti congrui $1\pmod{4}$ allora $$\exists\ \ \ \ m:\ \ \ a\mid 49m^2+1.$$
Se dimostriamo che il caso $a=q^r$ dove $q$ è un primo ha soluzione per ogni $m\equiv s\pmod{q^r}$ (per un certo valore di $s$), allora abbiamo concluso poichè il teorema cinese del resto ci permetterà di estendere la soluzione a un qualsiasi $a$ della forma definita all'inizio del FATTO3.
Ebbene, sia $g$ un generatore modulo $q^r$ (esiste).
Allora $$g^{\frac{\left(q-1\right)q^{r-1}}{2}}\equiv -1\pmod{q^r}.$$
Inoltre per un certo valore $t\leq q^r$ si ha che $g^t\equiv 7\pmod{q^r}$.
Adesso poniamo $$m=g^{\left(q-1\right)q^{r-1}+\frac{\left(q-1\right)q^{r-1}}{4}-t}$$(l'esponente è senz'altro positivo, e intero poichè $q\equiv 1\pmod{4}$).
Andando a sostituire in $$9m^2+1\equiv 0\pmod{q^r}$$ si ottiene che $$g^{2t}\cdot g^{2\left(q-1\right)q^{r-1}+\frac{\left(q-1\right)q^{r-1}}{2}-2t}\equiv 0\pmod{q^r}.$$Quindi $$g^{2\left(q-1\right)q^{r-1}+\frac{\left(q-1\right)q^{r-1}}{2}}\equiv -1\pmod{q^r},$$
Quindi $$g^{\frac{\left(q-1\right)q^{r-1}}{2}}\equiv -1\pmod{q^r},$$il che è vero per quanto detto prima.

I tre FATTI uniti danno luogo alla soluzione del problema. Il bonus fa uso solo del FATTO2 e del FATTO3.