Risoluzione sistema di congruenze

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

Risoluzione sistema di congruenze #54031

avt
pepe
Cerchio
Ciao! Ho il seguente sistema di congruenze da risolvere:

5x congruo 2 mod 11
3x congruo 2 mod 7

Io so che queste due congruenze hanno MCD =1 quindi coprime e dunque posso usare il metodo del teorema cinese dei resti, solo che non mi riesce!
Potete darmi una mano? Grazie! =)
 
 

Risoluzione sistema di congruenze #54039

avt
frank094
Maestro
Ciao Pepe,

dobbiamo risolvere il sistema di congruenze con equazioni di primo grado

\left\{ \begin{array}{l l} 5x \equiv_{11} 2 \\ 3x \equiv_7 2 \end{array} \right.

Fa attenzione però: le ipotesi del teorema cinese del resto non sono ancora verificate. Ricordati che la richiesta che i moduli delle equazioni siano coprimi due a due segue l'ipotesi che il sistema sia del tipo

\left\{ \begin{array}{l l} x \equiv_{m} a \\ x \equiv_n b \end{array} \right.

Dobbiamo togliere i coefficienti davanti alle x. In particolare studiamo singolarmente le due equazioni per vedere se sono risolvibili e, nel qual caso, ridurle in modo da applicare il teorema.

5x \equiv_{11} 2

è risolvibile perché 5 e 11 sono coprimi ed in particolare il loro massimo comun divisore divide 2. Allora cerchiamo l'inverso di 5 cercando uno dei rappresentanti della classe i cui elementi, moltiplicati per 5, tornano 1 modulo 11.

5x \equiv_{11} 1 \implies x_i = -2

Trovato l'inverso, moltiplichiamo per esso la nostra equazione

(-2) \cdot 5x \equiv_{11} (-2) \cdot 2 \implies x \equiv_{11} -4

L'altra equazione è invece

3x \equiv_7 2

che è ancora risolvibile in quando il massimo comun divisore tra 3 e 7 divide 2; in particolare cerchiamo anche qui l'inverso

3x \equiv_7 1 \implies x_i = -2

Trovare l'inverso è banale; se moltiplichiamo per 3 per due otteniamo un numero equivalente a -1 modulo sette perciò basta cambiare di segno!

(-2) \cdot 3x \equiv_7 (-2) \cdot 2 \implies x \equiv_7 - 4

Adesso, sei nelle condizioni di applicare il teorema cinese del resto perché il tuo sistema è equivalente a

\left\{ \begin{array}{l l} x \equiv_{11} -4 \\ x \equiv_7 -4 \end{array} \right.

Chiaramente in questo caso la soluzione è banale ( sai trovarla? ) e sarà l'unica soluzione del sistema modulo 77.

Hai bisogno di chiarimenti?
Ringraziano: Omega, Pi Greco, Ifrit, Galois, CarFaby

Re: Risoluzione sistema di congruenze #54116

avt
pepe
Cerchio
allora intanto grazie=)
allora fin li ci son arrivata, ora per dire la soluzione finale come faccio?
ti dico come ho fatto io ma non so se sia giusto..

5(-2*7) in mod 11 + 3(15) in mod 7 ==> (-14*5)+3(15) = [-25] in mod 77 <=> [52] in mod 77

?

Re: Risoluzione sistema di congruenze #54131

avt
frank094
Maestro
In realtà è molto più semplice di quel che pensi ( grazie al fatto che ha uno stesso resto per due moduli )! Considera, ad esempio, l'equazione diofantea associata:

-4 + 11n = - 4 + 7k \qquad \qquad n, \, k \in \mathbb{Z}

la quale si può scrivere anche come

11n - 7k = 0 \qquad \qquad n, \, k \in \mathbb{Z}

Chiaramente la coppia (0, 0) rappresenta una soluzione particolare e, se vogliamo, anche banale perciò è chiaro che si avrà

n = 7t

oppure, in maniera del tutto equivalente, si avrà

k = 11t

Se ora andiamo a sostituire troviamo

x = - 4 + 77t \implies x \equiv_{77} -4

Ho fatto un giro di calcoli per mostrarti che torna così ma è sufficiente vedere che, avendo x lo stesso resto per entrambi i moduli coprimi ( nota che è una ipotesi necessaria, altrimenti questa proprietà non vale in questo modo ma c'è di mezzo il minimo comune multiplo! ), deve averlo anche per il prodotto tra i moduli stessi. ( Questa è una delle proprietà delle congruenze che dovresti aver introdotto all'inizio! Se non ti è stata formalizzata dimmelo pure che te la scrivo qui emt ).
Ringraziano: Omega, Galois, CarFaby

Re: Risoluzione sistema di congruenze #54141

avt
pepe
Cerchio
no non me l'han detta.. puoi scrivermela per favore? =)

Re: Risoluzione sistema di congruenze #54143

avt
frank094
Maestro
Certamente!

Proprietà. Siano a, \, b \in \mathbb{Z} numeri interi e siano n, \, m \geq 2 \in \mathbb{N}; allora vale l'implicazione

a \equiv_m b, \; \; a \equiv_{n} b \implies a \equiv_{[m, \, n]} b

dove [m, \, n] indica il minimo comune multiplo.

Dimostrazione. La prima equivale a dire che

m \mid a - b

mentre la seconda equivale a dire

n \mid a - b

Allora è chiaro che, per definizione di minimo comune multiplo, si ha

[m, n] \mid a -b \implies a \equiv_{[m, \, n]} b

Nota ovviamente che se i moduli sono coprimi il minimo comune multiplo è il loro prodotto ed inoltre vale anche l'implicazione inversa della proprietà!
Ringraziano: Omega, Pi Greco, CarFaby
  • Pagina:
  • 1
Os