Congruenze maledette...

[kekko89]

Approfitto del tuo topic per chiarirmi un dubbio. Devo risolvere il seguente sistema:
$x-=3 mod5$
$x-=5 mod6$

Ora,risolvendo la prima,ottengo $x=8+5h$ che sostituita nella seconda mi da $5h-=-3 mod 6$. Risolvendo l'equazione $5h+6k=1$ ottengo $h=-1$ e $k=1$: Moltiplicando per $-3$ ottengo definitivamente $h=3+6l$ che sostutuita nella prima mi da: $x=8+15+30l$ e quindi $x=23+30l$. Questo è il metodo delle sostituzioni se non sbaglio. Ora però,come devo fare se volessi usare il teorema cinese del resto? So che il modulo è dato dal prodotto dei moduli (in questo caso,infatti,30),ma non ho capito il procedimento del teorema. Grazie!!

[gygabyte017]

Allora, spiego in modo "operativo" come funziona in teorema cinese del resto.

PROCEDURA COMPLETA

Abbiamo il seguente sistema:

${(a_1x -= b_1 (mod n_1)),(vdots),(a_mx -= b_m (mod n_m)):}$

1) Per applicare il teorema, è necessario che $MCD(n_i,n_k)=1\qquad AAi!=k$
2) Controllare che sia risolubile, cioè che $AAk=1..m\qquad MCD(a_k,n_k) | b_k$

3) $AAk=1..m$, se $d_k=MCD(a_k,n_k)!=1$, sostituire la k-esima congruenza, con una equivalente (nel senso che ha le stesse soluzioni) ottenuta dividendo ogni elemento per $d_k$.
In altre parole, $a_kx -= b_k (mod n_k)$ diventa $(a_k)/(d_k)x -= (b_1)/(d_k) (mod (n_1)/(d_k)) = a'_kx -= b'_k (mod n'_k)$

Quindi, tutto il sistema iniziale viene riscritto così:
${(a_1x -= b_1 (mod n_1)),(vdots),(a_mx -= b_m (mod n_m)):}$ $" "=>" "$ ${((a_1)/(d_1)x -= (b_1)/(d_1) (mod (n_1)/(d_1))),(vdots),((a_m)/(d_m)x -= (b_m)/(d_m) (mod (n_m)/(d_m))):}$ $" "=" "$ ${(a'_1x -= b'_1 (mod n'_1)),(vdots),(a'_mx -= b'_m (mod n'_m)):}$

con $d_k=MCD(a_k,n_k)\qquad AAk=1..m$


4) Ora, ogni congruenza ammette un'unica soluzione. $AAk=1..m$, trovare la soluzione $c_k$ della k-esima congruenza usando la divisione euclidea e l'identità di bezout.
Trovate quindi tutte le $m$ soluzioni, il sistema viene nuovamente riscritto così:
${(x -= c_1 (mod n'_1)),(vdots),(x -= c_m (mod n'_m)):}$


!!! L'obiettivo delle prime 4 fasi è quindi quello di trasformare il sistema iniziale in un sistema in cui la $x$ abbia come coefficiente $1$, e ogni congruenza abbia un'unica soluzione (lo riscrivo per chiarezza cambiando qualche nomenclatura):
${(x -= c_1 (mod r_1)),(vdots),(x -= c_m (mod r_m)):}$

5) Siano:
$R:= r_1 * \quad cdots \quad* r_m$

$R_k := R / (r_k)\qquad AAk=1..m$

Consideriamo il seguente nuovo sistema:
$("*"){(R_1x -= c_1 (mod r_1)),(vdots),(R_mx -= c_m (mod r_m)):}$

Siano $bar x_k$ le soluzioni delle congruenze del sistema $("*")$.


Allora $bar x := R_1 * bar x_1 + cdots + R_m * bar x_m$ è L'UNICA SOLUZIONE DEL SISTEMA INIZIALE $ mod R$


----------------------------------------------------------------
Considerazioni: fare tutti questi calcoli è lungo! Se le congruenze del sistema sono poche, conviene molto di più risolvere il sistema con il metodo classico della sostituzione!

