195. Divisibilità

[cip999]

Determinare tutti gli interi positivi $n$ per cui esiste un intero positivo $m$ tale che $$\frac{4^n - 1}{3} \quad \text{divide} \quad 49m^2 + 1$$

Bonus. (Non vale per la staffetta) Determinare tutti gli interi positivi $n$ per cui esiste un intero positivo $m$ tale che $$n \quad \text{divide} \quad 49m^2 + 1$$

[bern-1-16-4-13]

Testo nascosto:

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.

[cip999]

Direi che va bene (a parte il fatto che nel bonus ti sei dimenticato i fattori $2$, ma è stupido).

In alternativa, nel problema originale una volta appurato che $n = 2^k$ si può concludere subito andando di induzione su $k$, sfruttando il fatto che l'esistenza di $m$ gode in un certo senso di moltiplicatività (si mostra con il teorema cinese o anche costruendo il nuovo $m$ a mano).
Invece, per i bravi ragazzi che non usano cose illegali come i generatori modulo $p^k$, il FATTO3 viene anche (con un po' più fatica) mostrando, induttivamente, che esistono $a$ e $b$ primi con $p$ tali che $a^2 + b^2 = p^k$, e poi trasformando $b$ in $1$ e $a$ in un multiplo di $7$ con un po' di manipolazioni (e facendo diventare l'uguaglianza una divisibilità).

[bern-1-16-4-13]

Invece, per i bravi ragazzi che non usano cose illegali come i generatori modulo $p^k$

Quindi io sarei un ragazzo cattivo e tu uno bravo?!
Ahahahah, nemmeno avessi utilizzato bombe atomiche tipo la congettura di Bunyakovsky

[cip999]

Oppure sei una brava ragazza, come preferisci...
Vabbè dai, basta OT sennò ci bannano e non ti mandano alle IMO.