Sistemi di congruenza
ho qualche problema con questo sistema:
{11*x-=6(mod 48),15*x-=10(mod 20),-5*x-=14(mod 28)
dunque la secoda congruenza la ho trasformata in x-=4(mod 10) ma per le altre ho difficoltà a trovare le inverse(che per altro è il mio grande problema)
aiutatemi please!
ciao ciao
{11*x-=6(mod 48),15*x-=10(mod 20),-5*x-=14(mod 28)
dunque la secoda congruenza la ho trasformata in x-=4(mod 10) ma per le altre ho difficoltà a trovare le inverse(che per altro è il mio grande problema)
aiutatemi please!
ciao ciao
Risposte
"lellina89":
ho qualche problema con questo sistema:
${(11*x-=6(mod 48)),(15*x-=10(mod 20)),(-5*x-=14(mod 28)):}
dunque la secoda congruenza la ho trasformata in $x-=4(mod 10)$ ma per le altre ho difficoltà a trovare le inverse(che per altro è il mio grande problema)
aiutatemi please!
ciao ciao
La seconda equazione, poiché $gcd(15,20)=5$ e $5|10$, si riduce a
$3x-=2(mod4)$ $rarr$ $-x-=2 (mod4) rarr x-=2 (mod4)$.
In generale, per trovare l'inverso moltiplicativo puoi usare l'algoritmo di Euclide esteso: http://www.matematicamente.it/forum/-vp216539.html#216539
nella prima l'inverso di 11 (mod48) è 35. infatti $35*11$=385$-=$1(mod48)!
nella terza l'inverso di -5 (mod28) è -17. infatti $(-5)*-(17)$=85$-=$1(mod28)!
nella terza l'inverso di -5 (mod28) è -17. infatti $(-5)*-(17)$=85$-=$1(mod28)!
"luca.barletta":
[quote="lellina89"]ho qualche problema con questo sistema:
${(11*x-=6(mod 48)),(15*x-=10(mod 20)),(-5*x-=14(mod 28)):}
dunque la secoda congruenza la ho trasformata in $x-=4(mod 10)$ ma per le altre ho difficoltà a trovare le inverse(che per altro è il mio grande problema)
aiutatemi please!
ciao ciao
La seconda equazione, poiché $gcd(15,20)=5$ e $5|10$, si riduce a
$3x-=2(mod4)$ $rarr$ $-x-=2 (mod4) rarr x-=2 (mod4)$.
In generale, per trovare l'inverso moltiplicativo puoi usare l'algoritmo di Euclide esteso: http://www.matematicamente.it/forum/-vp216539.html#216539[/quote]
però questo ti aiuta a calcolare gli inversi..e poi per trovare una soluzione comune a tutti e tre? come si fa?
"stefanosteve":
però questo ti aiuta a calcolare gli inversi..e poi per trovare una soluzione comune a tutti e tre? come si fa?
bisogna aggiustare opportunamente il set di equazioni per poter applicare il CRT.
cos'è il CRT? è forse il teorema cinese del resto?
"moxetto":
cos'è il CRT? è forse il teorema cinese del resto?
sì, Chinese Remainder Theorem
"luca.barletta":
[quote="stefanosteve"]però questo ti aiuta a calcolare gli inversi..e poi per trovare una soluzione comune a tutti e tre? come si fa?
bisogna aggiustare opportunamente il set di equazioni per poter applicare il CRT.[/quote]
Ok...io le ho semplificate in questo modo:
x≡18(mod48)
x≡2(mod4)
x≡14(mod28)
sono corrette?poi ho trovato una soluzione per le prime due, e mi è risultata 18mod48, e poi ho messo a sistema:
x≡18mod48
x≡14mod28
e da questa mi è risultata la soluzione 210mod336...è corretto il procedimento?
allora il sistema diventa
$\{(x-=18(mod48)),(x-=2(mod4)),(x-=14(mod28)):}$
divido per il MCD
$\{(x-=3(mod8)),(x-=1(mod2)),(x-=1(mod2)):}$
infatti avevo sbagliato a fare i conti (forse ora è corretto)
le ultime due eq. sono uguali quindi il sistema diventa
$\{(x-=3(mod8)),(x-=1(mod2)):}$
$\{(x-=18(mod48)),(x-=2(mod4)),(x-=14(mod28)):}$
divido per il MCD
$\{(x-=3(mod8)),(x-=1(mod2)),(x-=1(mod2)):}$
infatti avevo sbagliato a fare i conti (forse ora è corretto)
le ultime due eq. sono uguali quindi il sistema diventa
$\{(x-=3(mod8)),(x-=1(mod2)):}$
@ stefanosteve
se vuoi applicare il CRT ricordati che esso richiede che nelle equazioni ${a_i-=b_i (mod n_i)}_(i=1)^M$ sia $gcd(n_i,n_j)=1$ per ogni $i\ne j$.
In ogni caso, il procedimento che usi evitando di passare per il CRT va bene.
se vuoi applicare il CRT ricordati che esso richiede che nelle equazioni ${a_i-=b_i (mod n_i)}_(i=1)^M$ sia $gcd(n_i,n_j)=1$ per ogni $i\ne j$.
In ogni caso, il procedimento che usi evitando di passare per il CRT va bene.
"moxetto":
allora il sistema diventa
$\{(x-=30(mod48)),(x-=2(mod4)),(x-=14(mod28)):}$
la prima è $x-=18(mod48)$
"moxetto":
allora il sistema diventa
$\{(x-=30(mod48)),(x-=2(mod4)),(x-=14(mod28)):}$
divido per il MCD
$\{(x-=5(mod8)),(x-=1(mod2)),(x-=1(mod2)):}$
(sempre se non ho sbagliato i conti) le ultime due sono uguali, il sistema diventa
$\{(x-=5(mod8)),(x-=1(mod2)):}$
Sei sicuro della prima?io ho proceduto in questo modo:
$(11x-=6(mod48)) --> (11x-=198(mod48)) --> (x-=18(mod48))$ giusto?
"moxetto":
allora il sistema diventa
$\{(x-=30(mod48)),(x-=2(mod4)),(x-=18(mod28)):}$
divido per il MCD
$\{(x-=5(mod8)),(x-=1(mod2)),(x-=9(mod14)):}$
infatti avevo sbagliato a fare i conti (forse ora è corretto)
Sicuro?...la a me risulta cosi:
$\{(x-=18(mod48)),(x-=2(mod4)),(x-=14(mod28)):}$
e da qui semplifico ancora in:
$\{(x-=3(mod8)),(x-=1(mod2)),(x-=1(mod2)):}$
"luca.barletta":
@ stefanosteve
attenzione che il CRT richiede che nelle equazioni ${a_i-=b_i (mod n_i)}_(i=1)^M$ sia $gcd(n_i,n_j)=1$ per ogni $i\ne j$
è vero, hai ragione..ma per esempio nel sistema:
$\{(x-=3(mod8)),(x-=1(mod2)):}$
il gdc(8,2) = 2...quindi non puoi applicare il CRT? quindi come fai a risolverla?
"stefanosteve":
[quote="luca.barletta"]@ stefanosteve
attenzione che il CRT richiede che nelle equazioni ${a_i-=b_i (mod n_i)}_(i=1)^M$ sia $gcd(n_i,n_j)=1$ per ogni $i\ne j$
è vero, hai ragione..ma per esempio nel sistema:
$\{(x-=3(mod8)),(x-=1(mod2)):}$
il gdc(8,2) = 2...quindi non puoi applicare il CRT? quindi come fai a risolverla?[/quote]
avevo modificato il mio messaggio precedente.
però il MCD(8,2)=2$!=$1, quindi non si può applicare il CRT?! giusto? io lo risolverei per sostituzione!
scusa stefanosteve, avevo invertito i moduli e quindi avevo sbagliato tutto, poi ho coretto! è giusto come hai fatto tu....
"luca.barletta":
[quote="stefanosteve"][quote="luca.barletta"]@ stefanosteve
attenzione che il CRT richiede che nelle equazioni ${a_i-=b_i (mod n_i)}_(i=1)^M$ sia $gcd(n_i,n_j)=1$ per ogni $i\ne j$
è vero, hai ragione..ma per esempio nel sistema:
$\{(x-=3(mod8)),(x-=1(mod2)):}$
il gdc(8,2) = 2...quindi non puoi applicare il CRT? quindi come fai a risolverla?[/quote]
avevo modificato il mio messaggio precedente.[/quote]
Ok ho visto ora..quindi in questo caso risolvo in questo modo:
visto che gdc(8,2) divide 1-3 trovo un inverso di (8,2)
8=3*2 + 2 --> 2=8-3*2
1-3 = (-1)*(8,2)
1-3 = (-1)*(8-3*2)
1-3 = -8+3*2
1+8 = 3+3*2
-5 = -5
-5 è soluzione particolare e quelle totali sono:
-5+k[8,2] = -5+k8 cioè -5mod8 = 3mod8
quindi ora la soluzione è esatta...
@ stefanosteve
La tua soluzione precedente andava bene.
Innanzitutto si nota che la seconda equazione è ridondante, quindi basta risolvere, per sostituzione, il sistema tra la prima e la terza equazione. In definitiva $x-=210 (mod336)$
La tua soluzione precedente andava bene.
Innanzitutto si nota che la seconda equazione è ridondante, quindi basta risolvere, per sostituzione, il sistema tra la prima e la terza equazione. In definitiva $x-=210 (mod336)$
a me il risultato esce x$-=$3(mod8)
dato
$\{(x-=3(mod8)),(x-=1(mod2)):}$
ho fatto
x=1+2k
1+2k$-=$3(mod8)
2k$-=$2(mod8)
k$-=$1(mod4) k=1+4y
x=1+2k=1+2+8y=3+8y quindi x$-=$3(mod8)
$\{(x-=3(mod8)),(x-=1(mod2)):}$
ho fatto
x=1+2k
1+2k$-=$3(mod8)
2k$-=$2(mod8)
k$-=$1(mod4) k=1+4y
x=1+2k=1+2+8y=3+8y quindi x$-=$3(mod8)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo