La congruenza lineare
Cos'è una congruenza lineare
Una congruenza lineare nell'incognita x è un'equazione $$ ax≡b \mod n $$
Dove a e b sono due numeri interi (a,b∈Z) e n è un numero naturale (n∈N).
A cosa servono le congruenze lineari?
Sono particolamente utili perché mi permettono di trovare le soluzioni di un'equazione lineare tramite le congruenze.
Nota. Ogni congruenza lineare nella forma $$ ax≡b \mod n $$ equivale a un'equazione lineare $$ ax+ny=b $$
Un esempio pratico
Questa congruenza modulo 3
$$ 4x ≡ 7 \mod 3 $$
equivale all'equazione lineare
$$ 4x+3y = 7 $$
L'equazione può ammettere o meno soluzioni intere nelle incognite x,y.
Al momento ancora non lo so
Le soluzioni intere della congruenza lineare
L'esistenza delle soluzioni intere
Una congruenza lineare ax≡b (mod n) ammette una o più soluzioni intere se il massimo comune divisore MCD(a,n) è un divisore di b. $$ (a,n)|b $$
Se MCD(a,n) divide b la congruenza lineare è detta congruenza compatibile.
Un esempio pratico
Riprendo la congruenza lineare precedente
$$ 4x ≡ 7 \mod 3 $$
Il massimo comune divisore di (a,n) è 1
$$ (4,3) = 1 $$
Il numero 1 è anche un divisore di b=7
$$ 1|7 $$
Pertanto, la congruenza lineare ammette soluzioni intere.
Ad esempio x=1.
$$ 4x ≡ 7 \mod 3 \\ 4(1) ≡ 7 \mod 3 \\ 4 ≡ 7 \mod 3 \\ 1 ≡ 1 \mod 3 \\ $$
Se la congruenza lineare è compatibile, allora anche l'equazione lineare corrispondente 4x+3y=7 ammette soluzioni intere x e y.
Una volta trovata una soluzione della congruenza lineare compatibile, posso trovare le soluzioni intere dell'equazione lineare.
Nota. La congruenza lineare 4x≡7 (mod 3) equivale all'equazione 4x+3y=7. Sapendo che una soluzione della congruenza lineare 4x≡7 (mod 3) è x=1 posso trovare l'incognita y dell'equazione $$ 4x+3y=7 \\ 4(1)+3y=7 \\ 3y=7-4 \\ y=1 $$ L'equazione ha una soluzione intera per x=1 e y=1. $$ 4x+3y=7 \\ 4(1)+3(1)=7 $$
Quante sono le soluzioni intere?
Una congruenza compatibile ax≡b (mod n) ammette d=MCD(a,n) soluzioni intere non congruenti modulo n tra loro. $$ x_0 + k \frac{n}{d} $$ Per ogni intero k compreso tra 0 e d-1.
Dove x0 è una soluzione della congruenza lineare ax0≡b.
Tutte le altre infinite soluzioni intere sono congruenti a queste prime d soluzioni.
Nota. Se MCD(a,n)=1 allora la congruenza lineare ha un'unica soluzione.
Esempio
Ho la seguente congruenza lineare
$$ 24x ≡ 21 \mod 9 $$
Semplifico i coefficienti al modulo 9.
$$ 6x ≡ 3 \mod 9 $$
Nota. Il primo coefficiente è 6 perché la divisione 24/9 ha resto 6. Il secondo coefficiente è 3 perché la divisione 21/9 ha resto 3.
La congruenza ammette soluzioni intere perché il massimo comune divisore (6,9)=3 è un divisore di b=3.
$$ MCD(6,9)=3|3 $$
Essendo MCD(6,9)=3 la congruenza lineare ha 3 soluzioni.
La prima soluzione intera x0 della congruenza è x=2
$$ 6x ≡ 3 \mod 9 \\ 6(2) ≡ 3 \mod 9 \\ 12 ≡ 3 \mod 9 \\ 3 ≡ 3 \mod 9 $$
Nota. La congruenza 12 mod 9 ≡ 3 mod 9 perché la divisione 12/9 ha resto 3.
Una volta trovata la soluzione x0 uso la formula con k=1 per trovare la seconda soluzione x1= 5
$$ x_1 = x_0 + k \frac{n}{d} \\ x_1 = 2 + 1 \frac{9}{3} \\ x_1 = 2 + 3 \\ x_1 =5 $$
Verifica. Con x=5 la congruenza diventa $$ 6x ≡ 3 \mod 9 \\ 6(5) ≡ 3 \mod 9 \\ 30 ≡ 3 \mod 9 \\ 3 ≡ 3 \mod 9 $$
Poi incremento k=2 per trovare la terza soluzione x2=8
$$ x_2 = x_0 + k \frac{n}{d} \\ x_2 = 2 + 2 \frac{9}{3} \\ x_2 = 2 + 6 \\ x_2 =8 $$
Verifica. Con x=2 la congruenza diventa $$ 6x ≡ 3 \mod 9 \\ 6(8) ≡ 3 \mod 9 \\ 48 ≡ 3 \mod 9 \\ 3 ≡ 3 \mod 9 $$
Essendo k=d-1, dove d=3 è il MCD, interrompo qui la ricerca.
Le soluzioni non congruenti tra loro di 6x ≡ 3 modulo 9 sono:
$$ x_0 = 2 \\ x_1 = 5 \\ x_2 = 8 $$
Sono ovviamente non congruenti tra loro perché divise per 9 hanno un resto diverso
$$ 2 \mod 9 ≠ 5 \mod 9 ≠ 8 \mod 9 $$
Le soluzioni non congruenti (x) mi permettono di trovare le soluzioni intere dell'equazione lineare corrispondente alla congruenza lineare
$$ 6x + 9y = 3 $$
Verifica. Con x=2 ottengo y=-1 $$ 6x + 9y = 3 \\ 6(2) + 9y = 3 \\ 12 + 9y = 3 \\ y = -1 $$ Con x=5 ottengo y=-3 $$ 6x + 9y = 3 \\ 6(5) + 9y = 3 \\ 30 + 9y = 3 \\ y = -5 $$ Con x=8 ottengo y=-3 $$ 6x + 9y = 3 \\ 6(8) + 9y = 3 \\ 48 + 9y = 3 \\ y = -5 $$
Ovviamente esistono altre infinte soluzioni intere (x) ma sono tutte soluzioni congruenti con le prime tre.
Verifica. Un'altra soluzione della 6x ≡ 3 mod 9 è 11 con k=3. $$ x_3 = x_0 + k \frac{n}{d} \\ x_3 = 2 + 3 \frac{9}{3} \\ x_3 = 2 + 9 \\ x_3 =11 $$ Tuttavia 11 è congruente con 2 modulo 9. $$ 11≡ 2 \mod 9 \\ 2 ≡ 2 \mod 9 $$ perché 11 diviso 9 ha resto 2.
E così via
