Re: Esponenziale Tosta
Inviato: 03 ott 2011, 17:40
Ammetto di non essere riuscito a seguirti 
OliForum Matematico
il forum ufficiale delle olimpiadi della matematica
https://www.oliforum.it/
Esponenziale Tosta
Pagina 4 di 4
Re: Esponenziale Tosta
Inviato: 03 ott 2011, 20:02
Mi ricorda vagamente un tizio su AoPS che risolveva più o meno tutte le diofantee così: "l'equazione non ha soluzioni modulo 1874923".
Re: Esponenziale Tosta
Inviato: 03 ott 2011, 21:51
Bon... ho deciso che la soluzione è giusta ripensandoci, se così non fosse e vabbè ho sprecato un po' a scriverla in bella:
$y^2+7=2^m$
Vale $y$ dispari quindi $y=2x+1$ e quindi è equivalente a $(2x+1)^2+7=2^m\to x^2+x+2=2^{m-2}$
Richiamo $n=m-2$ e ottengo da risolvere $x^2+x+2=2^n$ con $x,n$ negli interi non negativi ($x$ pure negli interi ma non cambia nulla).
Chiamo $\omega$ un numero complesso tale che $\omega^2+\omega+2=0$ e $\bar{\omega}$ ovviamente il suo coniugato.
È fatto più o meno noto che l'insieme $\mathbb{Z}[\omega]=\{a+b\omega:\ a,b\in\mathbb{Z}\}$ è un UFD cioè un elemento è primo se e solo se irriducibile e da questo si dimostra facilmente che vale la fattorizzazione unica e che ha senso parlare di fattore comune eccetera eccetera...
Inoltre vale $\omega\cdot \bar{\omega}=2$
E ancora di più vale che il quadrato della norma di un elemento in $\mathbb{Z}[\omega]$ è sempre intero! E gli unici elementi con norma 1 sono $1,-1$
La diofantea è banalmente equivalente a $(x-\omega)(x-\bar{\omega})=\omega^n\bar{\omega}^n$.
Vale che $\omega,\bar{\omega}$ sono primi perchè il quadrato della loro norma vale 2 che è primo quindi se si scomponessero avrei trovato 2 numeri interi diversi da 1 con prodotto 2, che è difficile.
Poi se $x-\omega,x-\bar{\omega}$ non fossero coprimi dovrei avere che un numero che li divide divide la differenza cioè $\omega-\bar{\omega}$ ma il prodotto di quei 2 hanno come fattori primi 2 primi solo, entrambi banalmente coprimi con $\omega-\bar{\omega}$ perciò anche $x-\omega,x-\bar{\omega}$ sono coprimi.
Ma allora ho il prodotto di 2 robe coprimi uguale al prodotto di 2 potenze di primo e perciò deve valere proprio l'uguaglianza tra fattori a meno di segno: le 2 robe stesse sono potenze di primo a meno di segno!
E questo è il passo fondamentale...
Deve valere $\omega^n=\pm(x-\omega)$ o $\omega^n=\pm(x-\bar\omega)=\pm(x+1+\omega)$
Chiamo $I(a+b\omega)=b$.
Allora deve valere o $I(\omega^n)=I(\pm(x-\omega))=\mp1$ o $I(\omega^n)=I(\pm(x+1+\omega))=\pm 1$ e quindi $I(\omega^n)=\pm 1$.
Definisco $I(\omega^n)=b_n$.
Vale facilmente $b_n=\frac{\omega^n-\bar{\omega}^n}{\omega-\bar{\omega}}$
E vale facilmente la ricorrenza $b_{n+2}=-b_{n+1}-2b_n$.
Sfruttando la ricorrenza analizzo modulo 4 ottengo: (0,1),-1,-1,-1,-1,-1,.... insomma tranne che per $b_1=1$ vale $b_n\not=1$ quindi cerco $b_n=-1$
Ora io voglio mostrare che modulo $2^{14}$ la sequenza dei $b_i$ ha antiperiodo $b_0,b_1,\dots b_{13}$ e poi parte il periodo!
Allora prendo un numero intero $\alpha$ tale che $2^{16}|\alpha^2+7$ e inoltre $\frac{-1+\alpha}{2}$ è dispari (questo esiste ma non mi va di dimostrarlo). Chiamo $\beta=\frac{-1+\alpha}{2}$ e $\bar{\beta}=\frac{-1-\alpha}{2}$.
Vorrei mostrare che $b_n\equiv \frac{\beta^n-\bar{\beta}^n}{\alpha}\pmod{2^{14}}$
E questo vale per induzione principalmente perchè per $b_0,b_1$ è vero e poi viene per induzione dato che $\beta.\bar{\beta}$ sono radici di $x^2+x+2$ modulo $2^{14}$
In particolare per la scelta di $\alpha$ vale $\upsilon_2(\bar{\beta})=1$ e perciò l'addendo $\bar{\beta}^n$ scompare per $n\ge 14$ e ottengo in questo caso: $b_n\equiv \alpha^{-1}\omega^n\pmod{2^{14}}$.
Quindi finche $\bar{\beta}^n$ vale qualcosa, cioè i primi 14 $b_i$ ho antiperiodo, poi parte un periodo lungo $Ord_{2^{14}}(\bar{\beta})$ che di certo divide $2^{12}$ (questo è vero per ogni numero... non mi va di dimostrarlo) (in particolare si dimostra che vale proprio l'uguaglianza anche senza usare un pc, ma vabbè non è strettamente necessario per la dimostrazione)
Arrivati qui ci armiamo di un computer e gli chiediamo di vedersi un po $b_i$ per $14\le i\le 13+2^{12}$ e viene che solo $b_{2061}\equiv -1\pmod{2^{14}}$.
Quindi ho dimostrato che se $b_n=-1$ e $n>13$ allora $n\equiv 2061\pmod{2^{12}}$.
Ora prendo il felice numero primo $p=10\cdot 2^{12}+1$ che il pc ci conferma che è primo.
Vale $p\equiv 4\pmod{7}$ e non credo serva dimostrazione.
Prima di tutto vale applicando la reciprocità quadratica: $\left(\frac{-7}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{7}{p}\right)=(-1)^{\frac{p-1}2}\cdot \left(\frac{7}{p}\right)\cdot (-1)^{\frac{(p-1)(7-1)}{4}}=\left(\frac{p}{7}\right)=\left(\frac{4}{7}\right)=1$
Quindi esiste $q$ intero tale che $p|q^2+7$ e che sia dispari. Chiamo $\gamma=\frac{-1+q}{2}$ e $\bar{\gamma}=\frac{-1-q}{2}$. E ora come prima per $2^{14}$ vale facilmente: $b_n\equiv \frac{\gamma^n-\bar{\gamma}^n}{\gamma-\bar{\gamma}}\pmod p$
Da quest'ultima formula risulta che il periodo di $b_i$ è un divisore di $p-1$ (che è chiaramente un multiplo dell'ordine sia di $\gamma$ che di $\bar{\gamma}$) e che la sequenza non ha antiperiodo dato che sia $\gamma$ che $\bar{\gamma}$ sono invertibili $\pmod{p}$.
Quindi ora si passa ad usare un pc e si analizzano $b_0,b_1,\dots b_{p-2}$ modulo $p$ e si ottiene che $b_i\equiv -1\pmod{p} \iff i\equiv 2,3,5,13,20481\pmod{p-1}$.
Vale anche $2^{12}|p-1$ quindi queste congruenze le posso rivedere modulo $4096$ ottenendo che se $b_n=-1$ allora $b_i\equiv 2,3,5,13,1\pmod{4096}$ che però dà assurdo per $n\ge 14$ dato che avevo dimostrato che $b_n=-1\to n\equiv 2061\pmod{4096}$.
Perciò $b_n=-1$ implica $n\le 13$ e questi casi si fanno facilmente a mano ottenendo $n=2,3,5,13$ che unito a $b_1=1$ dà come possibili $n$ soluzioni dell'equazione $x^2+x+2=2^n$ solo $1,2,3,5,13$ che si verifica facilmente essere davvero soluzioni
$y^2+7=2^m$
Vale $y$ dispari quindi $y=2x+1$ e quindi è equivalente a $(2x+1)^2+7=2^m\to x^2+x+2=2^{m-2}$
Richiamo $n=m-2$ e ottengo da risolvere $x^2+x+2=2^n$ con $x,n$ negli interi non negativi ($x$ pure negli interi ma non cambia nulla).
Chiamo $\omega$ un numero complesso tale che $\omega^2+\omega+2=0$ e $\bar{\omega}$ ovviamente il suo coniugato.
È fatto più o meno noto che l'insieme $\mathbb{Z}[\omega]=\{a+b\omega:\ a,b\in\mathbb{Z}\}$ è un UFD cioè un elemento è primo se e solo se irriducibile e da questo si dimostra facilmente che vale la fattorizzazione unica e che ha senso parlare di fattore comune eccetera eccetera...
Inoltre vale $\omega\cdot \bar{\omega}=2$
E ancora di più vale che il quadrato della norma di un elemento in $\mathbb{Z}[\omega]$ è sempre intero! E gli unici elementi con norma 1 sono $1,-1$
La diofantea è banalmente equivalente a $(x-\omega)(x-\bar{\omega})=\omega^n\bar{\omega}^n$.
Vale che $\omega,\bar{\omega}$ sono primi perchè il quadrato della loro norma vale 2 che è primo quindi se si scomponessero avrei trovato 2 numeri interi diversi da 1 con prodotto 2, che è difficile.
Poi se $x-\omega,x-\bar{\omega}$ non fossero coprimi dovrei avere che un numero che li divide divide la differenza cioè $\omega-\bar{\omega}$ ma il prodotto di quei 2 hanno come fattori primi 2 primi solo, entrambi banalmente coprimi con $\omega-\bar{\omega}$ perciò anche $x-\omega,x-\bar{\omega}$ sono coprimi.
Ma allora ho il prodotto di 2 robe coprimi uguale al prodotto di 2 potenze di primo e perciò deve valere proprio l'uguaglianza tra fattori a meno di segno: le 2 robe stesse sono potenze di primo a meno di segno!
E questo è il passo fondamentale...
Deve valere $\omega^n=\pm(x-\omega)$ o $\omega^n=\pm(x-\bar\omega)=\pm(x+1+\omega)$
Chiamo $I(a+b\omega)=b$.
Allora deve valere o $I(\omega^n)=I(\pm(x-\omega))=\mp1$ o $I(\omega^n)=I(\pm(x+1+\omega))=\pm 1$ e quindi $I(\omega^n)=\pm 1$.
Definisco $I(\omega^n)=b_n$.
Vale facilmente $b_n=\frac{\omega^n-\bar{\omega}^n}{\omega-\bar{\omega}}$
E vale facilmente la ricorrenza $b_{n+2}=-b_{n+1}-2b_n$.
Sfruttando la ricorrenza analizzo modulo 4 ottengo: (0,1),-1,-1,-1,-1,-1,.... insomma tranne che per $b_1=1$ vale $b_n\not=1$ quindi cerco $b_n=-1$
Ora io voglio mostrare che modulo $2^{14}$ la sequenza dei $b_i$ ha antiperiodo $b_0,b_1,\dots b_{13}$ e poi parte il periodo!
Allora prendo un numero intero $\alpha$ tale che $2^{16}|\alpha^2+7$ e inoltre $\frac{-1+\alpha}{2}$ è dispari (questo esiste ma non mi va di dimostrarlo). Chiamo $\beta=\frac{-1+\alpha}{2}$ e $\bar{\beta}=\frac{-1-\alpha}{2}$.
Vorrei mostrare che $b_n\equiv \frac{\beta^n-\bar{\beta}^n}{\alpha}\pmod{2^{14}}$
E questo vale per induzione principalmente perchè per $b_0,b_1$ è vero e poi viene per induzione dato che $\beta.\bar{\beta}$ sono radici di $x^2+x+2$ modulo $2^{14}$
In particolare per la scelta di $\alpha$ vale $\upsilon_2(\bar{\beta})=1$ e perciò l'addendo $\bar{\beta}^n$ scompare per $n\ge 14$ e ottengo in questo caso: $b_n\equiv \alpha^{-1}\omega^n\pmod{2^{14}}$.
Quindi finche $\bar{\beta}^n$ vale qualcosa, cioè i primi 14 $b_i$ ho antiperiodo, poi parte un periodo lungo $Ord_{2^{14}}(\bar{\beta})$ che di certo divide $2^{12}$ (questo è vero per ogni numero... non mi va di dimostrarlo) (in particolare si dimostra che vale proprio l'uguaglianza anche senza usare un pc, ma vabbè non è strettamente necessario per la dimostrazione)
Arrivati qui ci armiamo di un computer e gli chiediamo di vedersi un po $b_i$ per $14\le i\le 13+2^{12}$ e viene che solo $b_{2061}\equiv -1\pmod{2^{14}}$.
Quindi ho dimostrato che se $b_n=-1$ e $n>13$ allora $n\equiv 2061\pmod{2^{12}}$.
Ora prendo il felice numero primo $p=10\cdot 2^{12}+1$ che il pc ci conferma che è primo.
Vale $p\equiv 4\pmod{7}$ e non credo serva dimostrazione.
Prima di tutto vale applicando la reciprocità quadratica: $\left(\frac{-7}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{7}{p}\right)=(-1)^{\frac{p-1}2}\cdot \left(\frac{7}{p}\right)\cdot (-1)^{\frac{(p-1)(7-1)}{4}}=\left(\frac{p}{7}\right)=\left(\frac{4}{7}\right)=1$
Quindi esiste $q$ intero tale che $p|q^2+7$ e che sia dispari. Chiamo $\gamma=\frac{-1+q}{2}$ e $\bar{\gamma}=\frac{-1-q}{2}$. E ora come prima per $2^{14}$ vale facilmente: $b_n\equiv \frac{\gamma^n-\bar{\gamma}^n}{\gamma-\bar{\gamma}}\pmod p$
Da quest'ultima formula risulta che il periodo di $b_i$ è un divisore di $p-1$ (che è chiaramente un multiplo dell'ordine sia di $\gamma$ che di $\bar{\gamma}$) e che la sequenza non ha antiperiodo dato che sia $\gamma$ che $\bar{\gamma}$ sono invertibili $\pmod{p}$.
Quindi ora si passa ad usare un pc e si analizzano $b_0,b_1,\dots b_{p-2}$ modulo $p$ e si ottiene che $b_i\equiv -1\pmod{p} \iff i\equiv 2,3,5,13,20481\pmod{p-1}$.
Vale anche $2^{12}|p-1$ quindi queste congruenze le posso rivedere modulo $4096$ ottenendo che se $b_n=-1$ allora $b_i\equiv 2,3,5,13,1\pmod{4096}$ che però dà assurdo per $n\ge 14$ dato che avevo dimostrato che $b_n=-1\to n\equiv 2061\pmod{4096}$.
Perciò $b_n=-1$ implica $n\le 13$ e questi casi si fanno facilmente a mano ottenendo $n=2,3,5,13$ che unito a $b_1=1$ dà come possibili $n$ soluzioni dell'equazione $x^2+x+2=2^n$ solo $1,2,3,5,13$ che si verifica facilmente essere davvero soluzioni
Re: Esponenziale Tosta
Inviato: 05 ott 2011, 16:42
Ho la sensazione che mi sia richiesto un commento…
La soluzione che avevo in mente è un po' faticosa ma non richiede il computer; piuttosto che ricopiarvela vi do direttamente il link. Non è quella originale, ma una semplificata che lavora prevalentemente in $\mathbb{Z}$.
http://www.jstor.org/stable/2323504
La soluzione che avevo in mente è un po' faticosa ma non richiede il computer; piuttosto che ricopiarvela vi do direttamente il link. Non è quella originale, ma una semplificata che lavora prevalentemente in $\mathbb{Z}$.
http://www.jstor.org/stable/2323504
Re: Esponenziale Tosta
Inviato: 05 ott 2011, 16:47
La sensazione era giusta
Comunque il link che hai piazzato chiede 12 dollari per vedere la soluzione...
Comunque puoi darmi conferma che non ho preso strafalcioni?
Comunque il link che hai piazzato chiede 12 dollari per vedere la soluzione...
Comunque puoi darmi conferma che non ho preso strafalcioni?
Re: Esponenziale Tosta
Inviato: 07 ott 2011, 14:58
La tua dimostrazione mi sembra giusta, a meno dei conti al computer che non ho verificato.
Maledetto JSTOR
Do uno sketch di quella che avevo in mente; si articolava così (tenendo la tua notazione)
Seguendo il suggerimento che avevo dato, si ricava la formula
$$b_{n k+1}=b_{n+1}^k-2b_n^2\sum_{j=2}^k (-1)^j\binom{k}{j}b_{n+1}^{k-j}b_n^{j-2}b_{j-1}\qquad k\geq 2.$$
Modulo 16 si vede che $b_n=1$ se e solo se $n=1$, e se $b_n=-1$ allora $n=2,3$ o $n\equiv 1\pmod 4$.
Adesso vedo che $b_5=-1$ (altra soluzione), metto $k=4$ nella formula ed assumo $b_{4k+1}=-1$ ottenendo
$$-1=b_{4k+1}=(-1)^k-(-1)^k 18\sum_{j=2}^k\binom{k}{j}3^{j-2}b_{j-1},$$
da cui segue modulo 3 che k è dispari, e $\sum_{j=2}^k\binom{k}{j}3^{j-2}b_{j-1}=0$.
Adesso provo a mano $k=3$ e trovo l'ultima soluzione, assumo $k\geq 5$, tiro fuori i primi due termini dalla sommatoria, divido per $k(k-1)$, armeggio sul coefficiente binomiale ed ho
$$\frac{1}{2}-\frac{k-2}{2}=-\sum_{j=4}^k\binom{k-2}{j-2}\frac{3^{j-2}}{j(j-1)}b_{j-1},$$
da cui, confrontando la valutazione 3-adica, ho che $3\mid k$.
Quindi torno al primo formulone e adesso lo uso con $n=12$.
$$b_{12 k+1}=b_{13}^k-2b_{12}^2\sum_{j=2}^k (-1)^j\binom{k}{j}b_{13}^{k-j}b_{12}^{j-2}b_{j-1}\qquad k\geq 2.$$
$b_{12}=-45,b_{13}=-1$; se assumo che $b_{12k+1}=-1$ ho che
$$-1=b_{12k+1}=(-1)^k-(-1)^k 2b_{12}^2\sum_{j=2}^k(-1)^j \binom{k}{j}45^{j-2}b_{j-1},$$
e quindi
$$\sum_{j=2}^k(-1)^j \binom{k}{j}45^{j-2}b_{j-1}=0.$$
$k$ doveva essere dispari (ok, $3k$ doveva essere dispari…) e quindi $k\geq 3$, quindi come prima tiriamo suori un addendo dalla somma, dividiamo per $k(k-1)$, rimestiamo il binomiale ed abbiamo
$$\frac{1}{2}=-\sum_{j=3}^k\binom{k-2}{j-2}\frac{45^{j-2}}{j(j-1)}b_{j-1}$$
che è un assurdo confrontando le valutazioni 5-adiche.
E questo conclude.
Folklore: usando la fattorizzazione in ideali, questo approccio funziona anche quando gli interi del campo non hanno fattorizzazione unica, e risolve, per esempio, $x^2+4p-1=4p^n$ con x intero e p primo.
Maledetto JSTOR
Do uno sketch di quella che avevo in mente; si articolava così (tenendo la tua notazione)
Seguendo il suggerimento che avevo dato, si ricava la formula
$$b_{n k+1}=b_{n+1}^k-2b_n^2\sum_{j=2}^k (-1)^j\binom{k}{j}b_{n+1}^{k-j}b_n^{j-2}b_{j-1}\qquad k\geq 2.$$
Modulo 16 si vede che $b_n=1$ se e solo se $n=1$, e se $b_n=-1$ allora $n=2,3$ o $n\equiv 1\pmod 4$.
Adesso vedo che $b_5=-1$ (altra soluzione), metto $k=4$ nella formula ed assumo $b_{4k+1}=-1$ ottenendo
$$-1=b_{4k+1}=(-1)^k-(-1)^k 18\sum_{j=2}^k\binom{k}{j}3^{j-2}b_{j-1},$$
da cui segue modulo 3 che k è dispari, e $\sum_{j=2}^k\binom{k}{j}3^{j-2}b_{j-1}=0$.
Adesso provo a mano $k=3$ e trovo l'ultima soluzione, assumo $k\geq 5$, tiro fuori i primi due termini dalla sommatoria, divido per $k(k-1)$, armeggio sul coefficiente binomiale ed ho
$$\frac{1}{2}-\frac{k-2}{2}=-\sum_{j=4}^k\binom{k-2}{j-2}\frac{3^{j-2}}{j(j-1)}b_{j-1},$$
da cui, confrontando la valutazione 3-adica, ho che $3\mid k$.
Quindi torno al primo formulone e adesso lo uso con $n=12$.
$$b_{12 k+1}=b_{13}^k-2b_{12}^2\sum_{j=2}^k (-1)^j\binom{k}{j}b_{13}^{k-j}b_{12}^{j-2}b_{j-1}\qquad k\geq 2.$$
$b_{12}=-45,b_{13}=-1$; se assumo che $b_{12k+1}=-1$ ho che
$$-1=b_{12k+1}=(-1)^k-(-1)^k 2b_{12}^2\sum_{j=2}^k(-1)^j \binom{k}{j}45^{j-2}b_{j-1},$$
e quindi
$$\sum_{j=2}^k(-1)^j \binom{k}{j}45^{j-2}b_{j-1}=0.$$
$k$ doveva essere dispari (ok, $3k$ doveva essere dispari…) e quindi $k\geq 3$, quindi come prima tiriamo suori un addendo dalla somma, dividiamo per $k(k-1)$, rimestiamo il binomiale ed abbiamo
$$\frac{1}{2}=-\sum_{j=3}^k\binom{k-2}{j-2}\frac{45^{j-2}}{j(j-1)}b_{j-1}$$
che è un assurdo confrontando le valutazioni 5-adiche.
E questo conclude.
Folklore: usando la fattorizzazione in ideali, questo approccio funziona anche quando gli interi del campo non hanno fattorizzazione unica, e risolve, per esempio, $x^2+4p-1=4p^n$ con x intero e p primo.