Problema congruenza

[fafar]

Ciao a tutti

allora prima di tutto mi scuso se molto probabilmente farò degli errori poichè mi sono appena registrato

allora io non ho molto capito i problemi relativi alle congruenze, ad esempio:

$ 33x -= -9 (mod96) $

come faccio a trovare le soluzioni della congruenza?

spulciando di qua e di la ho capito che prima di tutto bisogna trovare l'mcd tra 33 e 96 con il metodo delle divisioni sucessive

ovvero dovrebbe essere:

$ 96 = 33 * 2 + 30; 30 = 96 + 33 ( - 2)

33 = 30 * 1 + 3: 3 = 33 + 30 ( - 1)

30 = 3 * 10 + 0 $

ora non saprei + come andare avanti e come distinguere vari casi.

Mi servirebbe sapere anche come elencare tutte le soluzioni tra 0 e 95.

Grazie

[fafar]

Ho capito che poi basta prendere la penultima riga e tornare indietro, ottenedo quindi x e y nella equazione

33x+96y=-9

ora come faccio a determinare quante soluzioni ci sono?

dopo una ricerca con google ho travato che siccome 3 il mcd è anche divisore di -9 allora ci sono infinite soluziuzioni, è corretto?
se si in che caso c'è una soluzione (posso immaginare quando anche l'mcd è 9) oppure nessuna soluzione (mcd maggiore di 9?) ?

grazie

[gundamrx91-votailprof]

Quali sono i concetti relativi alle congruenze algebriche che conosci?

[fafar]

prima di tutto grazie per la celere risposta.

poi non ho conoscenze in materia di congruenze, mi sto documentando utilizzando la funzione cerca in questo forum.

ok sono arrivato a questo punto:

calcolo l'mcd con l'algoritmo esteso di euclide (almeno penso si chiami così)

ax ≡ b mod n

dopo di chè se b è un multiplo dell'mcd(a,n) allora ci sono b soluzioni, caso non lo sia non ci sono soluzioni (credo sia così)

quindi ora dovrei avere

$ 3 = ( - 1 ) 96 + ( 3 ) 33 $

ora come faccio a scrivere la formula

x = {hb + kn / k € Z}.

Grazie

[gundamrx91-votailprof]

Si però in questo modo farai veramente molta fatica a procedere (intendo con i search qui e là )
senza una base teorica alle spalle.

Io ti consiglio di studiarti prima i concetti di:

relazione di congruenza
le classi dei resti e l'insieme delle classi dei resti
le congruenze algebriche

a questo punto sarai in grado di risolvere il problema che hai presentato.

Comunque per risolvere la tua congruenza algebrica devi prima di tutto
verificare se [tex]MCD(33,96)[/tex] divide [tex]-9[/tex]. Il massimo comune
divisore in questo caso è [tex]3[/tex] che guarda caso divide [tex]-9[/tex].
A questo punto puoi semplificare la congruenza dividendo tutto per [tex]3[/tex]:

[tex]33x \equiv -9_(_m_o_d_9_6_) \rightarrow 11x \equiv -3_(_m_o_d_3_2_)[/tex]

che ammette soluzione in quanto [tex](11,32)=1[/tex], cioè sono coprimi. Al fine però di
risolvere il problema devi trovare prima l'inverso moltiplicativo di [tex]11_(_m_o_d_3_2_)[/tex]
che si trova risolvendo la seguente congruenza algebrica [tex]11x \equiv 1_(_m_o_d_3_2_)[/tex]
e cioè [tex]32|11x-1[/tex], da cui [tex]11x-32y=1[/tex] che ha soluzione per [tex]x=3, y=1[/tex],
infatti [tex]33-32=1[/tex], quindi l'inverso moltiplicativo cercato è [tex]3[/tex], che moltiplicato
alla congruenza algebrica iniziale [tex]11x \equiv -3_(_m_o_d_3_2_)[/tex] diventa:

[tex]11x \equiv -9_(_m_o_d_3_2_) \equiv 23_(_m_o_d_3_2_)[/tex]
[tex]x \equiv 69_(_m_o_d_3_2_)[/tex] (ho moltiplicato per 3, quindi il coefficiente dell'incognita
diventa 1). Però [tex]x \equiv 69_(_m_o_d_3_2_) \equiv 5_(_m_o_d_3_2_)[/tex] che è la tua
soluzione. Infatti se ora sostituisci [tex]5[/tex] alla incognita di [tex]11x \equiv 23_(_m_o_d_3_2_)[/tex]
diventa [tex]11*5=23_(_m_o_d_3_2_)[/tex] ovvero [tex]32|55-23=32=32*k[/tex] per [tex]k \in Z[/tex]
cioè è un multiplo di [tex]32[/tex].

Spero di non aver fatto troppi errori....

[fafar]

grazie per la risposta....sono comunque ad un punto morto, ovvero ho capito come arrivare all'inverso moltiplicativo, ma poi non ho capito la seguente operazione:


11x ≡ -9 (mod 32) ≡ 23 (mod 32)

ovvero come hai ricavato quel 23.

Grazie

[gundamrx91-votailprof]

Dato che una congruenza la puoi scrivere anche usando le classi dei resti:

[tex]11x \equiv -9_(_m_o_d_3_2_)[/tex] equivale a [tex][11][x] = [-9]_(_3_2_)[/tex]

dove una classe di resto modulo n rappresenta l'insieme dei resti delle divisioni per n,
ovvero:

[tex][11]_(_3_2_)=\{11+32h | h \in Z\}=\{11,43,-21,75,-53,107,-85,...\}[/tex]
e
[tex][23]_(_3_2_)=\{23+32h | h \in Z\}=\{23,55,-9,87,-41,119,-73,...\}[/tex]

quindi in pratica sono degli insiemi definiti dai multipli di [tex]32 + 11[/tex] o [tex]23[/tex],
ma il numero che indica la classe di resto, chiamato anche rappresentante della classe,
è equivalente a uno qualsiasi che contiene, come [tex]-9[/tex] nel caso che ti ho indicato;
per cui scrivere [tex]23_(_m_o_d_3_2_)[/tex] o [tex]-9_(_m_o_d_3_2_)[/tex] è esattamente
equivalente, perchè tanto rappresentano la stessa classe di resto modulo [tex]32[/tex];
va da sè che si usano numeri positivi per facilitare i calcoli

[fafar]

credo di aver capito, grazie

[gundamrx91-votailprof]

Di nulla, nel caso riscrivi pure