Risoluzione equazioni congruenziali
Buonasera. Ho a che fare con due equazioni congruenziali da risolvere:
$ 9x-= 3mod(10) $
$ 7x-=amod(14) $
Considero la prima.
Ammette soluzioni poiché $ MCD(9,10) = 1 | 3 $. Ora devo trovare l'inverso aritmetico $ k $ di $ 9 $ in $ ZZ_10 $ e faccio
$ 9 = 1 + 10k $
mi viene
$ k = 4 / 5 $
e quindi l'equazione si dovrebbe ridurre a
$ x -= 4 / 5mod(10) $
ma la soluzione dovrebbe essere invece uguale a
$ x -= -3mod(10) $
Nella seconda
ammette soluzioni se $ 7 | a $; trovo l'inverso aritmetico $ k $ di $ 7 $ in $ZZ_14 $ ma ho che $ 7 = 7 + 14k $ (???) ecco che non mi trovo..
potreste darmi una mano?
$ 9x-= 3mod(10) $
$ 7x-=amod(14) $
Considero la prima.
Ammette soluzioni poiché $ MCD(9,10) = 1 | 3 $. Ora devo trovare l'inverso aritmetico $ k $ di $ 9 $ in $ ZZ_10 $ e faccio
$ 9 = 1 + 10k $
mi viene
$ k = 4 / 5 $
e quindi l'equazione si dovrebbe ridurre a
$ x -= 4 / 5mod(10) $
ma la soluzione dovrebbe essere invece uguale a
$ x -= -3mod(10) $
Nella seconda
ammette soluzioni se $ 7 | a $; trovo l'inverso aritmetico $ k $ di $ 7 $ in $ZZ_14 $ ma ho che $ 7 = 7 + 14k $ (???) ecco che non mi trovo..
potreste darmi una mano?
Risposte
$9x-=3(10)$
La condizione di risolubilità è soddisfatta, infatti $(9, 10)=1 |3$
Inoltre $(9,10)=1$ implica che $9$ è invertibile in $ZZ$ $/$ $10ZZ$
$=>$ per risolvere $9x-=3(10)$ basta trovare l'inverso moltiplicativo di $9$ in $ZZ$ $/$ $10ZZ$
Trovare l'inverso moltiplicativo di $9$ in $ZZ$ $/$ $10ZZ$ significa risolvere: $9y-=1(10)$
$9*9=81-=1(10)$ $=>$ $y =9^(-1) =9 (10)$
Adesso riprendiamo $9x-=3(10)$ e moltiplichiamo per $9$ entrambi i membri
otteniamo $x-=27(10)$ $=>$ $x-=-3(10)$ che è la nostra soluzione
$7x-=a(14)$
La condizione di risolubilità è $(7,14)=7|a$ $=>$ $a$ è della forma $7b$
Con questa sostituzione otteniamo: $7x-=7b(14)$ $=>$ $x-=b(2)$ che è la nostra soluzione
P.S. Dividere per $5$ significa moltiplicare per l'inverso moltiplicativo di $5$ (ovvero $5^(-1)$)
In $ZZ$ $/$ $10ZZ$, $5$ non è invertibile in quanto $(5,10) != 1$, quindi, visto che non esiste un tale $5^(-1)$ non esisterà un tale $k=4*5^-1$. Il che è perfettamente normale visto che stavi cercando di risolvere $9 =1 +10k$ che è solo un altro modo di scrivere $9-=1(10)$, e ovviamente $9$ non è mai congruo a $1$ modulo $10$
La condizione di risolubilità è soddisfatta, infatti $(9, 10)=1 |3$
Inoltre $(9,10)=1$ implica che $9$ è invertibile in $ZZ$ $/$ $10ZZ$
$=>$ per risolvere $9x-=3(10)$ basta trovare l'inverso moltiplicativo di $9$ in $ZZ$ $/$ $10ZZ$
Trovare l'inverso moltiplicativo di $9$ in $ZZ$ $/$ $10ZZ$ significa risolvere: $9y-=1(10)$
$9*9=81-=1(10)$ $=>$ $y =9^(-1) =9 (10)$
Adesso riprendiamo $9x-=3(10)$ e moltiplichiamo per $9$ entrambi i membri
otteniamo $x-=27(10)$ $=>$ $x-=-3(10)$ che è la nostra soluzione
$7x-=a(14)$
La condizione di risolubilità è $(7,14)=7|a$ $=>$ $a$ è della forma $7b$
Con questa sostituzione otteniamo: $7x-=7b(14)$ $=>$ $x-=b(2)$ che è la nostra soluzione
P.S. Dividere per $5$ significa moltiplicare per l'inverso moltiplicativo di $5$ (ovvero $5^(-1)$)
In $ZZ$ $/$ $10ZZ$, $5$ non è invertibile in quanto $(5,10) != 1$, quindi, visto che non esiste un tale $5^(-1)$ non esisterà un tale $k=4*5^-1$. Il che è perfettamente normale visto che stavi cercando di risolvere $9 =1 +10k$ che è solo un altro modo di scrivere $9-=1(10)$, e ovviamente $9$ non è mai congruo a $1$ modulo $10$
grazie mille della risposta SaraSue. Volevo chiarire alcuni punti:
- $ 9 $ è invertibile in $ZZ$ $/$ $10ZZ$ perché è coprimo con $ 10 $, giusto?
- mi puoi spiegare questo passaggio: $ x -= 27(10) => x -= -3(10) $ ?
- $ 9 $ è invertibile in $ZZ$ $/$ $10ZZ$ perché è coprimo con $ 10 $, giusto?
- mi puoi spiegare questo passaggio: $ x -= 27(10) => x -= -3(10) $ ?
"jigen45":
- $ 9 $ è invertibile in $ ZZ $ $ / $ $ 10ZZ $ perché è coprimo con $ 10 $, giusto?
Esatto infatti $(9, 10)=1$ significa che $9$ e $10$ sono coprimi
"jigen45":
- mi puoi spiegare questo passaggio: $ x -= 27(10) => x -= -3(10) $ ?
$ x -= 27(10)$ si puo' riscrivere come $x=27 +10k$ per $k in ZZ$.
Adesso, se prendiamo $k=-3$ otteniamo $ x= 27 + 10*(-3)=27-30=-3$ (il modulo rimane lo stesso).
la scelta $ k = -3 $ non è arbitraria, giusto?
ah ok, ho capito, grazie
Un altro modo di vederla è $27 in [-3]_10$ ($27$ appartiene alla classe di congruenza di $3$ modulo $10$)
in quanto $[3]_10 = {-3, 7, 17, 27, 37, ...}$
formalmente: $[x]_10 = {x +10k | k in ZZ}$
quindi: $[-3]_10 = {-3 +10k | k in ZZ}$
In altre parole la classe di congruenza $[x]_10$ ha infiniti rappresentanti in $ZZ$, noi scegliamo quello che ci fa più comodo. (Generalmente si usano i resti della divisione euclidea)
in quanto $[3]_10 = {-3, 7, 17, 27, 37, ...}$
formalmente: $[x]_10 = {x +10k | k in ZZ}$
quindi: $[-3]_10 = {-3 +10k | k in ZZ}$
In altre parole la classe di congruenza $[x]_10$ ha infiniti rappresentanti in $ZZ$, noi scegliamo quello che ci fa più comodo. (Generalmente si usano i resti della divisione euclidea)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo