Teorema cinese del resto

Salve! Vorrei capire nel dettaglio come si risolvono i sistemi di congruenze con il teorema cinese del resto, e se questo metodo è applicabile a tutti i sistemi risolvibili.

Per risolvibili intendo quelli che rispettano la condizione spiegata da Galois poco fa qui: sistemi di congruenze.

Per esempio riporto un sistema presentato in un compito d'esame di matematica discreta:





Grazie mille in anticipo, tutto lo staff di questo forum ha risolto praticamente ogni mio problema!

Rieccoci qua yagamix

Mi sembra necessario iniziare dall'enunciato del Teorema Cinese del Resto, che afferma:

Siano interi a due a due coprimi e siano interi relativi. Allora il sistema di congruenze:



Ammette soluzioni. Inoltre se è una soluzione del sistema, tutte le soluzioni di tale sistema saranno date da:

, dove


Ti faccio osservare che la condizione che il teorema cinese del resto è solo una
condizione sufficiente per la risolubilità del sistema: può infatti capitare che i moduli non siano effettivamente a due a due coprimi ma il sistema abbia comunque soluzione.

Detto ciò passo al tuo esercizio. Dobbiamo risolvere il sistema di congruenze:



Poiché per il Teorema Cinese del resto, il sistema ammette soluzione. Troviamola

Per trovare la soluzione, si ripercorre passo passo la dimostrazione del Teorema Cinese del resto, che ometto in questo topic. Passo direttamente ai conti, cercando di spiegare cosa sto facendo in modo che tu possa utilizzare l'esercizio come "giuda"

Siano:













Iniziamo col determinare una soluzione particolare della congruenza:



ovvero di:



da cui

Procediamo poi determinando una soluzione particolare della congruenza:



ovvero di:



da cui

Ed infine una soluzione particolare della congruenza:



ovvero di:



da cui

La soluzione particolare del sistema sarà data da:



dove

Pertanto le soluzioni del sistema sono:

Tutto chiaro, graize Galois

Esiste per caso un metodo per verificare le soluzioni ottenute? Magari tramite qualche sostituzione?

Certo

Basta andare a sostituire la soluzione ottenuta nelle tre equazioni congruenziali che compongono il sistema

Lo faccio per una



Sostituendo al posto della abbiamo:



che è verificata in quanto

Idem per le altre due. Volendo puoi sostituire la soluzione generale ma è esattamente la stessa cosa visto che il è proprio ottenuto dai prodotti dei tre moduli

Era proprio quello che cercavo Galois

Galois ha scritto:


Scusate se riapro la discussione, io non riesco a capire dove salta fuori il 32 nella soluzione particolare, potreste illuminarmi? Grazie!

Ciao Mandarino, deriva direttamente dalla definizione di congruenza modulo 140. Dato che



segue automaticamente che

Grazie, quindi posso usare la seguente procedura come regola principale?

e questo sarà la mia ?

Ciao Mandarino

Sinceramente non ho ben capito quello che hai scritto.. Troppi simboli e troppe poche parole

In ogni caso (forse) mi è chiaro il tuo dubbio... In generale (ed è proprio questa la potenza ed il bello delle congruenze) se stai lavorando modulo e, da varie operazioni che fai ottieni un numero che sia maggiore o uguale ad , sfruttando la divisione con resto, puoi ricondurti ad un numero che sia minore di (Sembra ingarbugliato, lo so.. ma rileggi con calma ed aiutati con seguente esempio:)

Se stai lavorando modulo 3, e da un'operazione qualsiasi ti salta fuori il numero 7, allora, poiché:

si ha che:



Pertanto:




Allo stesso modo, se stiamo lavorando modulo e vien fuori il numero 123, poiché:



Allora e quindi:

[Edit - Omega] Cortesemente non quotare l'intero messaggio precedente per rispondere. E' sufficiente cliccare su "rispondi". [/Edit]

Grazie mille credo di aver capito, riscrivo ciò che ho scritto nel post precedente per conferma:

Noi abbiamo che la soluzione particolare del sistema sarà data da:



dove

le soluzioni del sistema sono: soluzione generale prodotto dei moduli (come se applicassi l'algoritmo di Euclide) , nel nostro caso: