Sistema di congruenze

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.
Questa sezione è un contenitore temporaneo per i topic speciali a pagamento (One-Shot)

Se hai acquistato uno o più Topic speciali, puoi pubblicarli qui cliccando su "Apri un Topic".

Il registro completo dei Topic risolti e in corso è disponibile sul proprio profilo.

Sistema di congruenze #85134

avt
luca82
Punto
Salve, il mio problema è inerente a un sistema di congruenze. Ho inseguente sistema:

\begin{cases}5x \equiv 2 \ (\mbox{mod }3) \\ 3x \equiv 4 \ (\mbox{mod }7) \\ 3x \equiv 7 \ (\mbox{mod }8) \end{cases}

Vorrei sapere come ridurlo nella forma compatibile del teorema cinese del resto e come si risolve.

Per favore dato che mi sto rompendo la testa su questo tipo di esercizi da parecchio vi prego di essere quanto più semplici possibili nei passaggi.

Grazie in anticipo e auguri!
 
 

Sistema di congruenze #85142

avt
Galois
Coamministratore
Ciao Luca emt

Dobbiamo risolvere il seguente sistema di congruenze

\begin{cases}5x \equiv 2 \ (\mbox{mod }3) \\ 3x \equiv 4 \ (\mbox{mod }7) \\ 3x \equiv 7 \ (\mbox{mod }8) \end{cases}

Come hai ben intuito possiamo ricorrere al teorema cinese del resto (leggimi) le cui ipotesi sono:

- i coefficienti delle incognite, ossia delle x, devono essere uguali ad 1;

- i moduli debbono essere a due a due coprimi, ossia, presi a due a due, il loro massimo comun divisore deve essere 1.

La seconda ipotesi è soddisfatta, in quanto

\mbox{mcd}(3,7)=\mbox{mcd}(3,8)=\mbox{mcd}(7,8)=1

ma non lo è la prima ipotesi. Prendiamo quindi in esame, una per volta, le tre equazioni congruenziali e scriviamole in modo tale che sia 1 il coefficiente dell'incognita. Partiamo dalla prima

5x \equiv 2 \ (\mbox{mod }3)

Come fare? Basta trovare l'inverso moltiplicativo di 5 modulo 3 e moltiplicare ambo i membri dell'equazione per il numero trovato. A tal scopo ti invito a leggere la seguente discussione sul metodo per trovare gli elementi invertibili in Zn.

Dal momento che

5 \cdot 2 = 10 \equiv 1 \ (\mbox{mod }3)

allora 2 è l'inverso moltiplicativo cercato. Moltiplicando ambo i membri dell'equazione per 2 si ha

(5\cdot 2)x \equiv (2\cdot 2) \ (\mbox{mod }3)

10x \equiv 4 \ (\mbox{mod }3)

ossia, essendo 10 \equiv 1 \ (\mbox{mod }3) \mbox{ e } 4 \equiv 1 \ (\mbox{mod }3)

ricadiamo nell'equazione

x \equiv 1 \ (\mbox{mod }3)

che possiamo sostituire alla prima equazione del sistema congruenziale.

Procediamo allo stesso modo con le altre due.

3x \equiv 4 \ (\mbox{mod }7)

la possiamo riscrivere come

x \equiv 6 \ (\mbox{mod }7)

in quanto l'inverso moltiplicativo di 3 modulo 7 è 5 (basta osservare che 3\cdot 5=15 \equiv 1 (\mbox{mod } 7)) e, moltiplicando ambo i membri dell'equazione per 5, abbiamo

15x \equiv 20 \ (\mbox{mod }7)

da cui, essendo 20 \equiv 6 \ (\mbox{mod }7),

x \equiv 6 \ (\mbox{mod }7).

Infine, la terza ed ultima equazione del sistema:

3x \equiv 7 \ (\mbox{mod }8)

diventa

x \equiv 5 \ (\mbox{mod }8).

Anche in questo dopo aver trovato l'inverso moltiplicativo di 3 modulo 8, che è 3, basta moltiplicare per 3 e ridurre utilizzando la definizione di congruenza, ossia

(3\cdot 3)x \equiv (7\cdot 3) \ (\mbox{mod }8)

9x \equiv 21 \ (\mbox{mod }8)

x \equiv 5 \ (\mbox{mod }8)


Il sistema di congruenze da risolvere è, quindi:

