195. Divisibilità

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
cip999
Messaggi: 148
Iscritto il: 26 nov 2013, 14:44

195. Divisibilità

Messaggio da cip999 » 21 gen 2016, 21:12

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$$
- E cosa c'è di peggio del suicidio?
- La vita.

bern-1-16-4-13
Messaggi: 72
Iscritto il: 23 mag 2015, 18:27

Re: 195. Divisibilità

Messaggio da bern-1-16-4-13 » 22 gen 2016, 15:25

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
Messaggi: 148
Iscritto il: 26 nov 2013, 14:44

Re: 195. Divisibilità

Messaggio da cip999 » 22 gen 2016, 16:50

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à).
- E cosa c'è di peggio del suicidio?
- La vita.

bern-1-16-4-13
Messaggi: 72
Iscritto il: 23 mag 2015, 18:27

Re: 195. Divisibilità

Messaggio da bern-1-16-4-13 » 22 gen 2016, 17:17

cip999 ha scritto: 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?! :x
Ahahahah, nemmeno avessi utilizzato bombe atomiche tipo la congettura di Bunyakovsky :lol:

cip999
Messaggi: 148
Iscritto il: 26 nov 2013, 14:44

Re: 195. Divisibilità

Messaggio da cip999 » 22 gen 2016, 17:38

Oppure sei una brava ragazza, come preferisci... :D
Vabbè dai, basta OT sennò ci bannano e non ti mandano alle IMO.
- E cosa c'è di peggio del suicidio?
- La vita.

Rispondi