Sistema di congruenze a due equazioni

[giupar93]

salve ragazzi, ho questo sistema:

$ { ( x-=3(mod4) ),( x-=5(mod6) ):} $

risolvendo mi è venuto questo risultato

$x-=23(mod24)$

è corretto? GRazie mille !

[anaiss1]

A me viene $ x-= 11 (mod 12) $ Magari hai dimenticato una classe di congruenza perché hai moltiplicato 4 e 6 come se fossero coprimi? quando hai un sistema con moduli $ m $ e $ n $ la soluzione è una classe di congruenza in modulo del minimo comune multiplo cioè in modulo $ (m*n)/gcd (m, n) $

(In questo caso si può pensarla anche intuitivamente: se un numero è congruo a -1 a entrambi i numeri, la congruenza sarà la stessa anche col minimo comune multiplo)

[giupar93]

i vero.. non ricordavo la divisione.. ma oltre al modulo..il mio 23 è corretto? Se è no..potresti spiegarmi i passaggi?

[anaiss1]

"giupar93":i vero.. non ricordavo la divisione.. ma oltre al modulo..il mio 23 è corretto? Se è no..potresti spiegarmi i passaggi?

$ x-= 23 (mod12) $ è corretto anche se un po' strano:)

[giupar93]

ahahah l'importante che è corretto xD. ultimissima cosa così da non dover aprire topic nuovi.. come fai a vedere se il risultato di un sistema di congruenze è corretto oppure no ?

[anaiss1]

Io semplicemente controllo che il numero più piccolo della classe di congruenze trovata soddisfi le due congruenze... in questo caso è facile controllare che 11 (e 23) vanno bene, visto che 12 e 24 sono multipli sia di 4 che di 6 .

Posso chiederti che metodo usi per risolvere questi sistemi? (Forse non è il più semplice)

[giupar93]

diciamo che trasformo il sistema di congruenze, in questo caso, in:

$ { ( x1=3+4h ),( x1=5+6k ):} $

mi trovo h e k che in questo caso sono entrambi $-1$ e poi:

$ x1 = -1rarr x=-1+[[6,4]]/((6,4))k $
e da qui trovo che:

$x-=23(mod12)$

questo è quello che ho capito dalla spiegazione del prof xD

[anaiss1]

c'è un modo che secondo me è un po' più veloce: in pratica prima esprimi il massimo comun divisore come una combinazione lineare dei tuoi $ m $ e $ n $ :

$ gcd(m,n)=xn+ym $

poi divido tutto per il gcd in modo da avere numeri più piccoli e, soprattutto, coprimi:

$ 1=xtilde(n)+ytilde(m) $
(dove $ tilde(n)=n/gcd(m,n) $ e $ tilde(m)=m/gcd(m,n) $ )

Adesso sappiamo che: $ xtilde(n)-= 1(modtilde(m)) $ e viceversa $ ytilde(m)-= 1(modtilde(n)) $ (non mi dilungo a dimostrarlo ma pensandoci un attimo è intuitivo)
Quindi se vogliamo un numero $ z $ tale che
$ { ( z-=a(modn) ),(z-= b(modm) ):} $

Basta fare $ z=bxtilde(n)+aytilde(m) $

Ora sembra lungo ma ti assicuro che una volta trovati i tuoi $ x $ e $ y $ non ci metti nulla!