\begin{cases}x \equiv 1 \ (\mbox{mod }3) \\ x \equiv 6 \ (\mbox{mod }7) \\ x \equiv 5 \ (\mbox{mod }8) \end{cases}

e, possiamo procedere, con il teorema cinese del resto.

Siano:

b_1=1, \ b_2=6, \ b_3=5

n_1=3, \ n_2=7, \ n_3=8

N=n_1 \cdot n_2 \cdot n_3 = 168

N_1=n_2 \cdot n_3 = 56

N_2=n_1 \cdot n_3 = 24

N_3=n_1 \cdot n_2 = 21

Determiniamo una soluzione particolare (che indico con y_1) della congruenza:

N_1 y \equiv 1 \ (\mbox{mod} \ n_1)

ossia di:

56 y \equiv 1 \ (\mbox{mod} \ 3)

Evidentemente, tale congruenza ha per soluzione y_1=2.

Procediamo poi determinando una soluzione particolare y_2 della congruenza:

N_2 y \equiv 1 \ (\mbox{mod} \ n_2)

cioè di:

24 y \equiv 1 \ (\mbox{mod} \ 7)

da cui y_2=5

Infine una soluzione particolare y_3 di:

N_3 y \equiv 1 \ (\mbox{mod} \ n_3)

ossia di:

21 y \equiv 1 \ (mod \ 8)

è y_3=5


Possiamo così concludere che la soluzione particolare x_0 del sistema è data da:

x_0=b_1 N_1 y_1+b_2 N_2 y_2+b_3 N_3 y_3=

=1 \cdot 56 \cdot 2 + 6 \cdot 24 \cdot 5 + 5 \cdot 21 \cdot 5 = 112+720+525=

=1357 = 13 \ (\mbox{mod} \ 168)

in quanto 13 è il resto della divisione tra 1357 e 168, dove 168=n_1 \cdot n_2 \cdot n_3.


Le (infinite) soluzioni del sistema sono:

x=13+168k, \mbox{ con } k \in \mathbb{Z}

È tutto! Ci tengo a sottolineare che il metodo da me seguito per la soluzione del sistema congruenziale segue, pari passo, la dimostrazione del Teorema Cinese del resto che, ovviamente, ho omesso in questo topic.
Ringraziano: Omega, CarFaby, Luxspark

Sistema di congruenze #85170

avt
luca82
Punto
Davvero perfetto, grazie!
Ringraziano: Galois

Re: Sistema di congruenze #85551

avt
luca82
Punto
Ho un secondo dubbio sul teorema cinese del resto: non penso di aver capito come si ottiene il risultato della seconda equazione è vorrei sapere se è un problema di metodo mio oppure di battitura.

L'equazione

24y \equiv 1 ( \ \mbox{mod } 7)

dà come risultato  y=5 mentre a me esce y=3.

Potrei sapere come si svolge questo passo?

Re: Sistema di congruenze #85581

avt
Galois
Coamministratore
Ciao Luca,

nel risolvere l'equazione congruenziale

24y \equiv 1 ( \ \mbox{mod } 7)

il teorema cinese del resto non centra nulla, ma, per l'appunto, si tratta di risolvere un'equazione congruenziale.

Come spiegato nella discussione del link della mia precedente risposta, risolvere l'equazione congruenziale (ammettendo che abbia soluzione)

ax \equiv b \ (\mbox{mod } n)

equivale a trovare l'inverso moltiplicativo di a modulo n ed a moltiplicare ambo i membri per tale inverso.

Nel caso in esame

24y \equiv 1 ( \ \mbox{mod } 7)

L'inverso moltiplicativo di 24 (modulo 7) è 5, infatti

24 \cdot 5 = 120

che è equivalente ad 1 (modulo 7).

Moltiplicando ambo i membri dell'equazione per 5 abbiamo

120 y \equiv 5 ( \ \mbox{mod } 7)

ossia, essendo 120 \equiv 1 ( \ \mbox{mod } 7)

y \equiv 5 ( \ \mbox{mod } 7)

è proprio la soluzione.

Il tutto potrebbe sembrare un po' confuso ed è normale.. Rileggi tutto con calma e, soprattutto, svolgi qualche altro esercizio. Vedrai che tutto, pian piano, prenderà una luce diversa. emt
Ringraziano: CarFaby, luca82
  • Pagina:
  • 1
Os