Risoluzione equazione congruenziale
Buongiorno a tutti, mi trovo alle prese con il seguente esercizio:
"Determinare le soluzioni dell’equazione congruenziale
$ 171x≡20 (mod299) $.
Scrivere l’insieme delle soluzioni come elemento di $ Z_299 $ (anello delle classi resto modulo $ 300 $), scegliendo opportunamente il rappresentante tra $ 0 $ e $ 298 $, ed eseguire la verifica."
Ora, io ho proceduto in questo modo:
$ MCD(171, 299) = 1 $
Dunque l'equazione ammette soluzioni.
L'identità di Bezout mi dice che in questo caso $ 1 $ è esprimibile come combinazione lineare di $ 171 $ e $ 299 $. Ma come faccio a trovare $x $ e $ y$ tali che $ x171 + y299 = 1 $ ? Grazie in anticipo
[xdom="Seneca"]Sposto la discussione in Algebra, ché è la sezione più pertinente.[/xdom]
"Determinare le soluzioni dell’equazione congruenziale
$ 171x≡20 (mod299) $.
Scrivere l’insieme delle soluzioni come elemento di $ Z_299 $ (anello delle classi resto modulo $ 300 $), scegliendo opportunamente il rappresentante tra $ 0 $ e $ 298 $, ed eseguire la verifica."
Ora, io ho proceduto in questo modo:
$ MCD(171, 299) = 1 $
Dunque l'equazione ammette soluzioni.
L'identità di Bezout mi dice che in questo caso $ 1 $ è esprimibile come combinazione lineare di $ 171 $ e $ 299 $. Ma come faccio a trovare $x $ e $ y$ tali che $ x171 + y299 = 1 $ ? Grazie in anticipo
[xdom="Seneca"]Sposto la discussione in Algebra, ché è la sezione più pertinente.[/xdom]
Risposte
Una soluzione particolare è data da :
$x=140,y=-80$
Essa si ottiene, come è noto, con l'algoritmo di Euclide. La soluzione generale è:
$x=140+299n,y=-80-171n, n \in N$
La soluzione della congruenza iniziale è quindi: $x=140+299n=[140]_{299}$
La verifica è facile.
$x=140,y=-80$
Essa si ottiene, come è noto, con l'algoritmo di Euclide. La soluzione generale è:
$x=140+299n,y=-80-171n, n \in N$
La soluzione della congruenza iniziale è quindi: $x=140+299n=[140]_{299}$
La verifica è facile.
Ciao ciromario, grazie per la risposta! 
Ho applicato però l'algoritmo di Euclide (divisioni successive) ed ho:
$ 299 / 171 = 1 $ resto $ 128 $
$ 128 / 171 = 0 $ resto $ 128 $
Poi però mi blocco perché mi da sempre la stessa divisione...
Ho applicato però l'algoritmo di Euclide (divisioni successive) ed ho: $ 299 / 171 = 1 $ resto $ 128 $
$ 128 / 171 = 0 $ resto $ 128 $
Poi però mi blocco perché mi da sempre la stessa divisione...
ok allora ho fatto così:
$ 299 / 171 = 1 $ resto $ 128 $
$ 171 / 128 = 1 $ resto $ 43 $
$ 128 / 43 = 2 $ resto $ 42 $
$ 43 / 42 = 1 $ resto $ 1 $
$ 42 / 1 = 42 $ resto $ 0 $
Quindi devo ricavarmi $ x $ e $ y $ per cui $ x \cdot 299 + y \cdot 171 = 1 $
$ 1 = 43 - 1 \cdot 42 $
$ 1 = 43 - 1 \cdot (128 - 43 \cdot 2) $
Andando avanti così come faccio a ricavarmi i numeri che ha ottenuto ciromario?..
$ 299 / 171 = 1 $ resto $ 128 $
$ 171 / 128 = 1 $ resto $ 43 $
$ 128 / 43 = 2 $ resto $ 42 $
$ 43 / 42 = 1 $ resto $ 1 $
$ 42 / 1 = 42 $ resto $ 0 $
Quindi devo ricavarmi $ x $ e $ y $ per cui $ x \cdot 299 + y \cdot 171 = 1 $
$ 1 = 43 - 1 \cdot 42 $
$ 1 = 43 - 1 \cdot (128 - 43 \cdot 2) $
Andando avanti così come faccio a ricavarmi i numeri che ha ottenuto ciromario?..
Omh.. a me escono numeri diversi(scrivo il procedimento):
\(299 = 191 + 128\)
\(171 = 128 + 43\)
\(128 = 2 \cdot 43 + 42\)
\(43 = 42 + 1\)
ora per trovare le soluzioni si parte dall'ultima espressione e si va salendo sostituendo sempre il numero più piccolo, in modo tale da ottenere il massimo comun divisore come combinazione lineare dei valori iniziali:
\(1 = 43 - 42 = \) (sostituiamo \(42\) dalla penultima)
\(= 43 - (128 - 2 \cdot 43) = 3 \cdot 43 - 128 = \) (sostituamo \(43\))
\(= 3 \cdot (171 - 128) - 128 = 3 \cdot 171 - 4 \cdot 128= \) (sostituamo \(128\))
\(= 3 \cdot 171 - 4 \cdot (299 - 171) = 7 \cdot 171 - 4 \cdot 129\)
quindi i valori sono \(x_0 = 7\), \(y_0 = -4\), e il rappresentante di \(x\) è \(7\).
Prova a risolvere qualche altra equazione lineare da solo.
\(299 = 191 + 128\)
\(171 = 128 + 43\)
\(128 = 2 \cdot 43 + 42\)
\(43 = 42 + 1\)
ora per trovare le soluzioni si parte dall'ultima espressione e si va salendo sostituendo sempre il numero più piccolo, in modo tale da ottenere il massimo comun divisore come combinazione lineare dei valori iniziali:
\(1 = 43 - 42 = \) (sostituiamo \(42\) dalla penultima)
\(= 43 - (128 - 2 \cdot 43) = 3 \cdot 43 - 128 = \) (sostituamo \(43\))
\(= 3 \cdot (171 - 128) - 128 = 3 \cdot 171 - 4 \cdot 128= \) (sostituamo \(128\))
\(= 3 \cdot 171 - 4 \cdot (299 - 171) = 7 \cdot 171 - 4 \cdot 129\)
quindi i valori sono \(x_0 = 7\), \(y_0 = -4\), e il rappresentante di \(x\) è \(7\).
Prova a risolvere qualche altra equazione lineare da solo.
Ok, ci sono grazie mille! Adesso mi rimane da capire che cosa intende per "verifica"..
Ecco che esce la soluzione di ciromario, l'equazione era \(171 \cdot x \equiv 20 \mod 299\), noi abbiamo trovato che \(171 \cdot 7 \equiv 1 \mod 299\), dunque il valore cercato è \(7 \cdot 20 = 140\).
La verifica.. basta prendere la calcolatrice e vedere che \(299 \mid 171 \cdot 140 - 20\) (in particolare potrai notere che il risultato della divisione è \(80\)).
La verifica.. basta prendere la calcolatrice e vedere che \(299 \mid 171 \cdot 140 - 20\) (in particolare potrai notere che il risultato della divisione è \(80\)).
ciao, grazie della risposta, l'unica cosa che non mi è ancora chiara è la verifica 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo