Esercizio teorema cinese dei resti
Sto provando a risolvere il seguente sistema di congruenze algebriche:
$\{(14x -= 10_(mod12)),(3x -= 2_(mod5)):}$
e dovrei calcolare l'inverso moltiplicativo di $14_mod12$ e di $3_mod5$, solo che per la prima non so come fare in quanto $(14,12)$ non sono coprimi e $12$ non e' primo. Vorrei "dividere" la prima equazione per $2$, solo che ho il dubbio che l'equazione risultante non sia equivalente all'originale...
$\{(14x -= 10_(mod12)),(3x -= 2_(mod5)):}$
e dovrei calcolare l'inverso moltiplicativo di $14_mod12$ e di $3_mod5$, solo che per la prima non so come fare in quanto $(14,12)$ non sono coprimi e $12$ non e' primo. Vorrei "dividere" la prima equazione per $2$, solo che ho il dubbio che l'equazione risultante non sia equivalente all'originale...
Risposte
La tua idea non è sbagliata. Basta ragionarci un attimo sopra per non fare errori.
$14x-=10_(mod12) => 14x-10=12*k$, $k in ZZ => 2(7x-5)=2*6*k => 7x-5=6k => 7x-=5_(mod6) => x-=5_(mod6)$
$14x-=10_(mod12) => 14x-10=12*k$, $k in ZZ => 2(7x-5)=2*6*k => 7x-5=6k => 7x-=5_(mod6) => x-=5_(mod6)$
Si!!! $1_mod_6$ e' un inverso moltiplicativo di $7_mod_6$, quindi si puo' fare 
Grazie
Grazie
Arrivo alla soluzione del sistema con $x-=29_(mod_30)$, mentre il libro reca la soluzione $x-=29_(mod_60)$. Avendo diviso per $2$ la prima equazione
ho provato a riportare in modulo 60 la mia equazione, e verrebbe $2x-=58_(mod_60)$, pero' ora ho il dubbio se devo moltiplicare per l'inverso di $2_mod_60$.... e mi perdo
qualcosa.
ho provato a riportare in modulo 60 la mia equazione, e verrebbe $2x-=58_(mod_60)$, pero' ora ho il dubbio se devo moltiplicare per l'inverso di $2_mod_60$.... e mi perdo
qualcosa.
La tua soluzione è $x in {...,-31,-1,29,59,89,...}$.
Quella del libro invece è $x in {...,-31,29,89,...}$.
Secondo me hai ragione tu e ha torto marcio il libro
Ad esempio si vede velocemente che $x=-1$ è una particolare soluzione, e il libro non la contempla.
Ripeto: la soluzione corretta è la tua, ovvero $x-=29_(mod30)$, che si può anche scrivere come $x-=-1_(mod30)$
Quella del libro invece è $x in {...,-31,29,89,...}$.
Secondo me hai ragione tu e ha torto marcio il libro
Ad esempio si vede velocemente che $x=-1$ è una particolare soluzione, e il libro non la contempla.
Ripeto: la soluzione corretta è la tua, ovvero $x-=29_(mod30)$, che si può anche scrivere come $x-=-1_(mod30)$
Ho capito.
Che dire, se non "meglio cosi'"
Grazie
Che dire, se non "meglio cosi'"
Grazie
Prego. Aggiungo una cosa:
Come avrai notato, ho "diviso per 2" sia il $14$, sia il $10$, sia il $12$.
Questo discorso si può facilmente generalizzare:
Penso che ti potrà essere utile per i prossimi esercizi
$14x-=10_(mod12) => ... => x-=5_(mod6)$
Come avrai notato, ho "diviso per 2" sia il $14$, sia il $10$, sia il $12$.
Questo discorso si può facilmente generalizzare:
Consideriamo la seguente equazione congruenziale $ax-=b_(mod c)$A te la dimostrazione (basta seguire ciò che ho scritto io prima).
con $a,b,c in ZZ$ tali che $EE h in ZZ$, ($h !=0$) : $a=h*bar(a)$, $b=h*bar(b)$, $c=h*bar(c)$ (cioè sono tutti multipli di uno stesso numero $h$).
allora $ax-=b_(mod c)$ è equivalente a $bar(a)x-=bar(b)_(mod bar(c))$
Penso che ti potrà essere utile per i prossimi esercizi
Ok, provo a ragionarci e poi ti rispondo.
"Gi8":
Secondo me hai ragione tu e ha torto marcio il libro
Appunto... curiosità: che libro?
Esercizi di Algebra, di Fontana/Gabelli, editore Aracne.
"Gi8":
Prego. Aggiungo una cosa:
$14x-=10_(mod12) => ... => x-=5_(mod6)$
Come avrai notato, ho "diviso per 2" sia il $14$, sia il $10$, sia il $12$.
Questo discorso si può facilmente generalizzare:
Consideriamo la seguente equazione congruenziale $ax-=b_(mod c)$A te la dimostrazione (basta seguire ciò che ho scritto io prima).
con $a,b,c in ZZ$ tali che $EE h in ZZ$, ($h !=0$) : $a=h*bar(a)$, $b=h*bar(b)$, $c=h*bar(c)$ (cioè sono tutti multipli di uno stesso numero $h$).
allora $ax-=b_(mod c)$ è equivalente a $bar(a)x-=bar(b)_(mod bar(c))$
Penso che ti potrà essere utile per i prossimi esercizi
Non riesco a formalizzare la dimostrazione... io pensavo al fatto che i termini della prima congruenza algebrica,
per definizione, appartengono alla stessa classe dei resti, stessa cosa per i termini dell'equazione
equivalente che apparterrano anch'essi ad una stessa classe dei resti, ma essendo quest'ultimi dei
sottomultipli della prima equazione, allora la classe dei resti dei secondi fa parte di un
sottoinsieme dell'insieme che contiene la prima classe dei resti.
Non so se mi sono spiegato.....
Guarda, è "molto" semplice. Ti stai perdendo in un bicchiere d'acqua. Come ti ho già detto, bastava seguire ciò che ti ho scritto prima:
In modo assolutamente analogo arrivi a dimostrare questo:
Suggerimento: parti scrivendo $ax-=b_(mod c)=>...$ e vai avanti
"Gi8":
$14x-=10_(mod12) => 14x-10=12*k$, $k in ZZ => 2(7x-5)=2*6*k => 7x-5=6k => 7x-=5_(mod6)
In modo assolutamente analogo arrivi a dimostrare questo:
Consideriamo la seguente equazione congruenziale $ax-=b_(mod c)$
con $a,b,c in ZZ$ tali che $EE h in ZZ$, ($h !=0$) : $a=h*bar(a)$, $b=h*bar(b)$, $c=h*bar(c)$ (cioè sono tutti multipli di uno stesso numero $h$).
allora $ax-=b_(mod c)$ è equivalente a $bar(a)x-=bar(b)_(mod bar(c))$
Suggerimento: parti scrivendo $ax-=b_(mod c)=>...$ e vai avanti
All'inizio avevo pensato a questa dimostrazione:
$ax -= b_(mod_c)$ equivalente $bar(a)x -= bar(b)_(mod_bar(c))$
implica che per $a,b,c$ un divisore comune; posto $d=MCD(a,b,c)$ si ha che
$d|a ^^ d|b ^^ d|c$ da cui $a=a'd$, $b=b'd$ e $c=c'd$
$ax -= b_(mod_c)$ puo' essere scritta come $ax -kc = b$ e sostituendo si ha
$a'dx - kc'd = b'd$ e $d(a'x - kc') = d(b')$
che dovrebbe essere la nostra tesi.
Solo che poi ho pensato che dovrei dimostrare che $d=h$ o per lo meno che $d$ puo' essere
un multiplo di $h$, e quindi mi sono un po' arenato...
$ax -= b_(mod_c)$ equivalente $bar(a)x -= bar(b)_(mod_bar(c))$
implica che per $a,b,c$ un divisore comune; posto $d=MCD(a,b,c)$ si ha che
$d|a ^^ d|b ^^ d|c$ da cui $a=a'd$, $b=b'd$ e $c=c'd$
$ax -= b_(mod_c)$ puo' essere scritta come $ax -kc = b$ e sostituendo si ha
$a'dx - kc'd = b'd$ e $d(a'x - kc') = d(b')$
che dovrebbe essere la nostra tesi.
Solo che poi ho pensato che dovrei dimostrare che $d=h$ o per lo meno che $d$ puo' essere
un multiplo di $h$, e quindi mi sono un po' arenato...
Aspetta, forse non sono stato molto chiaro io. Ripeto:
Metto in spoiler la dimostrazione
Teorema:
Siano $a,b,c in ZZ$ tali che $a=h*bar(a)$, $b=h*bar(b)$, $c=h*bar(c)$, con $h in ZZ$ e $h !=0$.
Allora l'equazione conguenziale $ax-=b_(mod c)$ è equivalente all'equazione congruenziale $bar(a)x-=bar(b)_(mod bar(c))$
Metto in spoiler la dimostrazione
In effetti cosi' e' veramente banale la dimostrazione, mentre io pensavo (come ti ho indicato 
) a tutt'altra cosa.
A questo punto, il mio ragionamento puo' avere un senso?
) a tutt'altra cosa.A questo punto, il mio ragionamento puo' avere un senso?
"GundamRX91":
A questo punto, il mio ragionamento puo' avere un senso?
Insomma, non molto
Hai fatto dei passaggi contorti e poco chiari.
Un consiglio per il futuro: cerca sempre di essere il più semplice e preciso possibile. Buona continuazione
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo