Risoluzione di congruenze lineari

[savio789]

Salve a tutti, sono nuovo del forum, sto studiando le congruenze lineari e adesso conosco abbastanza bene la teoria, ma il passo successivo consiste nel fare gli esercizi.
In ogni forum ho trovato un metodo diverso e spiegazioni diverse per la loro risoluzione, con il risultato che sono soltanto confuson e di fatto non so quale è il metodo classico, giusto e generale per risolverle.

Qualcuno saprebbe indicarmi il metodo classico per risolvere una congruenza lineare? Ad esempio la seguente: 3x = 10 (mod 9)

Grazie, ciao

[hyoukarou]

Speravo ti rispondesse qualcuno più ferrato di me ma dato che mi trovo.. benvenuto al forum

Non credo esista un "metodo classico", ma credo esistano delle strade equivalenti di procedere.

Diciamo che hai una congruenza del tipo \(ax \equiv b \mod t\), allora hai che \(x \equiv b \cdot a^{-1} \mod t\) dove \(a^{-1}\) è l'inverso moltiplicativo di \(a\) modulo \(t\) (per inverso moltiplicativo intendo quel numero, diciamo \(c\) tale che \(ac = 1 \mod t\)).
Una strada alternativa potrebbe essere quella di ricorrere alle equazioni diofantee, infatti all'equazione precedente si può associare un'equazione diofantea lineare del tipo \(ax + ht = b\) e poi si può prendere una dei possibili valori di \(x\) come rappresentante.

L'equazione che hai messo tu purtroppo non ha soluzioni: \(3\) non ha inverso moltiplicativo modulo \(9\) e se scriviamo l'equazione diofantea lineare \(3x + 9y = 10\) per l'identità di Bézout essa non ha soluzioni
Warning. Il fatto che \(3\) non abbia inverso moltiplicativo non implica necessariamente che l'equazione non abbia soluzioni, lo possiamo asserire soltanto notando che \(10\) non è divisibile per 3.

Esempio:
\(3x \equiv 2 \mod 5\), l'inverso moltiplicativo di \(3\) modulo \(5\) è \(2\) (infatti \(3 \cdot 2 = 6 \equiv 1 \mod 5\)), pertanto \(x \equiv 2 \cdot 2 \equiv 4 \mod 5\).

Scrivendo l'equazione diofantea \(3x + 5y = 2\) e usando l'algoritmo euclideo si trova che \(3(-1) + 5(1) = 2\) quindi \(x \equiv -1 \equiv 4 \mod 5\), abbiamo trovato lo stesso risultato di prima seguendo un procedimento diverso.

Se googli trovi molta roba a riguardo, alcune cose fatte meglio altre peggio(tipo i link di wikipedia che ho messo prima sono davvero pessimi ma perdonerai la mia pigrizia )

P.S. una cosa che dicono sempre ai nuovi arrivati e di usare LaTeX per scrivere formule matematiche nel forum, è un buon consiglio e perderai al massimo 10 minuti per sperimentare un po'

[savio789]

Non so perchè ma mi sono perso di nuovo...
Io queste cose le ho lasciate anni fà, ma ora mi servono per un concorso e per eventuali lavori.
Potresti rispiegarmi dettagliatamente i seguenti passaggi:

Esempio:
3x≡2mod5, l'inverso moltiplicativo di 3 modulo 5 è 2 (infatti 3⋅2=6≡1mod5), pertanto x≡2⋅2≡4mod5.

MCD(3, 5) = 1, 1| 2 e 5 è numero primo, ok? Quindi l'equazione possiede un'unica soluzione, e poi?

L'equazione diofantea associata è 3x + 5y = 2 con soluzione (-1, 1) e fin qui ci sono. Potresti spiegarmi i seguenti passaggi:

x≡−1≡4mod5

Scusami l'ignoranza ma ne ho bisogno...

[hyoukarou]

"savio789":Non so perchè ma mi sono perso di nuovo...
Io queste cose le ho lasciate anni fà, ma ora mi servono per un concorso e per eventuali lavori.
Potresti rispiegarmi dettagliatamente..

Scusa se sono stato frettoloso la scorsa volta, comincio elencandoti i risultati più importanti(che ti invito a dimostrare se non lo hai già fatto):

