Volevo mettere integer party hard viewtopic.php?f=15&t=18649 nella staffetta, però quello in realtà è anche un po' algebra e poi è abbastanza tosto/non standard/truccoso, dato che ho già messo troppi problemi truccosi nella staffetta, però è figo, quindi plis guardatelo. Grazie.
Siano $a_0=0;a_1=1;a_{n+2}=a_{n+1}+a_n$.
Dimostrare (immagino che non vi ricordi niente quello che sto per scrivere) che per ogni primo $p>5$ tale che $p|a_n$, vale:
\begin{equation}
v_p(a_{nk})=v_p(k)+v_p(a_n)
\end{equation}
174. Fibonacci cannonoso
-
Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
Re: 174. Fibonacci cannonoso
Bello, un altro problema sulle estensioni quadratiche! 
Già che ci sono quindi provo a generalizzarlo a tutte le sequenze di Lucas...
Siano $S,P$ due interi coprimi e $D=S^2-4P$;
sia $a_0=0,a_1=1,a_{n+1}=Sa_n-Pa_{n-1}$ una successione (di interi ovviamente);
siano poi $\alpha,\beta$ le due radici di $x^2-Sx+P$, ovvero $\alpha=\dfrac{S+\sqrt D}2, \;\beta=\dfrac{S-\sqrt D}2$.
(Nota: i Fibonacci corrispondono a $S=1,P=-1,\alpha=\varphi,\beta=1-\varphi$)
Lemma noto $$a_n=\dfrac{\alpha^n-\beta^n}{\alpha-\beta}$$
Bene, questo fatto ci fa chiaramente vedere la correlazione della sequenza con degli esponenti; inoltre ciò che dobbiamo dimostrare è molto simile a LTE, quindi... ricicliamo la dimostrazione di LTE!
Ovvero:
- se $p\nmid k$ e $p\mid a_n$ allora $v_p(a_{nk})=v_p(a_n)$
- $v_p(a_{np})=v_p(a_n)+1$ nei due step (divide e divide esattamente)
- induzione banale per concludere
Per sicurezza escludiamo dalla dimostrazione il $2$ e i primi che dividono $S,D$ o $P$. (nel caso dei Fibonacci solo il $5$)
Step 1. $\displaystyle p\nmid k,\;p\mid a_n\implies v_p(a_{nk})=v_p(a_n)$
La nostra ipotesi è che $\dfrac{\alpha^n-\beta^n}{\alpha-\beta}\equiv0\pmod p$, da cui $\alpha^n\equiv\beta^n\pmod p$. Ora, per il lemma abbiamo $a_{nk}=\dfrac{\alpha^{nk}-\beta^{nk}}{\alpha-\beta}=\dfrac{\alpha^n-\beta^n}{\alpha-\beta}\left(\alpha^{n(k-1)}+\alpha^{n(k-2)}\beta^n+\dots+\beta^{n(k-1)}\right)$. Dobbiamo allora dimostrare che $p$ non divide il mostro nella parentesi, dato che abbiamo fattorizzato un $a_n$; sfruttando il fatto che $\alpha^n\equiv\beta^n\pmod p$ otteniamo che $\alpha^{n(k-1)}+\alpha^{n(k-2)}\beta^n+\dots+\beta^{n(k-1)}\equiv k\alpha^{n(k-1)}\pmod p$. Distinguiamo ora i casi se $D$ è residuo quadratico o no; se lo è, nessun problema, $\alpha$ esiste davvero modulo $p$, e dato che $p\nmid k$ e $p\nmid\alpha$ (per la supposizione $p\nmid P$) il mostro non è divisibile per $p$ e abbiamo fatto; se $D$ non è residuo quadratico, andiamo in $\mathbb Z[\sqrt D]$, ma allora $p$ è primo anche in quell'oggetto (lo lascio a chi vuole) e quindi concludiamo come prima (perché siamo infatti in un dominio d'integrità).
Dunque abbiamo dimostrato lo step 1.
Step 2. $\displaystyle p\mid a_n\implies v_p(a_{np})=v_p(a_n)+1$
Come sopra, dal lemma abbiamo che $a_{np}=a_n\left(\alpha^{n(p-1)}+\dots+\beta^{n(p-1)}\right)$. Dobbiamo quindi dimostrare che nella somma c'è esattamente un fattore $p$ e lo facciamo dicendo che ce n'è almeno uno (parte a) e ce n'è al più uno (parte b).
Inoltre abbiamo $\alpha^n\equiv\beta^n\pmod p\;\;(\ast)$ dal fatto che $p\mid a_n$.
Parte a. $\displaystyle p\mid \alpha^{n(p-1)}+\dots+\beta^{n(p-1)}$
Si ha grazie a $(\ast)$ che $\alpha^{n(p-1)}+\dots+\beta^{n(p-1)}\equiv p\alpha^{n(p-1)}\equiv0\pmod p$, che è quello che volevamo dimostrare.
Parte b. $\displaystyle p^2\nmid \alpha^{n(p-1)}+\dots+\beta^{n(p-1)}$
Da $(\ast)$ possiamo scrivere $\alpha^n=\beta^n+h\sqrt Dp$ con $h$ intero. Chiamiamo $k=h\sqrt D$, $x=\alpha^n$, $y=\beta^n$. Vediamo ora che $\displaystyle x^iy^{p-1-i}=(y+kp)^iy^{p-1-i}=(y^i+ikpy^{i-1}+\binom i 2 y^{i-2}(kp)^2+\dots)y^{p-1-i}$; ma se guardiamo modulo $p^2$ otteniamo $x^iy^{p-1-i}\equiv(y^i+ikpy^{i-1})y^{p-1-i}\equiv y^{p-1}+ikpy^{p-2}\pmod{p^2}$. Quindi finalmente abbiamo che $\alpha^{n(p-1)}+\dots+\beta^{n(p-1)}\equiv p\beta^{n(p-1)}+kp\beta^{n(p-2)}(1+2+\dots+(p-1))\equiv p\beta^{n(p-1)}+\dfrac{p(p-1)}2kp\beta^{n(p-2)}\equiv p\beta^{n(p-1)}\pmod{p^2}$; ma come nello step 1 abbiamo che $p\nmid\beta^{n(p-1)}$, quindi $p^2\nmid p\beta^{n(p-1)}$ e abbiamo finito lo step 2.
Step 3. $\displaystyle p\mid a_n\implies v_p(a_{nk})=v_p(a_n)+v_p(k)$
Per induzione, applichiamo ripetutamente lo step 2 finché esauriamo i fattori $p$ di $k$, e poi usiamo lo step 1 per dire che non ci sono altri fattori $p$.
Sono piuttosto sicuro che funzioni, ma non essendo ancora molto esperto potrebbe essermi sfuggita qualche sottigliezza che renderà tutti questi conti inutili (ma anche no xD)
Già che ci sono quindi provo a generalizzarlo a tutte le sequenze di Lucas...
Siano $S,P$ due interi coprimi e $D=S^2-4P$;
sia $a_0=0,a_1=1,a_{n+1}=Sa_n-Pa_{n-1}$ una successione (di interi ovviamente);
siano poi $\alpha,\beta$ le due radici di $x^2-Sx+P$, ovvero $\alpha=\dfrac{S+\sqrt D}2, \;\beta=\dfrac{S-\sqrt D}2$.
(Nota: i Fibonacci corrispondono a $S=1,P=-1,\alpha=\varphi,\beta=1-\varphi$)
Lemma noto $$a_n=\dfrac{\alpha^n-\beta^n}{\alpha-\beta}$$
Bene, questo fatto ci fa chiaramente vedere la correlazione della sequenza con degli esponenti; inoltre ciò che dobbiamo dimostrare è molto simile a LTE, quindi... ricicliamo la dimostrazione di LTE!
Ovvero:
- se $p\nmid k$ e $p\mid a_n$ allora $v_p(a_{nk})=v_p(a_n)$
- $v_p(a_{np})=v_p(a_n)+1$ nei due step (divide e divide esattamente)
- induzione banale per concludere
Per sicurezza escludiamo dalla dimostrazione il $2$ e i primi che dividono $S,D$ o $P$. (nel caso dei Fibonacci solo il $5$)
Step 1. $\displaystyle p\nmid k,\;p\mid a_n\implies v_p(a_{nk})=v_p(a_n)$
La nostra ipotesi è che $\dfrac{\alpha^n-\beta^n}{\alpha-\beta}\equiv0\pmod p$, da cui $\alpha^n\equiv\beta^n\pmod p$. Ora, per il lemma abbiamo $a_{nk}=\dfrac{\alpha^{nk}-\beta^{nk}}{\alpha-\beta}=\dfrac{\alpha^n-\beta^n}{\alpha-\beta}\left(\alpha^{n(k-1)}+\alpha^{n(k-2)}\beta^n+\dots+\beta^{n(k-1)}\right)$. Dobbiamo allora dimostrare che $p$ non divide il mostro nella parentesi, dato che abbiamo fattorizzato un $a_n$; sfruttando il fatto che $\alpha^n\equiv\beta^n\pmod p$ otteniamo che $\alpha^{n(k-1)}+\alpha^{n(k-2)}\beta^n+\dots+\beta^{n(k-1)}\equiv k\alpha^{n(k-1)}\pmod p$. Distinguiamo ora i casi se $D$ è residuo quadratico o no; se lo è, nessun problema, $\alpha$ esiste davvero modulo $p$, e dato che $p\nmid k$ e $p\nmid\alpha$ (per la supposizione $p\nmid P$) il mostro non è divisibile per $p$ e abbiamo fatto; se $D$ non è residuo quadratico, andiamo in $\mathbb Z[\sqrt D]$, ma allora $p$ è primo anche in quell'oggetto (lo lascio a chi vuole) e quindi concludiamo come prima (perché siamo infatti in un dominio d'integrità).
Dunque abbiamo dimostrato lo step 1.
Step 2. $\displaystyle p\mid a_n\implies v_p(a_{np})=v_p(a_n)+1$
Come sopra, dal lemma abbiamo che $a_{np}=a_n\left(\alpha^{n(p-1)}+\dots+\beta^{n(p-1)}\right)$. Dobbiamo quindi dimostrare che nella somma c'è esattamente un fattore $p$ e lo facciamo dicendo che ce n'è almeno uno (parte a) e ce n'è al più uno (parte b).
Inoltre abbiamo $\alpha^n\equiv\beta^n\pmod p\;\;(\ast)$ dal fatto che $p\mid a_n$.
Parte a. $\displaystyle p\mid \alpha^{n(p-1)}+\dots+\beta^{n(p-1)}$
Si ha grazie a $(\ast)$ che $\alpha^{n(p-1)}+\dots+\beta^{n(p-1)}\equiv p\alpha^{n(p-1)}\equiv0\pmod p$, che è quello che volevamo dimostrare.
Parte b. $\displaystyle p^2\nmid \alpha^{n(p-1)}+\dots+\beta^{n(p-1)}$
Da $(\ast)$ possiamo scrivere $\alpha^n=\beta^n+h\sqrt Dp$ con $h$ intero. Chiamiamo $k=h\sqrt D$, $x=\alpha^n$, $y=\beta^n$. Vediamo ora che $\displaystyle x^iy^{p-1-i}=(y+kp)^iy^{p-1-i}=(y^i+ikpy^{i-1}+\binom i 2 y^{i-2}(kp)^2+\dots)y^{p-1-i}$; ma se guardiamo modulo $p^2$ otteniamo $x^iy^{p-1-i}\equiv(y^i+ikpy^{i-1})y^{p-1-i}\equiv y^{p-1}+ikpy^{p-2}\pmod{p^2}$. Quindi finalmente abbiamo che $\alpha^{n(p-1)}+\dots+\beta^{n(p-1)}\equiv p\beta^{n(p-1)}+kp\beta^{n(p-2)}(1+2+\dots+(p-1))\equiv p\beta^{n(p-1)}+\dfrac{p(p-1)}2kp\beta^{n(p-2)}\equiv p\beta^{n(p-1)}\pmod{p^2}$; ma come nello step 1 abbiamo che $p\nmid\beta^{n(p-1)}$, quindi $p^2\nmid p\beta^{n(p-1)}$ e abbiamo finito lo step 2.
Step 3. $\displaystyle p\mid a_n\implies v_p(a_{nk})=v_p(a_n)+v_p(k)$
Per induzione, applichiamo ripetutamente lo step 2 finché esauriamo i fattori $p$ di $k$, e poi usiamo lo step 1 per dire che non ci sono altri fattori $p$.
Sono piuttosto sicuro che funzioni, ma non essendo ancora molto esperto potrebbe essermi sfuggita qualche sottigliezza che renderà tutti questi conti inutili (ma anche no xD)
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: 174. Fibonacci cannonoso
Uhm, riguardando bene mi sono accorto che quello che ho lasciato per esercizio è falso! 
A questo punto allora dimostro la cosa giusta: se $ D$ non è residuo quadratico $\mod p $ e $\mathbb Z [\sqrt D] $ è UFD (e nel caso dei Fibonacci lo è), allora $ p $ è primo. Infatti scrivendo $ p=ab $ e passando alle norme otteniamo $ p^2=N (a)N (b)$ che implica wlog $ p\mid N (a) =x^2-Dy^2$; se $ p\nmid y $ allora nella congruenza possiamo moltiplicare per il suo inverso e otteniamo che $ D $ è residuo quadratico. Ma allora $ p\mid x,y $ e quindi $ N (b)=\pm1 $, quindi $ b $ è un'unità, allora $ p $ è irriducibile ed essendo in un UFD è anche primo.
Anche se boh, parrebbe funzionare anche quando non è UFD...
A questo punto allora dimostro la cosa giusta: se $ D$ non è residuo quadratico $\mod p $ e $\mathbb Z [\sqrt D] $ è UFD (e nel caso dei Fibonacci lo è), allora $ p $ è primo. Infatti scrivendo $ p=ab $ e passando alle norme otteniamo $ p^2=N (a)N (b)$ che implica wlog $ p\mid N (a) =x^2-Dy^2$; se $ p\nmid y $ allora nella congruenza possiamo moltiplicare per il suo inverso e otteniamo che $ D $ è residuo quadratico. Ma allora $ p\mid x,y $ e quindi $ N (b)=\pm1 $, quindi $ b $ è un'unità, allora $ p $ è irriducibile ed essendo in un UFD è anche primo.
Anche se boh, parrebbe funzionare anche quando non è UFD...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
-
darkcrystal
- Messaggi: 706
- Iscritto il: 14 set 2005, 11:39
- Località: Chiavari
Re: 174. Fibonacci cannonoso
Premetto che non ho letto tutto; il punto che mi preme è il seguente:
A beneficio del pubblico,
Dicevamo, voglio un irriducibile che non sia primo. Sostengo che l'uguaglianza $4 = 2\cdot 2 = (\sqrt{5}+1)(\sqrt{5}-1)$ mi darà un tale esempio: voglio vedere che $2$ è irriducibile e che non è primo.
Definisco la norma di un elemento $a=x+y\sqrt{5}$ come $N(a)=x^2-5y^2$. E' una funzione moltiplicativa con le proprietà che ci si aspettano, in particolare le unità sono esattamente quegli $a$ tali che $N(a) = \pm 1$. Attenzione che in questo caso la norma non coincide con (il quadrato del)la norma complessa, quindi bisogna verificare a mano che sia effettivamente moltiplicativa, ed in più non assume solo valori positivi.
E ora cominciamo con santa pazienza:
Tuttociòpremesso, quello che è effettivamente un UFD è il ben più simpatico $\mathbb{Z}\big[\frac{1+\sqrt{5}}{2}\big]$, dove il problema di cui sopra sparisce, perché in questo anello $2$ divide $1+\sqrt{5}$: questa non è una verità molto profonda, semplicemente ci siamo premurati di aggiungere $\frac{1+\sqrt{5}}{2}$.
Ricetta generale che non posso giustificare in maniera semplice: se $D$ è un intero congruo ad 1 modulo 4 (e che non è un quadrato) e avete la tentazione di lavorare in $\mathbb{Z}[\sqrt{D}]$, non fatelo, perché non è mai un UFD. Quello che ha speranze di essere un UFD è $\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$ (vedere ad esempio cosa succede per $D=-3$!)
Esercizio (di Drago96, versione riveduta e corretta) Sia $D$ un intero libero da quadrati e supponiamo che $D$ non sia un residuo quadratico modulo $p$ per un certo $p$. Mostrare che $p$ è primo (ebbene sì!) anche in
\[
\begin{cases} \mathbb{Z}[\sqrt{D}], \mbox{ se }D \not \equiv 1 \pmod 4 \\
\mathbb{Z}[\frac{1+\sqrt{D}}{2}], \mbox{ se }D \equiv 1 \pmod 4 \\
\end{cases}
\]
Bonus: resta vero perfino in $\mathbb{Z}[\sqrt{D}]$ anche quando $D \equiv 1 \pmod 4$ (in realtà si fa nello stesso modo, solo che in un certo senso come risultato è più sorprendente...)
Dimostrazione: troviamo un elemento irriducibile che non è primo.Svariati saggi nella storia ha scritto:$\mathbb{Z}[\sqrt{5}]$ NON è un UFD!
A beneficio del pubblico,
- un elemento $a$ si dice "irriducibile" se (non è un'unità, cioè un elemento invertibile, ed inoltre) tutte le volte che ho una fattorizzazione $a=bc$ uno tra $b$ e $c$ è un'unità.
- un elemento $a$ si dice "primo" se tutte le volte che $a|bc$ si ha $a|b$ oppure $a|c$.
Dicevamo, voglio un irriducibile che non sia primo. Sostengo che l'uguaglianza $4 = 2\cdot 2 = (\sqrt{5}+1)(\sqrt{5}-1)$ mi darà un tale esempio: voglio vedere che $2$ è irriducibile e che non è primo.
Definisco la norma di un elemento $a=x+y\sqrt{5}$ come $N(a)=x^2-5y^2$. E' una funzione moltiplicativa con le proprietà che ci si aspettano, in particolare le unità sono esattamente quegli $a$ tali che $N(a) = \pm 1$. Attenzione che in questo caso la norma non coincide con (il quadrato del)la norma complessa, quindi bisogna verificare a mano che sia effettivamente moltiplicativa, ed in più non assume solo valori positivi.
E ora cominciamo con santa pazienza:
- $2$ è irriducibile: supponiamo, al contrario, di avere $2=ab$ con $a, b \in \mathbb{Z}[\sqrt{5}]$. Allora $4=N(2)=N(a)N(b)$, e se vogliamo che $a,b$ non siano unità si deve avere $N(a) = \pm 2$. Scrivendo $a=x+y\sqrt{5}$ otteniamo allora $x^2-5y^2=\pm 2$, che un rapido controllo modulo 5 ci dice essere impossibile. Dunque 2 è irriducibile.
- $2$ non è primo: infatti $2$ divide $2 \cdot 2 = (\sqrt{5}+1)(\sqrt{5}-1)$, e se fosse primo dividerebbe almeno uno tra $(\sqrt{5}+1)$ e $(\sqrt{5}-1)$. Ma questo non è possibile! Perché? Basta rifarsi alla definizione di divisibilità: $2$ divide $\sqrt{5} \pm 1$ se e solo se esiste un certo $b=w+z\sqrt{5}$ con $w,z$ interi tale che $2b=\sqrt{5} \pm 1$. Ma questo è impossibile, perché vuol dire in particolare $2w=1$.
Tuttociòpremesso, quello che è effettivamente un UFD è il ben più simpatico $\mathbb{Z}\big[\frac{1+\sqrt{5}}{2}\big]$, dove il problema di cui sopra sparisce, perché in questo anello $2$ divide $1+\sqrt{5}$: questa non è una verità molto profonda, semplicemente ci siamo premurati di aggiungere $\frac{1+\sqrt{5}}{2}$.
Ricetta generale che non posso giustificare in maniera semplice: se $D$ è un intero congruo ad 1 modulo 4 (e che non è un quadrato) e avete la tentazione di lavorare in $\mathbb{Z}[\sqrt{D}]$, non fatelo, perché non è mai un UFD. Quello che ha speranze di essere un UFD è $\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$ (vedere ad esempio cosa succede per $D=-3$!)
Esercizio (di Drago96, versione riveduta e corretta) Sia $D$ un intero libero da quadrati e supponiamo che $D$ non sia un residuo quadratico modulo $p$ per un certo $p$. Mostrare che $p$ è primo (ebbene sì!) anche in
\[
\begin{cases} \mathbb{Z}[\sqrt{D}], \mbox{ se }D \not \equiv 1 \pmod 4 \\
\mathbb{Z}[\frac{1+\sqrt{D}}{2}], \mbox{ se }D \equiv 1 \pmod 4 \\
\end{cases}
\]
Bonus: resta vero perfino in $\mathbb{Z}[\sqrt{D}]$ anche quando $D \equiv 1 \pmod 4$ (in realtà si fa nello stesso modo, solo che in un certo senso come risultato è più sorprendente...)
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein
Membro dell'EATO
Membro dell'EATO
Re: 174. Fibonacci cannonoso
Cavolo, mi sono dimenticato di questo fatto fondamentale... -.-
Bene, ora devo dimostrare il bonus e tutto il resto funziona (spero!)
Bene, ora devo dimostrare il bonus e tutto il resto funziona (spero!)
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
-
darkcrystal
- Messaggi: 706
- Iscritto il: 14 set 2005, 11:39
- Località: Chiavari
Re: 174. Fibonacci cannonoso
Sisi, ma sostanzialmente la dimostrazione è quella che hai dato sopra, se ci pensi un attimo; la pappardella era per tentare di spazzare via un certo numero di dubbi ricorrenti 
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein
Membro dell'EATO
Membro dell'EATO
Re: 174. Fibonacci cannonoso
Sì, infatti arrivati a $ p\mid x, y$ praticamente per definizione si ha anche $ p\mid a $.
Quindi, to sum up:
Quindi, to sum up:
- se $ D $ è residuo quadratico, allora siamo contenti perché $\sqrt D $ esiste davvero e continuano a valere tutte le le solite proprietà di $\mathbb Z_p $
- se $ D $ non è residuo quadratico, dobbiamo aggiungerlo, quindi non vale più Fermat, ad esempio; però in ogni caso $ p $ è primo anche in $\mathbb Z [\sqrt D] $; inoltre
- se $ D\equiv1\pmod4 $ allora $\mathbb Z [\sqrt D] $ non è UFD, mentre ha qualche speranza $\mathbb Z [\dfrac {1+\sqrt D} 2] $ ed in questo campo $ p $ è primo
- se $ D\equiv3\pmod4 $ allora $\mathbb Z [\sqrt D] $ potrebbe essere UFD
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
-
FrancescoVeneziano
- Site Admin
- Messaggi: 606
- Iscritto il: 01 gen 1970, 01:00
- Località: Genova
- Contatta:
Re: 174. Fibonacci cannonoso
Sì, quelli con D negativo sono esattamente −1,−2,−3,−7,−11,−19,−43,−67,−163 (con l'accortezza, come ha detto darkcrystal, che per D congruo ad 1 modulo 4 ad essere UFD è $\mathbb{Z}\left[ \frac{1+\sqrt{D}}{2}\right]$.Drago96 ha scritto:Se non erro i campi quadratici UFD con $ D $ positivo sono ancora sconosciuti (a parte molti piccoli), mentre per $ D $ negativo sono finiti ed è noto l'elenco
Quelli con D positivo sono un sacco, ed anche grandi. La congettura, aperta dai tempi di Gauss, è che siano infiniti, ed è fortemente suggerito da argomentazioni euristiche e dati sperimentali che abbiano una densità di un po' più di 3/4.
Wir müssen wissen. Wir werden wissen.
-
Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25