Sistema di congruenze con parametro

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

Sistema di congruenze con parametro #64131

avt
fuffy
Cerchio
Ciao a tutti, non riesco a capire come risolvere questo sistema di congruenze con parametro: per quali valori di a\in \mathbb{Z} il sistema ammette soluzione?

Per tali valori scrivere la soluzione.

\begin{cases} 6425x\equiv 7 \ (mod 12)\\ 8614x\equiv 3 \ (mod 7)\\ 3x\equiv a \ (mod 8) \end{cases}


Ho semplificato le prime due equazioni:

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

Siccome i moduli non sono a 2 a 2 coprimi non è un ''sistema cinese'' (ad esempio MCD(8,12)=4).

Condizione necessaria affinché il sistema sia compatibile è che ogni equazione lo sia.
Ovviamente studio l'ultima equazione, che è compatibile se e solo se 1=mcd(3,8) \ | \ a, il che è sempre possibile.

Però questa è una condizione solo necessaria e non sufficiente. Esiste qualche criterio per studiare un sistema a moduli non coprimi?

Grazie emt
 
 

Re: Sistema di congruenze con parametro #64170

avt
Galois
Amministratore
Ciao fuffy emt

Procediamo con ordine. Come ben dici il Teorema cinese dei resti, anche al sistema che hai correttamente semplificato, non è applicabile in quanto i moduli non sono a due a due coprimi.

Ricordiamo però un altro risultato:

il sistema di congruenze:

\begin{cases} x \equiv a_1 \ (mod \ n_1) \\ x \equiv a_2 \ (mod \ n_2) \\ ...... \\ x \equiv a_m \ (mod \ n_m)\end{cases}

ammette soluzioni se e solo se

\mbox{mcd}(n_{i},n_{j})|[a_{i}-a_{j}]\ \forall i,j \in \{ 1,2,..m \}, i\neq j

-------------------------
-------------------------

Attenzione però! Questo risultato non è al momento applicabile al tuo sistema (anche a quello che hai ottenuto dopo la semplificazione):

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

in quanto il coefficiente della x deve essere 1. Poco male! Prendiamo una ad una le tue congruenze e riscriviamole in modo tale da avere 1 come coefficiente della x. A quel punto potremmo applicare il risultato appena visto emt

\bullet \ 5x\equiv 7 \ (mod 12)

L'inverso di 5 modulo 12 è 5, infatti:

5 \cdot 5 = 25 \equiv 1 \ (mod 12)

Pertanto, moltiplicando ambo i membri per 5 avremo:

x= 7 \cdot 5 = 35 \equiv 11 \ (mod 12)

e quindi la nostra prima congruenza equivale a:

x \equiv 11 \ (mod 12)

\bullet \ 4x\equiv 3 \ (mod 7)

L'inverso di 4 modulo 7 è 2, infatti:

4 \cdot 2 = 8 \equiv 1 \ (mod 7)

Pertanto, moltiplicando ambo i membri per 2 avremo:

x= 3 \cdot 2 = 6 (mod 7)

Quindi la seconda congruenza equivale a:

x \equiv 6 \ (mod 7)

\bullet \ 3x\equiv a \ (mod 8)

L'inverso di 3 modulo 8 è 3, infatti:

3 \cdot 3 = 9 \equiv 1 \ (mod 8)

Pertanto, moltiplicando ambo i membri per 3 avremo:

x= a \cdot a = 3a (mod 8)

e quindi la terza congruenza equivale a:

x \equiv 3a \ (mod 8)

Il nostro sistema si riduce quindi a:

\begin{cases}x \equiv 11 \ (mod 12) \\ x \equiv 6 \ (mod 7) \\ x \equiv 3a \ (mod 8)\end{cases}

Per la condizione necessaria e sufficiente prima vista, il sistema ammette soluzione se e solo se:

\mbox{mcd}(n_{i},n_{j})|[a_{i}-a_{j}]\ \forall i,j \in \{ 1,2,3 \}, i\neq j

Posto:

a_{1}=11,\ a_{2}=6,\ a_{3}=3a

n_{1}=12,\ n_{2}=7,\ n_{3}=8

si ha:

1=\mbox{mcd}(12,7) \ \overbrace{|}^{?} \ [11-6]

la risposta è, ovviamente: Sì

1=\mbox{mcd}(7,8) \ \overbrace{|}^{?} \ [6-3a]

Sì, per ogni a.

4=\mbox{mcd}(12,8) \ \overbrace{|}^{?} \ [11-3a]

Vediamo!

4 \ | \ (11-3a) se e solo se, per definizione di congruenza:

3a \equiv 11 \ (mod 4)

congruenza verificata se e solo se a=1+4k, \ k \in \mathbb{Z}

Pertanto questi sono tutti e soli i valori per cui il tuo sistema ammette soluzione emt
Ringraziano: Omega, Pi Greco, Ifrit, CarFaby
  • Pagina:
  • 1
Os