Le congruenze lineari sono le relazioni tra le grandezze che hanno lo stesso resto dopo essere state divise da un numero intero, dove le quantità sono costanti o polinomi di primo grado.
le congruenze lineari sono di solito specificate nella forma ax ≡ b (mod n), dove b è il resto e n è il numero intero – spesso definito come il modulo – con il quale ax è diviso. Risolvere un sistema di congruenze lineari significa trovare i valori per le variabili che soddisfano ciascuna delle congruenze in un sistema.
Istruzioni
Quello che vi serve
Calcolatrice
1.
Trovare il massimo comun divisore per il modulo e il coefficiente della variabile, per ogni congruenza. Se il resto della congruenza è divisibile per il massimo comun divisore, allora la congruenza ha una soluzione. Inoltre, per ax ≡ b (mod n), il massimo comun divisore di n ed a è il numero di soluzioni per x quando x è compreso tra 0 e n. Ad esempio, nella congruenza 4x ≡ 2 (mod 6), il massimo comun divisore di 6 e 4 è 2, e 2 – il resto – è divisibile per 2 – il massimo comune divisore, per cui questa congruenza ha 2 soluzioni.
Se una qualsiasi delle congruenze non ha soluzioni, allora non vi è alcuna soluzione al sistema.
2. Risolvere la congruenza prima usando la formula x = b + kn, dove n è il modulo ed e b è il resto. Se le congruenze sono x ≡ 3 (mod 5) e x ≡ 5 (mod 8), allora x = 5k 3 per la prima congruenza.
3. Sostituire il valore di x in termini di k nell’equazione successiva. Nell’esempio di cui sopra, ciò significherebbe che 5k 3 ≡ 5 (mod 8).
Sottraendo 3 da entrambe le parti si ha 5k ≡ 2 (mod 8). Risolvere per k con l’aggiunta di 8, il modulo, a 2, il resto, fino a raggiungere un numero divisibile per 5. In questo caso, 2 8 = 10, e 10 è divisibile per 5, così 5k ≡ 10 (mod 8). Dividere attraverso il 5 per ottenere k ≡ 2 (mod 8), oppure k = 8m +2. Se ci sono più di due congruenze, quindi ripetere questo passaggio per ogni congruenza supplementare, con una nuova variabile per ogni congruenza.
4. Sostituire il valore di k dalla congruenza nel secondo il valore per x in congruenza prima di trovare un valore per x che lavorerà per entrambe le congruenze. Nell’esempio precedente, perché k = 8m 2, quindi x = 5 (8m +2) +3 = 40 +13, oppure x ≡ 13 (mod 40). Questo significa che i valori per x saranno sia per x ≡ 3 (mod 5) e x ≡ 5 (mod 8) sono 13, 53, 93, ecc.
