2^a-1 | b^2 + 9 ?
Un bel problema che ho pescato e risolto in un altro forum...
Determinare tutti gli interi positivi $a$ tali che esista un intero positivo $b$ tale che $2^a-1|b^2+9$
EDIT: per i meno esperti $x|y$ significa $x$ divide $y$
Ciao Ciao
Determinare tutti gli interi positivi $a$ tali che esista un intero positivo $b$ tale che $2^a-1|b^2+9$
EDIT: per i meno esperti $x|y$ significa $x$ divide $y$
Ciao Ciao
Risposte
Quoto visto che sta sprofondando irrisolto, forza Thomas, giuseppex87 ecc. ! 
Lemma: Sia $p>3$ primo. Se $p$ divide $b^2+9$ per qualche $b\in NN$, allora $p\equiv 1 (\mod 4)$
Dim: Poichè $p>3$ è $(3,p)=1$ quindi esiste $c\in NN$ tale che $3c\equiv 1 (\mod p)$. Allora $(bc)^2\equiv -1(\mod p)$ quindi $bc$ ha ordine $4$ modulo $p$. Per il Teorema di Eulero-Fermat, $4|p-1$.
Sia $a=2^\alpha beta$ con $alpha>=0$, $beta>=1$ e $beta$ dispari.
Supponiamo $beta>1$. Si ha $2^beta -1|2^a-1$. Poichè $beta$ è dispari $3$ non divide $2^beta -1$ (infatti $2^beta -1\equiv 1(\mod3)$). Ma $2^beta -1 \equiv -1(\mod 4)$ quindi esiste un primo $p>3$ con $p\equiv -1 (mod 4)$ divisore di $2^beta -1$. Per il lemma $p$ non può dividere $b^2+9$ per alcun $b$, quindi non si hanno soluzioni.
Sia allora $beta=1$ i.e $a=2^alpha$. Proviamo per induzione su $alpha$ che esiste $b$ tale che $2^a-1|b^2+9$.
Per $alpha=0$ è $2^a-1=1$ quindi $b=1$ soddisfa la tesi.
Supponiamo vera la tesi per $alpha-1$ e proviamola per $alpha$.
E' $2^(2^alpha)-1=(2^(2^(alpha-1))-1)(2^(2^(alpha-1))+1)$.
Poniamo per comodità: $n=2^(2^(alpha-1))-1$ e $m=2^(2^(alpha-1))+1$.
Osserviamo che $n$ e $m$ sono coprimi.
Per ipotesi d'induzione esiste $u$ tale che $2^(2^(alpha-1))-1|u^2+9$ i.e $u^2+9\equiv 0 (\mod n)$.
Posto $v=3*2^(2^(alpha-2))$ allora $v^2+9\equiv 0 (\mod m)$.
Per il teorema cinese dei resti esiste $b$ tale che:
$b\equiv u (\mod n)$
$b\equiv v (\mod m)$
Allora $2^(2^alpha)-1|b^2+9$.
Dim: Poichè $p>3$ è $(3,p)=1$ quindi esiste $c\in NN$ tale che $3c\equiv 1 (\mod p)$. Allora $(bc)^2\equiv -1(\mod p)$ quindi $bc$ ha ordine $4$ modulo $p$. Per il Teorema di Eulero-Fermat, $4|p-1$.
Sia $a=2^\alpha beta$ con $alpha>=0$, $beta>=1$ e $beta$ dispari.
Supponiamo $beta>1$. Si ha $2^beta -1|2^a-1$. Poichè $beta$ è dispari $3$ non divide $2^beta -1$ (infatti $2^beta -1\equiv 1(\mod3)$). Ma $2^beta -1 \equiv -1(\mod 4)$ quindi esiste un primo $p>3$ con $p\equiv -1 (mod 4)$ divisore di $2^beta -1$. Per il lemma $p$ non può dividere $b^2+9$ per alcun $b$, quindi non si hanno soluzioni.
Sia allora $beta=1$ i.e $a=2^alpha$. Proviamo per induzione su $alpha$ che esiste $b$ tale che $2^a-1|b^2+9$.
Per $alpha=0$ è $2^a-1=1$ quindi $b=1$ soddisfa la tesi.
Supponiamo vera la tesi per $alpha-1$ e proviamola per $alpha$.
E' $2^(2^alpha)-1=(2^(2^(alpha-1))-1)(2^(2^(alpha-1))+1)$.
Poniamo per comodità: $n=2^(2^(alpha-1))-1$ e $m=2^(2^(alpha-1))+1$.
Osserviamo che $n$ e $m$ sono coprimi.
Per ipotesi d'induzione esiste $u$ tale che $2^(2^(alpha-1))-1|u^2+9$ i.e $u^2+9\equiv 0 (\mod n)$.
Posto $v=3*2^(2^(alpha-2))$ allora $v^2+9\equiv 0 (\mod m)$.
Per il teorema cinese dei resti esiste $b$ tale che:
$b\equiv u (\mod n)$
$b\equiv v (\mod m)$
Allora $2^(2^alpha)-1|b^2+9$.
"ficus2002":
Lemma: Sia $p>3$ primo. Se $p$ divide $b^2+9$ per qualche $b\in NN$, allora $p\equiv 1 (\mod 4)$...
Bravo, tutto corretto!
La chiave stava proprio nel lemma che citi all'inizio
"carlo23":
Bravo, tutto corretto!
La chiave stava proprio nel lemma che citi all'inizio
Grazie
Volevo chiederti, la tua soluzione è più meno come la mia o hai trovato qualche scorciatoia?
"ficus2002":
[quote="carlo23"]
Bravo, tutto corretto!
La chiave stava proprio nel lemma che citi all'inizio
Grazie
Volevo chiederti, la tua soluzione è più meno come la mia o hai trovato qualche scorciatoia?[/quote]
L'idea è esattamente la stessa, nella seconda parte non ho usato il teorema cinesi dei resti ma un lemma più generale riguardo le soluzioni di $f(x)-=0 mod n$ con $f(x)$ determinato polinomio...in realtà se il fine è solo la soluzione di questo problema allora il teorema cinese dei resti abbrevia la dimostrazione
"carlo23":
Quoto visto che sta sprofondando irrisolto, forza Thomas, giuseppex87 ecc. !
eheh... mica sono sempre in vacanza come un bravo liceale... la pausa estiva è finita!
... o quasi... e poi... ti avevo già dimostrato un lemma che mi incuriosiva
... certo potevo provare a completare od a rifare in modo diverso, ma se scrivo una soluzione in genere mi piace che sia originale
"Thomas":
e poi... ti avevo già dimostrato un lemma che mi incuriosiva
Nessuno ti obbliga a niente... scusa ma quale lemma? non ricordo
eheh... non importa... lascia perdere! 
ciao
ps: se qualcuno si sente offeso, vuol dire che ha frainteso, ok?
ciao
ps: se qualcuno si sente offeso, vuol dire che ha frainteso, ok?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo