Introduzione

Un sistema di congruenze lineari ha forma

$$ \left\{ \begin{aligned} x &\equiv b_1 \pmod{m_1} \\ x &\equiv b_2 \pmod{m_2} \\ &\vdots \\ x &\equiv b_n \pmod{m_n} \end{aligned} \right. $$

Vogliamo trovare (se esiste) la congruenza lineare delle soluzioni del nostro sistema, con forma:

$x\equiv b \pmod N$ dove $N=mcm(m1, \dots, m_n)$

STEP 1: Verificare se esiste soluzione

Per la verifica della risolubilità di un sistema di congruenze dobbiamo:

Verifica preliminare (SEMPRE) Verifica che ogni congruenza, presa singolarmente, ammetta soluzione.
Normalizzazione Se le singole equazioni sono possibili, trasformale tutte nella forma $x\equiv a\ ( \text{mod }n)$
Verifica del Sistema Caso 1: I moduli sono a due a due coprimi tra loro. Per il Teorema Cinese dei resti il sistema ammette soluzione. Caso 2: I moduli NON sono a due a due coprimi tra loro. Per concludere che il sistema ammette soluzione, dobbiamo verificare la compatibilità a coppie, della seguente congruenza:

$$ b_i \equiv b_j \ \text{(mod MCD(}m_i,m_j)) $$

La prima cosa da fare è verificare se i moduli sono coprimi tra loro a due a due.

Se la risposta è sì, allora si può procedere…