Congruenze lineari

# Congruenze lineari ###### tags: `md` Il problema da risolvere è: dati $a$, $b$, $m \in \mathbb{Z}$ con $m > 0$, trovare tutti gli interi che risolvono la congruenza lineare ad un'incognita $$ ax \equiv b \ mod \ m $$ ###### Osservazione Se esiste un intero $d$ che divide $a$ e $m$ ma non divide $b$, allora l'equazione non ha soluzioni. Per avere soluzioni, è necessario che $MCD(a, m)$ divida $b$. ###### Teorema La congruenza $$ ax \equiv b \ mod \ m $$ ha soluzione se e solo se il massimo comun divisore tra $a$ e $m$ divide $b$. In questo caso l'equazione ha infinite soluzioni, precisamente $MCD(a, m)$ soluzioni modulo $m$. ###### Osservazione Con "l'equazione ha $MCD(a,m)$ soluzioni modulo $m$" intendiamo che l'insieme delle soluzioni è composto da esattamente $MCD(a,m)$ soluzioni $\bar{x}$ che soddisfano $0 \le \bar{x} < m$ e tutte le altre sono i numeri che si ottengono da queste sommando loro un multiplo di $m$. ###### Dimostrazione Se $MCD(a, m)$ non divide $b$ sappiamo che la congruenza non ha soluzioni. Se divide $b$, $MCD(a,m)$ è il massimo divisore positivo comune ad $a$, $b$, e $m$. Dividendo l'equazione data per $MCD(a, m)$ otteniamo $$ a'x \equiv b' \ (m') $$ dove $$ a'=\frac{a}{MCD(a, m)} \quad b'=\frac{b}{MCD(a, m)} \quad m'=\frac{m}{MCD(a, m)} $$ che è equivalente a $ax \equiv b \ mod \ m$ Per costruzione $a'$ e $m'$ sono coprimi e $a'$ ha un inverso $e'$ modulo $m'$. Dato che anche $e'$ ha un inverso modulo $m'$, ovvero $a'$, allora anche $e'$ è primo con $m'$. Ottengo quindi $$ e'a'x \equiv e'b' \ (m') $$ Visto che $e'a' \equiv 1 \ (m')$, posso riscrivere l'equazione come $$ x \equiv e'b' \ (m') $$ Le soluzioni sono tutti e soli gli interi della forma $e'b' + km'$ al variare di $k$ in $\mathbb{Z}$. Visto che $m' = \frac{m}{MCD(a, m)}$, ci sono esattamente $MCD(a, m)$ interi di questa forma in ogni sequenza di $m$ numeri consecutivi. #### Il teorema cinese del resto Si vuole risolvere un sistema della forma $$ \begin{cases} x \equiv a \ (m_1) \\ x \equiv b \ (m_2) \end{cases} $$ Le soluzioni sono tutti e soli i numeri della forma $$ x = a+km_1, \ k \in \mathbb{Z} $$ ###### Teorema ###### Teorema cinese del resto per due equazioni con moduli Dato il sistema di equazioni $$ \begin{cases} x \equiv a \ (m_1) \\ x \equiv b \ (m_2) \end{cases} $$ tale sistema ammette soluzione se e solo se $MCD(m_1, m_2)|(b-a)$. In tal caso, presa una soluzione $x_0$, tutte le altre soluzioni del sistema sono i numeri della forma $$ x_0 + s\cdot mcm(m_1, m_2), \ s \in \mathbb{Z} $$ ###### Osservazione Si può anche esprimere dicendo che tutte le soluzioni del sistema sono i numeri $x$ che soddisfano $$ x \equiv x_0 \quad (mcm(m_1,m_2)) $$ In particolare, osserviamo che esiste un'unica soluzione $x$ con $0 \le x < mcm(m_1,m_2)$. \begin{cases} x \equiv a \ (m_1) \\ x \equiv b \ (m_2) \end{cases} ###### Teorema cinese del resto con moduli primi fra loro Dato il sistema di congruenze $$ \begin{cases} x \equiv a \ (m_1) \\ x \equiv b \ (m_2) \end{cases} $$ con $MCD(m_1, m_2) = 1$, tale sistema ammette sempre soluzione ed esiste un'unica soluzione $x_0$ tale che $0 \le x_0 < m_1 \cdot m_2$. Tutte le altre soluzioni del sisteam sono i numeri della forma $$ x_0 + q \cdot m_1 \cdot m_2, \quad q \in \mathbb{Z} $$ ###### Teorema ###### Teorema cinese del resto, forma classica Dato il sistema di congruenze $$ \begin{cases} x \equiv a_1 \ (m_1) \\ x \equiv a_2 \ (m_2) \\ .. \ .. \ .. \\ .. \ .. \ .. \\ x \equiv a_{n-1} \ (m_{n-1}) \\ x \equiv a_n \ (m_n)\end{cases} $$ in cui i moduli sono a due a due coprimi (per ogni $i \neq j$ vale $MCD(m_i, m_j) = 1$), tale sistema ammette sempre soluzione ed esiste un'unica soluzione $x_0$ tale che $0 \le x_0 < m_1 \cdot m_2 ... m_{n-1} \cdot m_n$. Tutte le altre soluzioni del sistema sono i numeri della forma $$ x_0 + q \cdot m_1 ... m_{n-1} \cdot m_n, \quad q \in \mathbb{Z} $$