Step 0: Breve introduzione

Una congruenza lineare ha forma:

$$ a\equiv b \ (\text{mod } m) $$

(Si legge “$a$ congruo $b$ modulo $m$”)

Negli esercizi ci verrà chiesto di trovare l’incognita $x$ tale da soddisfare la congruenza:

$$ ax\equiv b \ (\text{mod } m) $$

• $a$ è il coefficiente di $x$
• $b$ è il termine noto
• $m$ è il modulo
• $x$ è l’incognita che cerchiamo

Per non trovare difficoltà in questo esercizi è necessario aver compreso il concetto di:

1. come trovare gli elementi invertibili in $\Z/n\Z$
2. come trovare l’elemento inverso di un invertibile in $\Z/n\Z$

(Esercizi disponibili al *Foglio 3 Esercizio 2 e* Foglio 4 Esercizio 2)

Step 1: Test di risolubilità

Non tutte le congruenze hanno soluzione. Per saperlo, dobbiamo calcolare il Massimo Comun Divisore (MCD) tra $a$ e $n$. Chiamiamolo $d$.

$$ d=MCD(a,m) $$

Se $d$ divide $b$ allora la congruenza lineare ammette esattamente $d$ soluzioni distinte in modulo $n$.