Tuttavia, tutta la procedura del teorema cinese del resto può essere semplificata :


PROCEDURA SEMPLIFICATA

Abbiamo il seguente sistema:

${(a_1x -= b_1 (mod n_1)),(vdots),(a_mx -= b_m (mod n_m)):}$

I primi tre punti 1) 2) e 3) sono identici.

Abbiamo quindi ottenuto il sistema equivalente:
${(a'_1x -= b'_1 (mod n'_1)),(vdots),(a'_mx -= b'_m (mod n'_m)):}$

che rinomino per semplicità: ${(a_1x -= b_1 (mod r_1)),(vdots),(a_mx -= b_m (mod r_m)):}$

4) Siano:
$R:= r_1 * \quad cdots \quad* r_m$

$R_k := R / (r_k)\qquad AAk=1..m$

Consideriamo il seguente nuovo sistema:
$("**"){(a_1R_1x -= c_1 (mod r_1)),(vdots),(a_mR_mx -= c_m (mod r_m)):}$

Siano $bar x_k$ le soluzioni delle congruenze del sistema $("**")$.

Allora $bar x := R_1 * bar x_1 + cdots + R_m * bar x_m$ è L'UNICA SOLUZIONE DEL SISTEMA INIZIALE $ mod R$


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

Faccio un esempio tanto per chiarire le idee (usando la procedura semplificata):

Abbiamo: ${(x-=3 (mod 5)),(x-=5 (mod 6)):}$

1) $MCD(5,6)=1$ OK!
2) $MCD(1,5) | 3$ e $MCD(1,6) | 5$ OK!
3) Essendo già tutti gli MCD=1 non dobbiamo sostituire niente.

4)
$R:=5*6=30$
$R_1=30/5=6$ e $R_2=30/6=5$

Consideriamo il nuovo sistema:
${(1*6*x-=3 (mod 5)),(1*5*x-=5 (mod 6)):}$

Risolviamo la prima congruenza: $6x -=3 (mod 5) => x -=3 (mod 5)$ quindi $x_1=3$.
Risolviamo la seconda congruenza: $5x -=5 (mod 6) $ $1 = 6 - 5*1 $ $5= 6*5 - 5*5 $ $=> x =-5 (mod 6)$ quindi $x_2=1$.

Soluzione del sistema: $bar x = 6*3 + 5*1 = 23 mod 30$



Spero sia tutto chiaro! (sto morendo dalla fatica ho scritto troppo )

Ciao ciao

[kekko89]

GRAZIE!!avanzi una birra..

[gygabyte017]

GRAZIE!!avanzi una birra..

Magari!

[remedios]

salve a tutti. sfrutto questo post per un dubbio circa questa congruenza:

$6x=626824 (mod 22)$

osservando che è riducibile per due diventa: $3x=313412(mod 11)$

ma $313412$ dovrebbe potersi scrivere in una classe di resto equivalente. è corretto? e come si trova?

[Lord K]

Trovi il resto della divisione per $11$ ^^

$313412= 28492*11+0$

quindi la tua congruenza risulta:

$3x\equiv 0 (11)$

[remedios]

ah, ok. allora avevo capito bene.
a questo punto però, la congruenza trovata non è compatibile, xkè il MCD(3,11) non divide 0.

giusto?

[Lord K]

Io dico che $MCD(3,11)=1|0$ visto che vale per tutti i numeri ^_^

Quindi la tua soluzione è:

$x\equiv 0(11)$

[remedios]

si, hai ragione. grazie per la correzione.

con le congruenze dovrebbe avere a che fare anche quest'esercizio: trovare il periodo di $p^9$ e $p^10$ sapendo che il periodo di $p$ è $12$

Il periodo di $p^h$ è quel numero positivo a cui devo elevarlo per ottenere l'identità. Ma poichè il periodo di $p$ è 12, è come se fossimo in $Z_12$.

A questo punto possiamo utilizzare la formula : $n/(MCD(h,n))$

è corretto?