Congruenze lineari
ciao a tutti =) ho un problema con le congruenze e vorrei che qualcuno mei chiarisse un pò le idee =) devo svolgere il sistema di congruenze....
{3x≡15(mod21)
{89x≡7(mod11)
{7x≡13(mod15)
io ho provato a farlo, ma credo di aver sbagliato, vi posto come ho fatto:
io ho risolto 3x≡15(mod21) in qst modo:
x≡5(mod7)
poi MCD tra 7 e 1 = 1 quindi è coprimo ed è invertibile, quindi il primo esce x≡ 1(mod7)
poi l'altro ossia 89x≡7(mod11) e 7x≡13(mod15) li ho fatti allo stesso modo quindi alla fine mi esce questo risultato:
{x≡1(mod7)
{x≡89(mod11)
{x≡7(mod15)
è giusto? ho sbagliato?? aiutatemi per favore...
{3x≡15(mod21)
{89x≡7(mod11)
{7x≡13(mod15)
io ho provato a farlo, ma credo di aver sbagliato, vi posto come ho fatto:
io ho risolto 3x≡15(mod21) in qst modo:
x≡5(mod7)
poi MCD tra 7 e 1 = 1 quindi è coprimo ed è invertibile, quindi il primo esce x≡ 1(mod7)
poi l'altro ossia 89x≡7(mod11) e 7x≡13(mod15) li ho fatti allo stesso modo quindi alla fine mi esce questo risultato:
{x≡1(mod7)
{x≡89(mod11)
{x≡7(mod15)
è giusto? ho sbagliato?? aiutatemi per favore...
Risposte
Ciao, per regolamento devi scrivere con le formule, vedi come-si-scrivono-le-formule-asciimathml-e-tex-t26179.html <-- qui
Allora, facciamo un po di chiarezza sulla teoria,consideriamo una congruenza del tipo
$ax-=b(modn)$ dove $a,b,n in ZZ , a!=0$.
Di dimostra che $ax-=b(modn)$ è compatibile se e solo se posto $d=(a,b) => d|b$
Quindi per prima cosa devi accertarti che la congruenza, quando la risolvi, sia compatibile (cioè che ammetta soluzione!)
in secondo luogo.
Si dimostra che $ax-=b(modn)$ è equivalente a $(a/d)x-=b/d(mod(n/d))$
Poniamo per semplicità $a'=a/d$ , $b'=b/d$ , $n'=n/d$.
Il problema ora si traduce nel trovare $x$ verificanti $a'x-=b'(modn')$.
Ora poiché $( (a/d);(n/d))=(a',n')=1 => EE a'^-1 in ZZ_(n') t.c a*a^(-1)=1(modn')$
dunque moltiplicando ambo i membri $a^(-1)$ hai che $x-=(a'^(-1))b'(modn')$
Quindi tutte le soluzioni della congruenza sono della forma $x=(a'^(-1))b'+nk ,k in ZZ$
In particolare vi sono esattamente $d$ soluzioni modulo $n$.
Fatto un po luce su questo, sapresti dirmi ora cosa hai sbagliato e correggere?
Poi pensiamo alla risoluzione del sistema.
"skipt":e va bene
ciao a tutti =) ho un problema con le congruenze e vorrei che qualcuno mei chiarisse un pò le idee =) devo svolgere il sistema di congruenze....
{3x≡15(mod21)
{89x≡7(mod11)
{7x≡13(mod15)
io ho provato a farlo, ma credo di aver sbagliato, vi posto come ho fatto:
io ho risolto 3x≡15(mod21) in qst modo:
x≡5(mod7)
No, qui stai delirando a ruota libera. Non va per niente bene.
poi MCD tra 7 e 1 = 1 quindi è coprimo ed è invertibile, quindi il primo esce x≡ 1(mod7)
poi l'altro ossia 89x≡7(mod11) e 7x≡13(mod15) li ho fatti allo stesso modo quindi alla fine mi esce questo risultato:
{x≡1(mod7)
{x≡89(mod11)
{x≡7(mod15)
è giusto? ho sbagliato?? aiutatemi per favore...
Allora, facciamo un po di chiarezza sulla teoria,consideriamo una congruenza del tipo
$ax-=b(modn)$ dove $a,b,n in ZZ , a!=0$.
Di dimostra che $ax-=b(modn)$ è compatibile se e solo se posto $d=(a,b) => d|b$
Quindi per prima cosa devi accertarti che la congruenza, quando la risolvi, sia compatibile (cioè che ammetta soluzione!)
in secondo luogo.
Si dimostra che $ax-=b(modn)$ è equivalente a $(a/d)x-=b/d(mod(n/d))$
Poniamo per semplicità $a'=a/d$ , $b'=b/d$ , $n'=n/d$.
Il problema ora si traduce nel trovare $x$ verificanti $a'x-=b'(modn')$.
Ora poiché $( (a/d);(n/d))=(a',n')=1 => EE a'^-1 in ZZ_(n') t.c a*a^(-1)=1(modn')$
dunque moltiplicando ambo i membri $a^(-1)$ hai che $x-=(a'^(-1))b'(modn')$
Quindi tutte le soluzioni della congruenza sono della forma $x=(a'^(-1))b'+nk ,k in ZZ$
In particolare vi sono esattamente $d$ soluzioni modulo $n$.
Fatto un po luce su questo, sapresti dirmi ora cosa hai sbagliato e correggere?
Poi pensiamo alla risoluzione del sistema.
grazie innanzitutto, vorrei chiederti solo una cosa, ieri in attesa di una vostra risposta ho provato a capirlo, e credo che qst volta sono riuscito a capire... però voglio esserne sicuro, io forse ho usato un metodo più semplice ma con qst metodo mi trovo bene XD... ti faccio vedere come ho risolto qst esercizio
{3x ≡ 15(mod21)
{89x ≡ 7 (mod11)
allora prima di tutto cerco di capire se 3x≡15(mod21)si può risolvere, quindi faccio MCD (a,b) ossia 3 e 21 = 3 , 3 divide 15 quindi è risolvibile e avremmo soluzioni..
poi applico d=h*a + k*n ....
ossia 3=h*3 + k*21
posso semplificare e mi diventa 1=h*1 + k*7
dò dei valori alla h k
h=6
k=-1
b=j*d ossia
15= j*3; j=5
prima soluzione x=5
fin qui va bene? ... io con qst modo mi trovo benissimo, spero che va bene
{3x ≡ 15(mod21)
{89x ≡ 7 (mod11)
allora prima di tutto cerco di capire se 3x≡15(mod21)si può risolvere, quindi faccio MCD (a,b) ossia 3 e 21 = 3 , 3 divide 15 quindi è risolvibile e avremmo soluzioni..
poi applico d=h*a + k*n ....
ossia 3=h*3 + k*21
posso semplificare e mi diventa 1=h*1 + k*7
dò dei valori alla h k
h=6
k=-1
b=j*d ossia
15= j*3; j=5
prima soluzione x=5
fin qui va bene? ... io con qst modo mi trovo benissimo, spero che va bene
scusatemi ho dimenticato le formule... sorry
Hai applicato Bezout, giusto?
comunque riscrivi bene con le formule, faccio fatica assai a leggere...
In realtà, Skipt, Bezout è uno strumento molto potente. $x=5$ va bene. ma ricorda che è una soluzione particolare.
L'insieme delle soluzioni della prima sono date da $x=5+7k , k in ZZ$
In realtà è un po dispendioso usare Bezout, ti toglie molto tempo, specialmente nella ricerca dei coefficienti.
Un'alternativa potresti vedere le singole congruenze come equazioni in $ZZ_n$
cioè del tipo
$[a][x]_n=_n (1)$ ti mando qui.
quindi per risolvere la (1) ti basta trovare un inverso aritmetico di a(modn).
Mi spiego
Prendiamo la congruenza $3x-=15(mod21)$
riduciamola e otteniamo che $x-=5(mod7)$ (ironia della sorte va già bene! , ho diviso tutto per il $()$)
Prendiamo quest'altra
$89x-=7(mod11)$
Prima di tutto notiamo che $[89]_11= [1]_11$ sei d'accordo?
quindi è equivalente a
$x-=7(mod11)$ <-- e anche qui non dobbiamo fare particolari stratagemmi (le soluzioni di quella sono del tipo $x=7+11k, k in ZZ$)
Infine abbiamo l'ultima,
$x-=7(mod15)$ <-- che è compatibile e ridotta in forma normale (e ha soluzioni $ x=7+15k'$)
Pertanto il sistema di partenza è equivalente a risolvere questo
$\(*){( x-=5(mod7)),(x-=7(mod11)),(x-=7(mod15)):}$ sei d'accordo con me?
Ora cosa possiamo dire sui moduli del sistema $(*)$? e sulle sue soluzioni? quale teorema ci viene in aiuto?
comunque riscrivi bene con le formule, faccio fatica assai a leggere...
In realtà, Skipt, Bezout è uno strumento molto potente. $x=5$ va bene. ma ricorda che è una soluzione particolare.
L'insieme delle soluzioni della prima sono date da $x=5+7k , k in ZZ$
In realtà è un po dispendioso usare Bezout, ti toglie molto tempo, specialmente nella ricerca dei coefficienti.
Un'alternativa potresti vedere le singole congruenze come equazioni in $ZZ_n$
cioè del tipo
$[a][x]_n=_n (1)$ ti mando qui.
quindi per risolvere la (1) ti basta trovare un inverso aritmetico di a(modn).
Mi spiego
Prendiamo la congruenza $3x-=15(mod21)$
riduciamola e otteniamo che $x-=5(mod7)$ (ironia della sorte va già bene! , ho diviso tutto per il $()$)
Prendiamo quest'altra
$89x-=7(mod11)$
Prima di tutto notiamo che $[89]_11= [1]_11$ sei d'accordo?
quindi è equivalente a
$x-=7(mod11)$ <-- e anche qui non dobbiamo fare particolari stratagemmi (le soluzioni di quella sono del tipo $x=7+11k, k in ZZ$)
Infine abbiamo l'ultima,
$x-=7(mod15)$ <-- che è compatibile e ridotta in forma normale (e ha soluzioni $ x=7+15k'$)
Pertanto il sistema di partenza è equivalente a risolvere questo
$\(*){( x-=5(mod7)),(x-=7(mod11)),(x-=7(mod15)):}$ sei d'accordo con me?
Ora cosa possiamo dire sui moduli del sistema $(*)$? e sulle sue soluzioni? quale teorema ci viene in aiuto?
Aspetta ma siiiii ora ho capitoooooo!! =) grazie mille davvero !!!! =D =D scusami per il disturbo che ho causato ..... GRAZIE MILLE ankora =D
buono allora 
qualunque cosa, se vuoi riscontri nella risoluzione del sistema, posta i tuoi calcoli qui, se hai dei dubbi
qualunque cosa, se vuoi riscontri nella risoluzione del sistema, posta i tuoi calcoli qui, se hai dei dubbi
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo