Sistema di equazioni congruenziali

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.

Sistema di equazioni congruenziali #59868

avt
Devilmoon
Punto
Salve, sono di nuovo qui a chiedervi spiegazioni per un sistema di equazioni congruenziali che non mi è proprio chiaro. Io ho questo sistema cinese, che mi viene chiesto di risolvere:

\begin{cases} x \equiv 2 \ mod(5) \\ x \equiv 1 \ mod(3) \\ x \equiv 6 \ mod(14) \\ x \equiv 5 \ mod(11) \end {cases}

Dai miei appunti, conosco una formula che mi permette di risolvere un generico sistema cinese a due equazioni in questo modo:

\begin{cases} x\equiv h \ mod(M)  \\ x\equiv k \ mod(N) \end{cases}

x=h+M[M]_{N}^{-1}(k-h)+MNZ

Tuttavia, non ho la più pallida idea di come io possa applicarla ad un sistema con più di 2 equazioni. Cercando quindi una risposta nel vostro forum mi sono quindi imbattuto in questa discussione:

Teorema cinese dei resti

che tratta la risoluzione di un sistema con 3 equazioni.

In modo forse un po' triviale ho provato a copiare la procedura per la ricerca della soluzione di quel post, aggiungendo però un N_{4} e moltiplicando anche n_{4} nei casi opportuni in relazione agli altri N. Tuttavia, i numeri che ho ottenuto cercando gli y mi hanno spiazzato, quindi ho pensato forse di non aver ben compreso il passaggio che viene fatto in questa parte di spiegazione:

Iniziamo col determinare una soluzione particolare y_{1} della congruenza:

N_{1} y \equiv 1 \ (mod \ n_{1})

ovvero di:

28 y \equiv 1 \ (mod \ 5)

da cui y_{1}=2

Potreste per favore spiegarmi nel dettaglio quel passaggio, o, in alternativa, se c'è una falla nel ragionamento che sto cercando di seguire?

Ancora meglio sarebbe avere una spiegazione sul come si possa risolvere un sistema cinese a n equazioni, ma non so se è un argomento trattabile in un post da forum.

In ogni caso, vi ringrazio in anticipo.
 
 

Sistema di equazioni congruenziali #59908

avt
Galois
Coamministratore
Ciao Devilmoon,

dobbiamo risolvere il sistema di congruenze:

\begin{cases} x \equiv 2 \ mod(5) \\ x \equiv 1 \ mod(3) \\ x \equiv 6 \ mod(14) \\ x \equiv 5 \ mod(11) \end {cases}

Utilizziamo il Teorema Cinese dei Resti il cui enunciato lo trovi nella discussione che tu stesso hai linkato.

Poniamo quindi, nel nostro caso:

n_1=5, \ n_2=3, \ n_3=14, \ n_4=11

Essendo tali numeri a due a due coprimi, per il teorema cinese dei resti, il sistema ammette soluzione: troviamola.

Iniziamo col porre:

\\ b_1=2, \ b_2=1, \ b_3=6, \ b_4=5\\ \\ \\ N=n_1 \cdot n_2 \cdot n_3 \cdot n_4 = 2310\\ \\ N_1=n_2 \cdot n_3 \cdot n_4 = 462\\ \\ N_2=n_1 \cdot n_3 \cdot n_4 = 770 \\ \\ N_3=n_1 \cdot n_2 \cdot n_4 = 165\\ \\ N_4=n_1 \cdot n_2 \cdot n_3 = 210

Iniziamo col determinare una soluzione particolare y_1 della congruenza:

N_1 y \equiv 1 \ (mod \ n_1)

ovvero di:

462 y \equiv 1 \ (mod \ 5)

da cui y_1=3

Procediamo poi determinando una soluzione particolare y_2 della congruenza:

N_2 y \equiv 1 \ (mod \ n_2)

ovvero di:

770 y \equiv 1 \ (mod \ 3)

da cui y_2=2

Ora determiniamo una soluzione particolare y_3 della congruenza:

N_3 y \equiv 1 \ (mod \ n_3)

ovvero di:

165 y \equiv 1 \ (mod \ 14)

da cui y_3=9

Ed infine una soluzione particolare y_4 della congruenza:

N_4 y \equiv 1 \ (mod \ n_4)

ovvero di:

210 y \equiv 1 \ (mod \ 11)

da cui y_4=1.

La soluzione particolare x_0 del sistema sarà data da:

