da Tipper » 22/02/2009, 21:07
$90 x \equiv 30 \mod 120$ significa $90x = 30 + 120 k$, con $k \in \mathbb{Z}$, ossia (dividendo ambo i membri per $30$) $3x = 1 + 4 k$, quindi la prima congruenza è del tutto equivalente a $3x = 1 \mod 4$. Dato che $3$ e $4$ sono coprìmi allora $3$ è invertibile modulo $4$ e il suo inverso moltiplicativo è proprio $3$, di conseguenza la prima congruenza equivale a $x \equiv 3 \mod 4$.
Per quanto riguarda la seconda, $\gcd(25, 56) = 1$, quindi $25$ è invertibile modulo $56$ e il suo inverso moltiplicativo risulta essere $9$. Dato che $39 \cdot 9 \equiv 15 \mod 56$ la seconda congruenza equivale a $x \equiv 15 \mod 56$, cosicché il sistema di partenza si riduce a
$\{(x \equiv 3 \mod 4),(x \equiv 15 \mod 56):}$
È immediato verificare che se $x \equiv 15 \mod 56$ allora necessariamente $x$ è pure congruo a $3$ modulo $4$, mentre non è detto il viceversa. In conclusione, la soluzione del sistema è $x \equiv 15 \mod 56$.