[*:irmdsot1]Def: Se \(a \neq 0\) e \(b\) sono due interi si dice che \(a\) divide \(b\) se esiste \(c \in \mathbb{Z}\) tale che \(b = ac\). Il simbolo \(a \mid b\) si legge "a divide b".
\(\)[/*:m:irmdsot1]
[*:irmdsot1] Se \(a \mid b\) e \(b \mid c\) allora \(a \mid c\)[/*:m:irmdsot1]
[*:irmdsot1] Se \(a \mid b\) e \(a \mid c\) allora \(a \mid (b \pm c)\)[/*:m:irmdsot1]
[*:irmdsot1] Se \(a \mid b\) allora \(a \mid bx\) per ogni \(x \in \mathbb{Z}\)[/*:m:irmdsot1]
[*:irmdsot1] Se \(a \mid b\) e \(a \mid c\) allora \(a \mid (bx \pm cy)\) per ogni \(x \in \mathbb{Z}\), \(y \in \mathbb{Z}\)
\(\)[/*:m:irmdsot1]
[*:irmdsot1]Def: L'intero \(c\) si dice massimo comun divisore di \(a\) e \(b\) se \(c\) è un divisore di \(a\) e di \(b\) e se inoltre ogni divisore di \(a\) e di \(b\) è un divisore di \(c\). Il massimo comun divisore di \(a\) e di \(b\) viene indicato con \((a, b)\).[/*:m:irmdsot1]
[*:irmdsot1]Def: due interi \(a\) e \(b\) si dicono relativamente primi se \((a, b) = 1\).[/*:m:irmdsot1]
[*:irmdsot1]Def: un numero \(p > 1\) si dice primo se i suoi soli divisori sono \(\pm 1\) e \(\pm p\).
\(\)[/*:m:irmdsot1]
[*:irmdsot1]Se \(a\) e \(b\) sono interi, non entrambi \(0\), allora \((a, b)\) esiste. Si possono trovare inoltre due interi \(m_0\) e \(n_0\) tali che \((a, b) = m_0 a + n_0 b\).[/*:m:irmdsot1]
[*:irmdsot1]Cor: se \(a\) e \(b\) sono relativamente primi, si possono trovare due interi \(m\) ed \(n\) tali che \(ma + nb = 1\)(identità di Bézout).[/*:m:irmdsot1]
[*:irmdsot1] Se \(a\) è relativamente primo con \(b\) e \(a \mid bc\) allora \(a \mid c\).
\(\)[/*:m:irmdsot1]
[*:irmdsot1]Def: \(a \equiv b \mod n\)(letto "a congruo b modulo n") se e soltanto se \(n \mid (a - b)\).
\(\)[/*:m:irmdsot1]
[*:irmdsot1] La relazione \(\equiv\) è una relazione di equivalenza.[/*:m:irmdsot1]
[*:irmdsot1] Questa relazione di equivalenza ha \(n\) distinte classi di equivalenza.[/*:m:irmdsot1]
[*:irmdsot1] Se \(a \equiv b \mod n\) e \(c \equiv d \mod n\) allora si ha che \(a + b \equiv c + d \mod n\) e che \(ab \equiv cd \mod n\).[/*:m:irmdsot1]
[*:irmdsot1] Se \(ab \equiv ac \mod n\) e \((a, n) = 1\) allora \(b \equiv c \mod n\).[/*:m:irmdsot1]
[*:irmdsot1] La somma e il prodotto modulo \(n\) godono delle usuali leggi commutative, associative, distributive, inoltre esiste uno zero per la somma e un'unità per il prodotto.[/*:m:irmdsot1]
[*:irmdsot1] Per ogni \(a \neq 0\) esiste \(b\) tale che \(ab \equiv 1 \mod p\), \(p\) primo.[/*:m:irmdsot1]
[*:irmdsot1] Per ogni \(a \neq 0\), \((a, n) = 1\) esiste un \(b\) tale che \(ab = 1 \mod n\).[/*:m:irmdsot1][/list:u:irmdsot1]

Detto ciò


"savio789":



Esempio:
3x≡2mod5, l'inverso moltiplicativo di 3 modulo 5 è 2 (infatti 3⋅2=6≡1mod5), pertanto x≡2⋅2≡4mod5.



MCD(3, 5) = 1, 1| 2 e 5 è numero primo, ok? Quindi l'equazione possiede un'unica soluzione, e poi?



torniamo a quest'esempio, \(3x \equiv 2 \mod 5\).

Per il penultimo punto sappiamo che esiste un elemento \(b\) tale che \(b * 3 \equiv 1 \mod 5\).
Andando a tentativi \(0\) e \(1\) non possono essere di sicuro, \(2 * 3 \equiv 6 \equiv 1 \mod 5\), abbiamo appena trovato che l'inverso di \(3\) è \(2\).

Ora per un'altra proprietà che abbiamo già visto sui moduli, \(2 * (3x) \equiv 2(2) \mod 5\), per la legge associativa \((2*3) x \equiv 4 \mod 5\) ma sappiamo che \(6 \equiv 1 \mod 5\), percui rimane \(x \equiv 4 \mod 5\)(è la soluzione).

(ovviamente come avrai già notato \(x \equiv 4 \mod 5\) significa che \(x\) può assumere i valori interi \(-6\), \(-1\), \(4\), \(9\), \(14\) e così via, per questo l'artimetica modulare è detta dell'orologio)



"savio789":
L'equazione diofantea associata è 3x + 5y = 2 con soluzione (-1, 1) e fin qui ci sono. Potresti spiegarmi i seguenti passaggi:



x≡−1≡4mod5



Questo era un altro metodo per trovare la soluzione, \(3x \equiv 2 \mod 5\) se e soltanto se \(5 \mid (3x - 2\) ovvero esiste un \(y \in \mathbb{Z}\) tale che \(3x - 2 = 5y\) ovvero \(3x + 5(-y) = 2\).
Usando l'algoritmo euclideo o qualsiasi metodo tu voglia puoi trovare una soluzione, avevamo visto per appunto \((-1, -1)\)(qua ho cambiato il segno di \(y\) ma è la stessa cosa).

Piccola digressione:
Diciamo che hai un'equazione diofantea lineare del tipo \(ax + by = c\) e conosci una soluzione, \((x_0, y_0)\).
Si può notare facilmente che \(a (bt) + b(-at) = 0\)(si chiama equazione omogenea), si dimostra banalmente che le infinite soluzioni della diofantea lineare sono della forma \((x, y) = (x_0 + bt, y_0 - at)\).

Quindi riprendendo da dov'eravamo rimasti, conosciamo una soluzione della nostra diofantea, \((-1, -1)\) quindi abbiamo che \(x = -1 + 5t\), ovvero \(x \equiv -1 \equiv 4 \mod 5\).