Equazioni congruenziali

Cominciamo con la definizione.

Si dicono equazioni congruenziali le equazioni lineari in una incognita in Z_n.

Queste equazioni, tipicamente, vengono scritte in due modi

oppure

Per risolvere questo tipo di equazioni è molto utile conoscere il seguente teorema:

Teorema: Sia

una congruenza lineare modulo n. Allora la congruenza ammette soluzione se e solo se MCD(a,n) divide b.

In realtà il teorema è un po' più complesso, ma non voglio confonderti troppo.

Esempio:

Risolviamo la seguente equazione congruenziale:

MCD(16,5)=1, e 1 divide 6. Dunque l'equazione ammette soluzioni. Come trovarle? Dobbiamo cercare quel numero che sia l'inverso di 16 in Z₅, in modo da poter moltiplicare a destra e a sinistra per quel numero e ottenere x=qualcosa mod n.

L'esistenza di tale numero è garantita proprio dal fatto che MCD(16,5)=1 e per l'identità di Bezout, (te la racconto dopo), 1 è esprimibile come combinazione lineare di 16 e 5. Infatti possiamo scrivere

Cioè

che significa che

Quindi scrivere 16 è come scrivere 1, detta in modo rigoroso, abbiamo scoperto che in Z₅, 16 è l'inverso di se stesso, dunque moltiplicano entrambi i membri dell'equazione per 16 otteniamo

96 è 1 mod 5, quindi

Cioè x appartiene alla classe [1]₅ ovvero x={1,6,11,16,...}

Come puoi vedere l'argomento non è semplicissimo, in realtà la questione è prendere cofidenza con queste operazioni sulle classi di resto per riuscire a  trovare l'inverso.

Identità di Bézout: dati due numeri interi a e b, non entrambi nulli e tali che MCD(a,b)=d, allora esistono x e y tali che ax+by=d. Quindi nel nostro caso si ha

Spero di essere stato chiaro, se così non fosse chiedi pure!