Trovare tutti gli interi positivi $n$ tali che $2^n-1 \mid m^2+9$ per qualche intero $m$
(TST Italiano 2006)
$2^n-1 \mid m^2+9$
$2^n-1 \mid m^2+9$
The only goal of science is the honor of the human spirit.
-
Ido Bovski
- Messaggi: 232
- Iscritto il: 07 mag 2012, 11:51
Re: $2^n-1 \mid m^2+9$
Ma siamo sicuri che sia un problema del TST del 2006? Ho controllato e non mi pare. Comunque, affinché questo mio messaggio non sia inutile metto un hint e dico anche che è un bel problema 
Hint:
Hint:
Testo nascosto:
Re: $2^n-1 \mid m^2+9$
Che sia del 2006 non ci metto la mano sul fuoco, che sia un tst italiano e parecchio conosciuto, e per di piu' già passato su questo forum, quasi quasiIdo Bovski ha scritto:Ma siamo sicuri che sia un problema del TST del 2006?
Ps. Mi sa che ti conviene metterla la soluzione, di certo non fai danno a nessuno
The only goal of science is the honor of the human spirit.
-
Ido Bovski
- Messaggi: 232
- Iscritto il: 07 mag 2012, 11:51
Re: $2^n-1 \mid m^2+9$
Non avevo scritto la soluzione perché il problema già lo conoscevo e volevo lasciarlo a qualcun'altro. Va bien...
Dim. Supponiamo $\gcd(a, p)=1$, allora $(ab^{-1})^2\equiv -1 \pmod p$, ma $p\equiv 3 \pmod 4$ e quindi $\displaystyle \left(\frac{-1}{p}\right)=-1$, assurdo. Pertanto $p\mid a$ e di conseguenza $p\mid b$.
Dimostreremo che esiste $m$ intero tale che $2^n-1 \mid m^2+9$ se e solo se $n$ è una potenza di $2$.
$\bullet$ Se $n$ non è una potenza di $2$ allora esiste $d$ dispari tale che $d\mid n$. Poiché $2^d-1\equiv 3 \pmod 4$, v'è un primo $p\equiv 3 \pmod 4$ tale che $p\mid 2^d-1\mid (2^d)^{n/d}-1^{n/d}\mid m^2+3^2$. Per il lemma dimostrato $p\mid 3$, ovvero $p=3$, ma $2^d-1\equiv 1 \not\equiv 0 \pmod 3$, assurdo.
$\bullet$ Sia $n=2^k$. Dimostriamo che esiste $m$ intero tale che $2^{2^k}-1 \mid m^2+9$ per induzione su $k$. Per il basso base, ovvero $k=1$, basta scegliere $m\equiv 0 \pmod 3$. Per il passo induttivo osserviamo che $2^{2^k}-1=(2^{2^{k-1}}-1)(2^{2^{k-1}}+1)$. Per ipotesi induttiva allora esiste $u$ intero tale che $2^{2^{k-1}}-1\mid u^2+9$. Scegliendo invece $v=3\cdot 2^{2^{k-2}}$, abbiamo che $2^{2^{k-1}}+1\mid v^2+9$. Concludiamo dunque che per il CRT esiste $m$ tale che $m\equiv u \pmod {2^{2^{k-1}}-1}$ e $m\equiv v \pmod {2^{2^{k-1}}+1}$, poiché $\gcd(2^{2^{k-1}}-1, 2^{2^{k-1}}+1)=1$.
Lemma. Siano $a, b>1$ due interi e sia $p\equiv 3 \pmod 4$ un numero primo. Se $p\mid a^2+b^2$, allora $p\mid a$ e $p\mid b$.Trovare tutti gli interi positivi $n$ tali che $2^n-1 \mid m^2+9$ per qualche intero $m$
Dim. Supponiamo $\gcd(a, p)=1$, allora $(ab^{-1})^2\equiv -1 \pmod p$, ma $p\equiv 3 \pmod 4$ e quindi $\displaystyle \left(\frac{-1}{p}\right)=-1$, assurdo. Pertanto $p\mid a$ e di conseguenza $p\mid b$.
Dimostreremo che esiste $m$ intero tale che $2^n-1 \mid m^2+9$ se e solo se $n$ è una potenza di $2$.
$\bullet$ Se $n$ non è una potenza di $2$ allora esiste $d$ dispari tale che $d\mid n$. Poiché $2^d-1\equiv 3 \pmod 4$, v'è un primo $p\equiv 3 \pmod 4$ tale che $p\mid 2^d-1\mid (2^d)^{n/d}-1^{n/d}\mid m^2+3^2$. Per il lemma dimostrato $p\mid 3$, ovvero $p=3$, ma $2^d-1\equiv 1 \not\equiv 0 \pmod 3$, assurdo.
$\bullet$ Sia $n=2^k$. Dimostriamo che esiste $m$ intero tale che $2^{2^k}-1 \mid m^2+9$ per induzione su $k$. Per il basso base, ovvero $k=1$, basta scegliere $m\equiv 0 \pmod 3$. Per il passo induttivo osserviamo che $2^{2^k}-1=(2^{2^{k-1}}-1)(2^{2^{k-1}}+1)$. Per ipotesi induttiva allora esiste $u$ intero tale che $2^{2^{k-1}}-1\mid u^2+9$. Scegliendo invece $v=3\cdot 2^{2^{k-2}}$, abbiamo che $2^{2^{k-1}}+1\mid v^2+9$. Concludiamo dunque che per il CRT esiste $m$ tale che $m\equiv u \pmod {2^{2^{k-1}}-1}$ e $m\equiv v \pmod {2^{2^{k-1}}+1}$, poiché $\gcd(2^{2^{k-1}}-1, 2^{2^{k-1}}+1)=1$.
Re: $2^n-1 \mid m^2+9$
Ho letto oggi per caso dal PEN che una fonte è anche IMO shortlist 98'
The only goal of science is the honor of the human spirit.