Come risolvere congruenze lineari
Ciao ragazzi,
vorrei chiedervi un chiarimento sulla risoluzione delle congruenze lineari.
Sostanzialmente, ho capito che si possono risolvere in due modi, cioè
svolgendo l'equazione diofantea associata oppure trovare l'inverso aritmetico.
E fin qui ci siamo, però a volte mi ritrovo delle congruenze in cui non riesco
a trovare l'inverso aritmetico e devo svolgere l'equazione diofantea.
Ad esempio, delle seguenti congruenze lineari non riesco a trovare l'inverso aritmetico
(ma che riesco a svolgere con la diofantea):
$7x -= 2 (mod 4)$
$12x -= 9 (mod 75)$
Invece di queste altre congruenze riesco a trovare l'inverso aritmetico...
$2x -= 4 (mod 5)$
$3x -= 3 (mod 5)$
Gentilmente, potete spiegarmi da cosa dipende il fatto che esista l'inverso aritmetico?
E come riesco a capire quale dei due metodi devo applicare?
Vi ringrazio in anticipo,
A presto.
vorrei chiedervi un chiarimento sulla risoluzione delle congruenze lineari.
Sostanzialmente, ho capito che si possono risolvere in due modi, cioè
svolgendo l'equazione diofantea associata oppure trovare l'inverso aritmetico.
E fin qui ci siamo, però a volte mi ritrovo delle congruenze in cui non riesco
a trovare l'inverso aritmetico e devo svolgere l'equazione diofantea.
Ad esempio, delle seguenti congruenze lineari non riesco a trovare l'inverso aritmetico
(ma che riesco a svolgere con la diofantea):
$7x -= 2 (mod 4)$
$12x -= 9 (mod 75)$
Invece di queste altre congruenze riesco a trovare l'inverso aritmetico...
$2x -= 4 (mod 5)$
$3x -= 3 (mod 5)$
Gentilmente, potete spiegarmi da cosa dipende il fatto che esista l'inverso aritmetico?
E come riesco a capire quale dei due metodi devo applicare?
Vi ringrazio in anticipo,
A presto.
Risposte
Perché nella prima non trovi l'inverso aritmetico? Dovrebbe essere $3$, infatti $$7\cdot 3 \equiv 1 \pmod{4}$$
Comunque per semplificarti la vita ricordati di lavorare con numeri più piccoli possibile, per esempio (sempre nella prima) scrivendo $3$ al posto di $7$, perché sono equivalenti modulo $4$.
Comunque l'inverso di $a$ modulo $b$ esiste se e solo se $a$ e $b$ sono primi fra loro. Ecco perché non riesci a trovare l'inverso di $12$ modulo $75$: hanno in comune un fattore $3$.
Ma in quel caso puoi dividere tutto per $3$, ottenendo: $$4x\equiv 3\pmod{25}$$
e adesso puoi trovare l'inverso di $4$ modulo $25$ (sono primi tra loro).
Comunque per semplificarti la vita ricordati di lavorare con numeri più piccoli possibile, per esempio (sempre nella prima) scrivendo $3$ al posto di $7$, perché sono equivalenti modulo $4$.
Comunque l'inverso di $a$ modulo $b$ esiste se e solo se $a$ e $b$ sono primi fra loro. Ecco perché non riesci a trovare l'inverso di $12$ modulo $75$: hanno in comune un fattore $3$.
Ma in quel caso puoi dividere tutto per $3$, ottenendo: $$4x\equiv 3\pmod{25}$$
e adesso puoi trovare l'inverso di $4$ modulo $25$ (sono primi tra loro).
Ciao milizia,
sinceramente non mi spiego perchè l'inverso dovrebbe essere 3.
Mi spiegheresti il procedimento che hai utilizzato?
Un ulteriore domanda, è possibile svolgere le congruenze lineari su wolfram alpha?
Ricordo di aver visto un modo, ma non ricordo più.
sinceramente non mi spiego perchè l'inverso dovrebbe essere 3.
Mi spiegheresti il procedimento che hai utilizzato?
Un ulteriore domanda, è possibile svolgere le congruenze lineari su wolfram alpha?
Ricordo di aver visto un modo, ma non ricordo più.
è l'inverso perche 7 per 3 è congruo ad 1 modulo 4, cosi come lo sono tutti i numeri della forma 4k+3.
immagino che non abbia usato un metodo per trovare l'inverso, normalmente quando il modulo è piccolo si va a tentativi dato che ne puoi fare al piu m-1, se vuoi un metodo fai la diofnatea.
Se il modulo non è coprimo con l'elemento da invertire non è possibile trovare l'inverso naturalmente, lo puoi mostrare con la diofantea.
immagino che non abbia usato un metodo per trovare l'inverso, normalmente quando il modulo è piccolo si va a tentativi dato che ne puoi fare al piu m-1, se vuoi un metodo fai la diofnatea.
Se il modulo non è coprimo con l'elemento da invertire non è possibile trovare l'inverso naturalmente, lo puoi mostrare con la diofantea.
"wall98":
è l'inverso perche 7 per 3 è congruo ad 1 modulo 4, cosi come lo sono tutti i numeri della forma 4k+3.
immagino che non abbia usato un metodo per trovare l'inverso, normalmente quando il modulo è piccolo si va a tentativi dato che ne puoi fare al piu m-1, se vuoi un metodo fai la diofnatea.
Se il modulo non è coprimo con l'elemento da invertire non è possibile trovare l'inverso naturalmente, lo puoi mostrare con la diofantea.
Giusto, ora mi è chiaro. Ti ringrazio
"milizia96":
Perché nella prima non trovi l'inverso aritmetico? Dovrebbe essere $ 3 $, infatti \[ 7\cdot 3 \equiv 1 \pmod{4} \]
Comunque per semplificarti la vita ricordati di lavorare con numeri più piccoli possibile, per esempio (sempre nella prima) scrivendo $ 3 $ al posto di $ 7 $, perché sono equivalenti modulo $ 4 $.
Comunque l'inverso di $ a $ modulo $ b $ esiste se e solo se $ a $ e $ b $ sono primi fra loro. Ecco perché non riesci a trovare l'inverso di $ 12 $ modulo $ 75 $: hanno in comune un fattore $ 3 $.
Ma in quel caso puoi dividere tutto per $ 3 $, ottenendo: \[ 4x\equiv 3\pmod{25} \]
e adesso puoi trovare l'inverso di $ 4 $ modulo $ 25 $ (sono primi tra loro).
Quindi l'inverso dovrebbe essere 7?
Io ho trovato questa soluzione:
\[x\equiv 7\pmod{25} \]
È corretta?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo