Teorema Cinese del Resto

[Fedecart]

Ho cercato un po sulla rete e un po su questo forum ma ogni volta che si parla del teorema cinese del resto si va o troppo sullo specifico e sul complicato, parlando di campi e anelli che ora come ora non ho idea di cosa siano, oppure si da per scontato che tutti conoscano l'argomento. So che è utile nelle dimostrazioni di teoria dei numeri con le congruenze, di che si tratta? In parole povere se si può... E magari un esempio pratico =)

[EvaristeG]

Allora ... qui se ne parla senza troppi fronzoli e solo nel primo post... qui c'è un post con dei sistemi di congruenze ... e nessuno parla di anelli, mi pare... se poi hai dubbi, chiedi pure ancora.

[Fedecart]

Ok grazie. non le avevo trovate quelle discussioni sul forum, e quando ho cercato su wikipedia, li si che parlavano di anelli e non ci ho capito niente.
Grazie per i link

[gian92]

ciao ragazzi ho una domanda su questo teorema:

se abbiamo un sistema del tipo:

$ x_1\equiv a_1 (mod m_1)\\ x_2\equiv a_2 (mod m_2)\\ ..\\ x_k\equiv a_k (mod m_k)\\ $

se la il prodotto di tutti gli $ m_i $ con i diverso da m non ha inverso moltiplicativo modulo m il sistema non ha soluzioni?

[Tibor Gallai]

Sìsì.

[gian92]

ah ok grazie

[FrancescoVeneziano]

Invece potrebbe averne.
$ x\equiv 1 \pmod 2 x \equiv 3 \pmod 4 $
ha come soluzioni tutti gli $ x\equiv 3 \pmod 4. $

Quando $ m_1,m_2 $ non hanno fattori in comune il teorema cinese ti dice che il sistema ha sempre una soluzione modulo $ m_1 m_2 $; quando $ m_1 | m_2 $ ci sono due possibilità: o le due condizioni sono incompatibili e non ci sono soluzioni, o la congruenza modulo $ m_2 $ implica già quella modulo $ m_1 $ e quindi c'è una soluzione modulo $ m_2 $.
Nel caso generale si cerca di ricondursi a questi due casi che si sanno trattare: moduli coprimi e moduli che si dividono tra loro, e quindi prima si usa il teorema cinese per spezzare ogni congruenza modulo $ m_i $ in più congruenze modulo le potenze di primo che dividono $ m_i $, poi si raggruppano le congruenze così ottenute da $ m_i $ diversi che riguardano lo stesso primo e si controlla se sono incompatibili (in questo caso nessuna soluzione), o sovradeterminate (in questo caso una sola basterà ad implicare tutte le altre, che si potranno quindi ignorare). Terminata questa operazione, se nessuna congruenza è risultata incompatibile, si usa il teorema cinese nell'altro verso per trasformare il sistema rimasto, che ha un'equazione per ogni primo che divide il prodotto degli $ m_i $, in un'unica congruenza modulo il minimo comune multiplo degli $ m_i $. Esempio:
$ x\equiv 1 \pmod 6 x \equiv 2 \pmod {20} $
uso il teorema cinese ed ottengo
$ x\equiv 1 \pmod 2 x \equiv 1 \pmod 3 x \equiv 2 \pmod 4 x \equiv 2 \pmod 5 $
ed ora la prima e la terza sono incompatibili. Se invece fosse stato
$ x\equiv 1 \pmod 6 x \equiv 3 \pmod {20} $
avremmo ottenuto
$ x\equiv 1 \pmod 2 x \equiv 1 \pmod 3 x \equiv 3 \pmod 4 x \equiv 3 \pmod 5, $
la prima equazione è inutile e rimangono
$ x \equiv 1 \pmod 3 x \equiv 3 \pmod 4 x \equiv 3 \pmod 5 $
cioè $ x \equiv 43 \pmod {60} $.

[Tibor Gallai]

Ma perché, qualcuno aveva veramente capito cos'era la "m" di gian92?

[gian92]

Ma perché, qualcuno aveva veramente capito cos'era la "m" di gian92?

quella m era uno qualsiasi dei pedici...potevo dire k era uguale...ora è chiaro?
mi dispiace per non essere stato chiaro

p.s. graze mille francesco veneziano

[Tibor Gallai]

quella m era uno qualsiasi dei pedici...potevo dire k era uguale...ora è chiaro?

E' meno chiaro che mai... prima usi m come un indice, poi lo usi come modulo...
O mi state facendo una supercazzola, o avete una sorta di sinergia che vi permette di comunicare attraverso il nonsense, e capirvi.

[gian92]

quella m era uno qualsiasi dei pedici...potevo dire k era uguale...ora è chiaro?

E' meno chiaro che mai... prima usi m come un indice, poi lo usi come modulo...
O mi state facendo una supercazzola, o avete una sorta di sinergia che vi permette di comunicare attraverso il nonsense, e capirvi.

vediamo se riesco a spiegarmi:

con i diverso da m non ha inverso moltiplicativo modulo m il sistema non ha soluzioni?

è questa la m imputata?

se si avrei dovuto scrivere:

con i diverso da k non ha inverso moltiplicativo modulo $ \displaystyle m_k $ il sistema non ha soluzioni?

[Tibor Gallai]

Un qualunque intero è congruo a qualcosa in ogni modulo. Fissando un intero e scrivendo un po' di congruenze con moduli qualsiasi, si ottiene automaticamente un sistema risolubile, indipendentemente dai moduli.

Questo risponde alla domanda riveduta e corretta, come credo anche il post di FrancescoVeneziano, che probabilmente aveva capito tutto da subito.

[gian92]

forse non mi sono spiegato allora
$ x\equiv 5 (mod 6)\\ x\equiv 8 (mod 14)\\ x\equiv 9 (mod 21)\\ $

il fatto che $ 14 \cdot 21 $ non ha inverso moltiplicativo mod 6 implica che il sistema non abbia soluzioni?

[Tibor Gallai]

Ti stavo dicendo: ragionare solo sui moduli (ovvero le tue m) non ti permette di escludere che un sistema abbia soluzioni.

Perché?

Fissa un po' di moduli qualsiasi, e un intero qualsiasi. Tu ad esempio hai scelto 6, 14 e 21 come moduli. Allora, considerando ad esempio x=37, abbiamo il sistema

x == 1 (mod 6)
x == 9 (mod 14)
x == 16 (mod 21).

Questo sistema è risolubile, e una sua soluzione è x=37.

In generale, per qualsiasi k-upla di moduli puoi costruire svariati sistemi risolubili, con questo metodo. D'altra parte, esistono anche sistemi non risolubili, che ovviamente non si possono ottenere col metodo suddetto. Quindi, ragionare solo sui moduli (ovvero sugli m e non sugli a!) non permette di concludere che un dato sistema non abbia soluzione.
Può permetterti di concludere che un sistema abbia soluzione, ad esempio nelle ipotesi del teorema cinese del resto.

[gian92]

ah ho capito grazie mille

quindi in pratica se non possiamo costruire le soluzioni utilizzando il metodo che gobbino mette nelle sue schede nella pagina sul teorema cinese del resto (non so se ce lo hai presente, sennò te lo riscrivo) non è detto che il sistema non ne abbia!