Dimostrazione sulle congruenze
Mi sono trovato davanti al seguente esercizio:
Sia $p$ $primo$ e $a,binZZ$ Chiamato $A=\sum_{i=0}^p a^ib^(p-i)$
dimostrare che $A-=a$ $(modp)$ se $a-=b$ $(modp)$
eche $A-=a+b$ $(modp)$ se $a!=b$ $(modp)$(leggere "non congruente", non ho trovato il simbolo..)
Ora ho svolto semplicemente la prima parte, sostituendo $a=kp + b$ , facendo pochi passaggi il risultato era chiaro.
Ma per la seconda parte non riesco proprio a giungere alla soluzione, ho provato utilizzando il binomio di newton (cercando di portare un coeff. binomiale nella sommatoria) ma con scarso successo, ho anche tentato di svolgere la sommatoria cercando di "eliminare" fattori congrui a $p$, così facendo sono giunto al punto in cui dimostrare che $p$ divide $\sum_{i=1}^(p-i) a^ib^(p-1)$ sarebbe sufficiente a darmi il risultato sperato!
Ma non riesco comunque a cavarne le gambe, un aiutino? Magari per induzione, nel caso come posso usare il primo successivo? Idee migliori?
Sia $p$ $primo$ e $a,binZZ$ Chiamato $A=\sum_{i=0}^p a^ib^(p-i)$
dimostrare che $A-=a$ $(modp)$ se $a-=b$ $(modp)$
eche $A-=a+b$ $(modp)$ se $a!=b$ $(modp)$(leggere "non congruente", non ho trovato il simbolo..)
Ora ho svolto semplicemente la prima parte, sostituendo $a=kp + b$ , facendo pochi passaggi il risultato era chiaro.
Ma per la seconda parte non riesco proprio a giungere alla soluzione, ho provato utilizzando il binomio di newton (cercando di portare un coeff. binomiale nella sommatoria) ma con scarso successo, ho anche tentato di svolgere la sommatoria cercando di "eliminare" fattori congrui a $p$, così facendo sono giunto al punto in cui dimostrare che $p$ divide $\sum_{i=1}^(p-i) a^ib^(p-1)$ sarebbe sufficiente a darmi il risultato sperato!
Ma non riesco comunque a cavarne le gambe, un aiutino? Magari per induzione, nel caso come posso usare il primo successivo? Idee migliori?
Risposte
Ciao! Hai un po' di dimestichezza con i gruppi?
Comunque suppongo che $A$ sia $ \sum_{i=0}^(p) a^ib^(p-i) $, e non $ \sum_{i=0}^(p) a^ib^(p-1) $, altrimenti gia' il primo risultato sarebbe falso
Comunque suppongo che $A$ sia $ \sum_{i=0}^(p) a^ib^(p-i) $, e non $ \sum_{i=0}^(p) a^ib^(p-1) $, altrimenti gia' il primo risultato sarebbe falso
Hai ragione ho sbagliato a scrivere, ho già modificato sopra.
In quanto ai gruppi, non ho moltissima dimestichezza, cioè so come lavorarci ma non sono ferratissimo.
Secondo te sarebbe il giusto approccio per questo esercizio?
In quanto ai gruppi, non ho moltissima dimestichezza, cioè so come lavorarci ma non sono ferratissimo.
Secondo te sarebbe il giusto approccio per questo esercizio?
Ok, non ti serve molto da sapere, e direi che un approccio puo' essere il seguente (magari ne esiste uno piu' facile, non so).
Hai osservato che basta mostrare che $p$ divide
$ab^{p-1}+a^2b^{p-2}+...a^{p-2}b^2+a^{p-1}b= \sum_{i=1}^(p-1) a^ib^(p-i) $,
ed e' quello che vogliamo verificare. Se $p$ divide uno tra $a$ e $b$ il risultato e' immediato. Quindi supponiamo che $p$ non divida nessuno dei due. Raccogli $b$ ed eliminalo, e ti riduci a $ab^{p-2}+a^2b^{p-3}+...a^{p-2}b+a^{p-1}$.
Ricorda che la somma degli elementi non nulli in $\mathbb{Z}_p$ fa zero (viene con la formula solita della somma di interi consecutivi), quindi e' sufficiente dimostrare che quella somma e' in realta' una somma di distinti rappresentanti (non nulli) di $\mathbb{Z}_p$. Prendi $ab^{p-1}$. Osserva che questo numero non e' $1$ modulo $p$, grazie all'ipotesi. Se riesci a dimostrare che questo elemento ha ordine $p-1$, e in particolare che genera ogni addendo di quella somma, hai finito (stai di fatto prendendo un numero diverso da zero e uno in $\mathbb{Z}_p$ e stai vedendo che genera il gruppo moltiplicativo $U(\mathbb{Z}_p)$ degli invertibili, che ha ordine $p-1$). Questo e' facile da fare.
Spero ti ritrovi, fammi sapere se non e' chiaro qualcosa! Ciao
Hai osservato che basta mostrare che $p$ divide
$ab^{p-1}+a^2b^{p-2}+...a^{p-2}b^2+a^{p-1}b= \sum_{i=1}^(p-1) a^ib^(p-i) $,
ed e' quello che vogliamo verificare. Se $p$ divide uno tra $a$ e $b$ il risultato e' immediato. Quindi supponiamo che $p$ non divida nessuno dei due. Raccogli $b$ ed eliminalo, e ti riduci a $ab^{p-2}+a^2b^{p-3}+...a^{p-2}b+a^{p-1}$.
Ricorda che la somma degli elementi non nulli in $\mathbb{Z}_p$ fa zero (viene con la formula solita della somma di interi consecutivi), quindi e' sufficiente dimostrare che quella somma e' in realta' una somma di distinti rappresentanti (non nulli) di $\mathbb{Z}_p$. Prendi $ab^{p-1}$. Osserva che questo numero non e' $1$ modulo $p$, grazie all'ipotesi. Se riesci a dimostrare che questo elemento ha ordine $p-1$, e in particolare che genera ogni addendo di quella somma, hai finito (stai di fatto prendendo un numero diverso da zero e uno in $\mathbb{Z}_p$ e stai vedendo che genera il gruppo moltiplicativo $U(\mathbb{Z}_p)$ degli invertibili, che ha ordine $p-1$). Questo e' facile da fare.
Spero ti ritrovi, fammi sapere se non e' chiaro qualcosa! Ciao
Per prima cosa voglio ringraziarti per la risposta.
Ho capito il procedimento che mi hai suggerito, e in linea teorica mi torna tutto. Le mie perplessità sono sul fatto che non capisco come $ab^(p-1)$ possa essere un generatore per quella serie di addendi, inoltra per fermat non posso scrivere$b^(p-1)=1$ ? in tal caso mi rimarrebbe solo $a$ che non capisco come possa essere un generatore. Ora continuando questo procedimento posso fare la stessa cosa all'elemento $a^(p-1)b$ lasciandolo scritto come $b$, non so però cosa farmene, questi due usati assieme sarebbero effettivamente generatori di quegli addendi, però non ho idea di come si faccia.
Inoltre questo esercizio è in una sezione del libro dove questi concetti non sono ancora stati spiegati, cioè in verità è proprio nel libro "1" mentre i concetti di generatori sono trattati nel secondo libro (secondo anno), quindi credo che l'esercizio possa essere svolto con mezzi più terra terra, anche se personalmente trovo questo approccio molto astuto!
Ho capito il procedimento che mi hai suggerito, e in linea teorica mi torna tutto. Le mie perplessità sono sul fatto che non capisco come $ab^(p-1)$ possa essere un generatore per quella serie di addendi, inoltra per fermat non posso scrivere$b^(p-1)=1$ ? in tal caso mi rimarrebbe solo $a$ che non capisco come possa essere un generatore. Ora continuando questo procedimento posso fare la stessa cosa all'elemento $a^(p-1)b$ lasciandolo scritto come $b$, non so però cosa farmene, questi due usati assieme sarebbero effettivamente generatori di quegli addendi, però non ho idea di come si faccia.
Inoltre questo esercizio è in una sezione del libro dove questi concetti non sono ancora stati spiegati, cioè in verità è proprio nel libro "1" mentre i concetti di generatori sono trattati nel secondo libro (secondo anno), quindi credo che l'esercizio possa essere svolto con mezzi più terra terra, anche se personalmente trovo questo approccio molto astuto!
Hai ragione, errore mio: il generatore e' $ab^{p-2}$, che e' $ab^{-1}$. Cerco anche di semplificare.
Quello che sto facendo e' raccogliere $b$ e ottenere
$b(ab^{p-2}+a^2b^{p-3}+...a^{p-2}b+a^{p-1}) $
quindi e' necessario e sufficiente mostrare che la parentesi e' multiplo di $p$, visto che $b$ si assume coprimo con $p$.
Inoltre, essendo $b^{p-1}=1 \mod p$, modulo $p$ quella somma in parentesi diventa
$ab^{-1}+a^2b^{-2}+...+a^{p-2}b^{-(p-2)}+1$.
Qundi ora e' chiaro che $ab^{-1}$ genera.
Non mi viene in mente un approccio piu' elementare, soprattutto questa mi pare la maniera piu' naturale di usare l'ipotesi che $a \ne b \mod p$. Quali sono gli argomenti coperti dal libro 1?
Ciao
Quello che sto facendo e' raccogliere $b$ e ottenere
$b(ab^{p-2}+a^2b^{p-3}+...a^{p-2}b+a^{p-1}) $
quindi e' necessario e sufficiente mostrare che la parentesi e' multiplo di $p$, visto che $b$ si assume coprimo con $p$.
Inoltre, essendo $b^{p-1}=1 \mod p$, modulo $p$ quella somma in parentesi diventa
$ab^{-1}+a^2b^{-2}+...+a^{p-2}b^{-(p-2)}+1$.
Qundi ora e' chiaro che $ab^{-1}$ genera.
Non mi viene in mente un approccio piu' elementare, soprattutto questa mi pare la maniera piu' naturale di usare l'ipotesi che $a \ne b \mod p$. Quali sono gli argomenti coperti dal libro 1?
Ciao
Ok il discorso mi torna perfettamente, e abbiamo provato che $ab^(-1)$ è effettivamente un generatore per quegli addendi, non resta da provare che $ab^(-1)$ è anche generatore di $ZZ_p$?
Sicuramente sono io ad ignorare la banalità di questa richiesta, però ripeto questo argomento non l'ho ancora trattato nel corso, l'ho giusto studiato per conto mio per curiosità!
Il libro copre più o meno: diofantee, relazioni, congruenze, anelli, ideali, omomorfismi di anelli, anelli di polinomi, fattorizzazione, pid, ufd, ideali primi e massimali.
Grazie ancora per il tuo tempo!
Sicuramente sono io ad ignorare la banalità di questa richiesta, però ripeto questo argomento non l'ho ancora trattato nel corso, l'ho giusto studiato per conto mio per curiosità!
Il libro copre più o meno: diofantee, relazioni, congruenze, anelli, ideali, omomorfismi di anelli, anelli di polinomi, fattorizzazione, pid, ufd, ideali primi e massimali.
Grazie ancora per il tuo tempo!
"Romy88":
Ok il discorso mi torna perfettamente, e abbiamo provato che $ab^(-1)$ è effettivamente un generatore per quegli addendi, non resta da provare che $ab^(-1)$ è anche generatore di $ZZ_p$?
Sicuramente sono io ad ignorare la banalità di questa richiesta, però ripeto questo argomento non l'ho ancora trattato nel corso, l'ho giusto studiato per conto mio per curiosità!
No accidenti, hai ragionissima! E' una domanda giusta, ho commesso io una leggerezza. Non è infatti affatto vero che, come elemento di $\mathbb{Z}_p^{\star}$, $ab^{-1}$ generi tutto $\mathbb{Z}_p^{\star}$ (non $ZZ_p$, fa' attenzione). Il mio modo era anche inutilmente più complicato!
Ma la questione si può mettere a posto così. Visto che gli anelli dovresti conoscerli, considera l'anello $(ZZ_p, +, \cdot)$. Poniamo $x := ab^{-1} \in ZZ_p$ e considera la quantità $y:=1+x+...x^{p-2}$. Vogliamo vedere che è zero. Poiché $x^{p-1}=1$ (Fermat), abbiamo facimente che $yx=y$, ovvero $y(x-1)=0$. Ma questo significa, poiché $ZZ_p$ è un campo (e quindi un dominio) che $y=0$ oppure $x=1$. La seconda possibilità non sussiste perché avresti $ab^{-1}=1$ in $ZZ_p$ ovvero $a \equiv b \mod p$, contro l'ipotesi. Quindi $y=0$, ovvero come elemento di $ZZ$ quel coso è multiplo di $p$.
Spero che ora tutto sia ok, perdonami per la leggerezza di prima e fammi sapere
Ciao!
Si intendevo $\mathbb{Z}_p^{\star}$, ma non avevo trovato il modo per scriverlo! (grazie comunque di averlo puntualizzato!)
Effettivamente la questione era ancora più semplice usando le serie geometriche, e in particolare che
$\sum_{i=0}^(p-2) (ab^(-1))^i=(1-(ab^(-1))^(p-1))/(1-a)$
da cui per fermat si giungeva rapidamente alla tesi.
Grazie mille per avermi aiutato, sei stato molto chiaro e disponibilissimo!
Effettivamente la questione era ancora più semplice usando le serie geometriche, e in particolare che
$\sum_{i=0}^(p-2) (ab^(-1))^i=(1-(ab^(-1))^(p-1))/(1-a)$
da cui per fermat si giungeva rapidamente alla tesi.
Grazie mille per avermi aiutato, sei stato molto chiaro e disponibilissimo!
Sì, è la stessa minestra se guardi bene, ma devi fare attenzione a qualche dettaglio (stai lavorando in $ZZ_p$, è poco standard l'uso delle frazioni). Però quella formula la ricavi col metodo elementare classico, appunto moltiplicando la somma per $ab^{-1}$ e vedendo che la somma stessa non cambia (usando Fermat). Quindi :
$ (1-ab^{-1}) \cdot \sum_{i=0}^(p-2) (ab^(-1))^i=0 $.
Figurati!
Ciao
$ (1-ab^{-1}) \cdot \sum_{i=0}^(p-2) (ab^(-1))^i=0 $.
Figurati!
Ciao
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo