Sistemi di congruenza lineari

Ciao Andrea! Come per l’altro esercizio che mi hai proposto ( https://library.weschool.com/domanda/sistemi-di-congruenze-lineari-15190.html#answer-15191 ) l’idea da seguire è sempre la stessa: portare il sistema in una forma del tipo $$\begin{cases} x \equiv a \quad (\text{mod }n_1) \\ x \equiv b \quad (\text{mod }n_2) \end{cases}$$in modo da tentare di applicare il teorema cinese dei resti. Siccome il nostro sistema è $$\begin{cases} 6x \equiv 8 \quad (\text{mod }14) \\ 3x \equiv 4 \quad (\text{mod }5) \end{cases}$$dobbiamo cercare di eliminare in tutti i modi i coefficienti delle $x$, con qualche trucco algebrico. Partiamo dalla prima congruenza: $$6x \equiv 8 \quad (\text{mod }14)$$Per prima cosa notiamo che possiamo dividere tutto quanto per due, in questo modo. Dato che questa congruenza è equivalente ad affermare che $6x = 8 + 14z$ per qualche $z \in \mathbb{Z}$, allora è anche vero che $3x = 4 + 7z$, cioè che $$3x \equiv 4 \quad (\text{mod }7)$$A questo punto vogliamo tentare di togliere quel $3$ davanti alla $x$. Se la congruenza fosse un’equazione, divideremmo entrambi i membri per $3$: o per meglio dire, moltiplicheremmo entrambi i membri dell’equazione per l’inverso di $3$. Nel contesto dell’aritmetica modulare si segue un’idea analoga, tenendo presente però che un certo elemento ammette inverso solo se è primo con il numero rispetto a cui stiamo facendo il modulo. Dato che $3$ è primo con $7$, possiamo affermare che $3$ ammette inverso: questo inverso va cercato tra tutte le possibili classi di resto modulo $7$, che sono rappresentabili da tutti i numeri naturali minori di $7$. Dopo un po’ di tentativi ci si accorge che $3 \cdot 5 = 15$ e che $15 \equiv 1 \ (\text{mod }7)$, ovvero che $3 \cdot 5 \equiv 1 \ (\text{mod }7)$, il che significa che è proprio $5$ a essere l’inverso di $3$! Presa quindi la nostra congruenza, possiamo moltiplicare a destra e a sinistra per $5$: $$(3 \cdot 5)x \equiv 4 \cdot 5 \ (\text{mod }7) \quad \Rightarrow \quad x \equiv 20 \ (\text{mod }7)$$Dato che $20 \equiv 6 \ (\text{mod }7)$ allora possiamo riscrivere, finalmente, la nostra congruenza nel modo migliore possibile: $$x \equiv 6 \quad (\text{mod }7)$$Passiamo adesso alla seconda congruenza: $$3x \equiv 4 \quad (\text{mod }5)$$Questa relazione sembra quella di prima, ma cambia il modulo (stiamo lavorando modulo $5$ e non modulo $7$). Per questo motivo, quando cerchiamo di “togliere” il $3$ - ovvero, quando cerchiamo di moltiplicare per l’inverso di $3$, se esiste - non possiamo aspettarci di moltiplicare per $5$ come abbiamo fatto prima, dato che l’inverso di $3$ modulo $5$ non è detto che sia lo stesso inverso di $3$ modulo $7$. Un attimo di riflessione ci porta a capire che l’inverso di $3$ esiste anche in questo caso, perché $3$ è primo con $5$; inoltre questo inverso è $2$, dato che $3 \cdot 2 = 6$ e $6 \equiv 1 \ (\text{mod }5)$. Allora otteniamo: $$(3 \cdot 2)x \equiv 4 \cdot 2 \ (\text{mod }5) \quad \Rightarrow \quad x \equiv 8 \ (\text{mod }5) \quad \Rightarrow \quad x \equiv 3 \ (\text{mod }5)$$Insomma, alla fine di tutto questo ragionamento siamo arrivati dove volevamo, dato che il sistema è diventato così: $$\begin{cases} x \equiv 6 \quad (\text{mod }7) \\ x \equiv 3 \quad (\text{mod }5) \end{cases}$$Il teorema cinese dei resti può essere applicato, dato che $5$ è primo con $7$: una soluzione particolare del sistema è $x=13$, visto che $13:7$ ha resto $6$ e $13:5$ ha resto $3$. La soluzione del sistema è quindi $$x = 13 + 35k, \qquad k \in \mathbb{Z}$$Ecco fatto :) Ciao, buona giornata!

Ok ora è chiaro....ma mi potresti spiegare come usi il teorema cinese per giungere a quelle soluzioni??? - Andrea Manisi 08 Settembre 2015

È proprio l'enunciato del teorema cinese dei resti, nella sua formulazione originale, a dire esattamente quello che ho scritto: le soluzioni del sistema sono esprimibili come somma di una soluzione particolare con un multiplo del prodotto dei moduli delle equazioni presenti nel sistema. Dato che i moduli sono $5$ e $7$ e che la soluzione particolare è $13$, la soluzione generale è proprio $x = 13 + 35k$ con $k$ intero: cioè, $13$ più un multiplo di $7 \cdot 5 = 35$. Se preferisci, le soluzioni possono anche essere scritte così: $$x \equiv 13 \quad (\text{mod }35)$$ - Michele Ferrari 08 Settembre 2015

Ok perfetto grazie mille!!! Ora ho visto la luce in questo argomento! Grazie - Andrea Manisi 08 Settembre 2015