\\ x_0=b_1 N_1 y_1+b_2 N_2 y_2+b_3 N_3 y_3 + b_3 N_3 y_3 =\\ \\ 2 \cdot 462 \cdot 3 + 1 \cdot 770 \cdot 2 + 6 \cdot 165 \cdot 9 + 5 \cdot 210 \cdot 1 = 2772+1540+8910+1050=14272=412 \ (mod \ 2310)

dove 2310=n_1 \cdot n_2 \cdot n_3 \cdot n_4

Pertanto le soluzioni del sistema sono:

x=412+2310k, \ k \in \mathbb{R}

Questa la famiglia delle soluzioni del tuo sistema. Ora, in risposta alla tua seconda domanda:

N_{1} y \equiv 1 \ (mod \ n_{1})

ovvero di:

28 y \equiv 1 \ (mod \ 5)

da cui y_{1}=2

Potreste per favore spiegarmi nel dettaglio quel passaggio, o, in alternativa, se c'è una falla nel ragionamento che sto cercando di seguire?

Se vuoi sapere da dove viene fuori l'equazione congruenziale: N_{1} y \equiv 1 \ (mod \ n_{1})

ti rimando alla dimostrazione del Teorema Cinese dei resti che trovi su un qualsiasi testo di Algebra (sarebbe improponibile riportarla qua)

28 y \equiv 1 \ (mod \ 5) si ottiene dalla precedente sostituendo al posto di N_1, \ n_1 i valori precedentemente posti.

y_{1}=2

è la soluzione di tale equazione congruenziale (leggimi!)

Se il tuo dubbio è questo, ovvero se non sai come risolvere le equazioni congruenziali, nel precedente post è spiegato come si deve procedere.

Il procedimento là proposto è quello standard. Se però ci facciamo furbi ed aguzziamo la mente:

cosa vuol dire risolvere, ad esempio, l'equazione congruenziale:

28 y \equiv 1 \ (mod \ 5) ?

Vuol dire trovare un y tale che 5 | (28y-1)

Inoltre tale y deve appartenere, in questo caso, a \mathbb{Z}_5, ovvero y \in \{0,1,2,3,4\}

nulla ci vieta quindi, se abbiamo a disposizione (come penso) una calcolatrice, di procedere per tentativi (sono 5 valori da provare). E, se facciamo girare

ancor di più la mente, e ci ricordiamo dei criteri di divisibilità, sapendo che un numero è divisibile per 5 se termina per 0 o 5,

tale deve essere il numero 28y-1. Poiché a 28y dobbiamo poi sottrarre 1, 28y deve terminare quindi per 6 o per 1. Essendo 28 pari, moltiplicato per

qualsiasi valore non darà mai un numero dispari (deve quindi terminare necessariamente per 6). Poiché 28 \cdot 2 = 56 la nostra y sarà proprio 2.

(A dirsi sempre lungo e tortuoso ma a farsi è estremamente semplice)
Ringraziano: Omega, CarFaby, Devilmoon

Re: Sistema di equazioni congruenziali #59947

avt
Devilmoon
Punto
Tutto chiarissimo!

A quanto pare stavo svolgendo correttamente l'esercizio ma avevo sbagliato un paio di calcoli, e da qui quei numeri "strani" che mi trovavo...

Ti ringrazio molto, solo una piccola cosa: slla fine, il risultato del calcolo di x_{0} è 14272, che poi tu eguagli a 412(2310).

Questo perché 14272 fa parte della classe di 412 modulo 2310? Se sì, c'è un modo veloce per sapere a quale classe appartiene un dato n in mod m quando trattiamo numeri così grandi?

EDIT: forse mi sono dato una risposta da solo.

Se ho un numero k=x(n), posso fare k/n, ottenendo un risultato molto probabilmente con qualche resto, moltiplicare n per la parte intera del risultato ottenuto dalla divisione e sottrarlo a k, giusto?

Re: Sistema di equazioni congruenziali #60017

avt
Galois
Coamministratore
Eccomi!

14272=412 \ (mod \ 2310)

deriva direttamente dalla definizione di congruenza modulo 2310. Dato che

14272 : 2310 = 6 \mbox{ resto }412

segue automaticamente che

14272=412 \ (mod \ 2310)

Ti basta eseguire una semplice divisione con resto (se vuoi aiutarti con la calcolatrice per trovare il quoziente).
Ringraziano: Omega, CarFaby, Devilmoon
  • Pagina:
  • 1
Os