- $97x\equiv13(mod\,105)$
affinchè la congruenza ammetta soluzioni c'è bisogno che MCD(105,97) divida 13
in questo caso abbiamo MCD(105,97)=1 che divide 13 per cui la congruenza ammette soluzioni;
la congruenza corrisponde a dire che $97x$ diviso $105$ da come resto $13$;
ossia $97x=105y+13 \quad\Rightarrow\quad 13=97x-105y$
troviamo anzitutto una soluzione particolare della diofantea utilizzando l'algoritmo di Euclide a contrario;
l'algoritmo di Euclide applicato tra 105 e 97 è il seguente:
$105=97+8 \\97=12\cdot8+1\\8=8\cdot1+0$
per applicarlo a contrario isoliamo i resti nelle prime 2 uguaglianze:
$8=105-97\\1=97-12\cdot8$
sostituendo la 1° nella 2° si ha:
$1=97-12(105-97)=97\cdot13-105\cdot12$
moltiplicando l'uguaglianza per 13 si ha:
$13=97\cdot169-105\cdot156$
abbiamo trovato la nostra sol. particolare $x=169$ e $y=156$
pertanto tutte le possibili soluzioni della congruenza saranno del tipo
$169+105k \quad\quad \forall k\in Z$
(in questo caso abbiamo un'unica espressione che esprime la soluzione, a differenza dei sistemi di congruenze lineari) - $12x\equiv 33 (mod\,57)$
in tal caso si ha $MCD(12,57)=3|33$ per cui la congruenza ammette soluzioni; inoltre poichè MCD è diverso da 1, allora la congruenza è semplificabile;
dividendo per 3 otteniamo l'equivalente:
$4x\equiv 11 (mod\, 19)$
da cui ricaviamo la diofantea $11=4x+19y$
Applichiamo l'algoritmo di Euclide a 19 e 4:
$19=4\cdot4+3\\4=3+1\\3=3\cdot1+0$
da cui
$1=4-3=4-(19-4\cdot4)=4\cdot5+19$
moltiplichiamo per 11:
$11=4\cdot55+19\cdot11$
la nostra sol.particolare è $x=55$
le possibili soluzioni della congruenza sono del tipo
$55+19k \quad\quad\forall \kappa \in Z$ - $14x\equiv1 (mod\, 77)$
$MCD(77,14)=7$ che non divide 1 pertanto la congruenza non ammette soluzioni
Voglio segnalare i seguenti appunti che ho trovato sulla rete, e che mi hanno chiarito (almeno credo) ogni residuo dubbio sulle congruenze lineari:
http://www.dm.unipi.it/~gaiffi/lmm_2005 ... azioni.pdf