Sistemi di congruenze lineari
ciao a tutti!
Ho un problemino con questo semplice esercizio mai risolto in classe:
Si risolva il seguente sistema di congruenze lineari, riducendolo alla risoluzione di un equazione diofantea:
3x = 4 (mod5)
{ (dove = indica la congruenza)
2x = 3 (mod7)
Potreste darmi una traccia di soluzione da seguire?
La mia idea per ottenere l'equazione diofantea è stata quella di risovere la prima congruenza (-> x = 4+5k) per poi sostituire il risultato all'incognita x della seconda equazione (-> 4(4+5k) = 3 (7)) e trasformare quest'ultima in un eq diofantea in k,y (-> 20k-7y =-13). speravo così che le soluzioni di quest'ultima (-> k= 13+7h, y = 39+20h) interpretate come x=y+k mi dessero la soluzione del sistema...ma non è così...
Chissà che orrori che ho combinato!
Ringrazio in anticipo per l'aiuto!
Ho un problemino con questo semplice esercizio mai risolto in classe:
Si risolva il seguente sistema di congruenze lineari, riducendolo alla risoluzione di un equazione diofantea:
3x = 4 (mod5)
{ (dove = indica la congruenza)
2x = 3 (mod7)
Potreste darmi una traccia di soluzione da seguire?
La mia idea per ottenere l'equazione diofantea è stata quella di risovere la prima congruenza (-> x = 4+5k) per poi sostituire il risultato all'incognita x della seconda equazione (-> 4(4+5k) = 3 (7)) e trasformare quest'ultima in un eq diofantea in k,y (-> 20k-7y =-13). speravo così che le soluzioni di quest'ultima (-> k= 13+7h, y = 39+20h) interpretate come x=y+k mi dessero la soluzione del sistema...ma non è così...
Chissà che orrori che ho combinato!
Ringrazio in anticipo per l'aiuto!
Risposte
"sely":
3x = 4 (mod5)
La mia idea per ottenere l'equazione diofantea è stata quella di risovere la prima congruenza (-> x = 4+5k)
Ringrazio in anticipo per l'aiuto!
La tua equazione di partenza non è $x \equiv 4 (mod 5)$ ma $3x \equiv 4 (mod 5)$, per cui la tua soluzione non sarà $x \equiv 4 (mod 5)$ ma (a occhio) $x \equiv 3 (mod 5)$ ; prova ad andare avanti in modo simile in quella dopo (sostituendo i nuovi valori che ti vengono) e ricordando questa osservazione...
Perchè noto gli errori solamente dopo aver dato l'invio?!?
Hai ragione, ma ho sbagliato a copiare il testo! Ecco quello giusto:
$\{( 3x -= 2 (5)),(4x -= 3 (7)):}$
e quindi la soluzione x = 4+5k dovrebbe essere giusta per la prima equazione! il problema però rimane nell'intero esercizio...
Scusate la svista!
Scusa sely, ma non potresti risolvere separatamente ogni equazione e poi fare l'intersezione degli insiemi delle soluzioni?
Per la soluzione basta tenere presente che $3$ [risp. $4$] è invertibile modulo $5$ [risp. modulo $7$] e sporcarsi un po' le mani coi conti... (Almeno questo è quello che ho fatto io che, non essendo algebrista, non conosco metodi generali per la soluzione di questi problemini.)
Per la soluzione basta tenere presente che $3$ [risp. $4$] è invertibile modulo $5$ [risp. modulo $7$] e sporcarsi un po' le mani coi conti... (Almeno questo è quello che ho fatto io che, non essendo algebrista, non conosco metodi generali per la soluzione di questi problemini.)
Ok, riprendiamo ora la tua idea: sostituendo $x = 4 + 5k$ nella seconda equazione, hai che:
$16 + 20k \equiv 3 (mod 7)$ o, equivalentemente, che $6k \equiv 1 (mod 7)$ da cui la soluzione dovrebbe essere immediata,
ovvero $k \equiv 6 (mod 7)$, $rarr k = 6 + 7y$.
A questo punto sostituisci questo valore in $x = 4 + 5k$ e dovresti trovare la tua soluzione.
$16 + 20k \equiv 3 (mod 7)$ o, equivalentemente, che $6k \equiv 1 (mod 7)$ da cui la soluzione dovrebbe essere immediata,
ovvero $k \equiv 6 (mod 7)$, $rarr k = 6 + 7y$.
A questo punto sostituisci questo valore in $x = 4 + 5k$ e dovresti trovare la tua soluzione.
Io me l'ero sbrigata così: visto che $(4)^(-1)\equiv_7 2\equiv_5 (3)^(-1)$, troviamo:
$\{(4x\equiv_7 3),(3x\equiv_5 2):} => \{(x\equiv_7 6\equiv_7 -1),(x\equiv_5 4\equiv_5 -1):} => \{(x=-1+7k, ", con " k \in ZZ),(x=-1+5h, ", con "h\in ZZ):}$
affinché $-1+7k=-1+5h$ occorre e basta che $k$ sia multiplo di $5$ ed $h$ sia multiplo di $7$ (giacché $5$ e $7$ sono coprimi), quindi le soluzioni del tuo sistema sono tutti e soli i numeri del tipo:
$x=-1+35n, " con " n\in ZZ$.
$\{(4x\equiv_7 3),(3x\equiv_5 2):} => \{(x\equiv_7 6\equiv_7 -1),(x\equiv_5 4\equiv_5 -1):} => \{(x=-1+7k, ", con " k \in ZZ),(x=-1+5h, ", con "h\in ZZ):}$
affinché $-1+7k=-1+5h$ occorre e basta che $k$ sia multiplo di $5$ ed $h$ sia multiplo di $7$ (giacché $5$ e $7$ sono coprimi), quindi le soluzioni del tuo sistema sono tutti e soli i numeri del tipo:
$x=-1+35n, " con " n\in ZZ$.
grazie mille ad entrambi! problema risolto! e il confronto mi aiuta sempre a prendere dimestichezza con l'argomento!
Saluti!
Saluti!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo