Dubbi sistemi di congruenze lineari
Ciao a tutti, ho alcuni dubbi in merito alla riduzione di sistemi di congruenze lineari e alla loro risoluzione.
Ad esempio per questo sistema:
3x ≡ 12 (mod 9)
7x ≡ 2 (mod 6)
30x ≡ 24 (mod 12)
ho capito che vi sono vari metodi di riduzione, infatti per quanto riguarda la prima possiamo dividere tutto per 3 che è l'mcd; la seconda ha soluzione "immediata" che è 2 perchè 14/6 dà resto 2 (o almeno credo si possa fare così).
Per quanto riguarda la terza dopo aver diviso per 6 aver ottenuto 5x ≡ 4 (mod 2) non so come procedere.
Inoltre vorrei capire se la soluzione mediante identità di bezout si può applicare quando il mcd è 1 oppure sempre, grazie.
Ad esempio per questo sistema:
3x ≡ 12 (mod 9)
7x ≡ 2 (mod 6)
30x ≡ 24 (mod 12)
ho capito che vi sono vari metodi di riduzione, infatti per quanto riguarda la prima possiamo dividere tutto per 3 che è l'mcd; la seconda ha soluzione "immediata" che è 2 perchè 14/6 dà resto 2 (o almeno credo si possa fare così).
Per quanto riguarda la terza dopo aver diviso per 6 aver ottenuto 5x ≡ 4 (mod 2) non so come procedere.
Inoltre vorrei capire se la soluzione mediante identità di bezout si può applicare quando il mcd è 1 oppure sempre, grazie.
Risposte
Potrei fare così...
5 ≡ 1 (mod 2) , mentre 4 ≡ 0 (mod 2) , per cui l'ultima congruenza diventa:
x ≡ 0 (mod 2)
è corretto? Grazie.
5 ≡ 1 (mod 2) , mentre 4 ≡ 0 (mod 2) , per cui l'ultima congruenza diventa:
x ≡ 0 (mod 2)
è corretto? Grazie.
conosci il teorema cinese dei resti?
Si lo conosco, ero più interessato alla riduzione.
Nel momento che una congruenza algebrica [tex]ax \equiv b_{(mod n)}[/tex] ammette soluzione se e solo se [tex](a,n)=1[/tex] oppure se e solo se
[tex]d:=MCD(a,n)|b[/tex], a quel punto puoi fare le riduzioni che vuoi.
[tex]d:=MCD(a,n)|b[/tex], a quel punto puoi fare le riduzioni che vuoi.
Si questo lo so, ma non riesco a capire bene quale metodo sia meglio applicare.
Infatti alcune volte mi trovo di fronte a congruenze che non riesco a ridurre...ad esempio:
3x ≡ 5 (mod 4)
o
2x ≡ 3 (mod 11)
Infatti alcune volte mi trovo di fronte a congruenze che non riesco a ridurre...ad esempio:
3x ≡ 5 (mod 4)
o
2x ≡ 3 (mod 11)
Direi che non c'è nulla da ridurre... [tex](3,4)=1[/tex] e [tex](2,11)=1[/tex] quindi vanno bene come sono.
Ma per usare il TCR non devo eliminare i coefficienti della x ?
Basta calcolare l'inverso moltiplicativo sulla prima congruenza, da cui poi calcoli la [tex]x[/tex] che successivamente ti "riporti" sulla congruenza successiva, e così via...
Sulla prima quale ?
Per quanto riguarda le ultime due congruenze che ho scritto, invece, mi riferisco a questo sistema:
2x ≡ 1 (mod 3)
3x ≡ 5 (mod 4)
22x ≡ 33 (mod 121)
che diventa
x ≡ -1 (mod 3)
3x ≡ 5 (mod 4)
2x ≡ 3 (mod 11)
Arrivato qui non riesco a continuare..
Per quanto riguarda le ultime due congruenze che ho scritto, invece, mi riferisco a questo sistema:
2x ≡ 1 (mod 3)
3x ≡ 5 (mod 4)
22x ≡ 33 (mod 121)
che diventa
x ≡ -1 (mod 3)
3x ≡ 5 (mod 4)
2x ≡ 3 (mod 11)
Arrivato qui non riesco a continuare..
Dalla prima hai che [tex]2x \equiv 1_{(mod 3)}[/tex], "diventa" [tex]x \equiv 2_{(mod 3)}[/tex] da cui [tex]x=2+3k, k \in \mathbb{Z}[/tex], che sostiuita nella seconda...
Se io utilizzo nella prima congruenza l'identità di bezout come metodo per la riduzione ottengo -1 come valore della Xo (come in un esempio che ho sui miei appunti) e quindi x ≡ -1 (mod 3) anzichè x ≡ 2 (mod 3) come tu mi hai suggerito e mi sembra anche corretto...dove sbaglio?
Non sbagli: [tex]x \equiv -1_{(mod 3)} \equiv 2_{(mod 3)}[/tex].
Immagino tu sappia perché....
Immagino tu sappia perché....
Perchè sia -1 che 2 in mod 3 fanno parte della classe [2] ?
Si.
Ok, ora come prosegui con l'esercizio?
Ok, ora come prosegui con l'esercizio?
Suppongo con le sostituzioni..
Si, sino ad arrivare alla soluzione cercata.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo