Equazioni Congruenziali
Salve ragazzi vorrei un chiarimento su questo argomento.
In pratica il mio prof ha detto che risolvere un equazione di questo tipo:
[A]n . [X]n = n in Zn
equivale a risolvere l'equazione congruenziale:
a.x = b ( modulo n)
prima di tutto vorrei capirne il motivo..
poi ha detto che tale equazione congruenziale ammette infinite soluzioni se esiste il MCD(a,n) ed esso divide b,altrimenti non esistono..
ma perchè infinite??
grazie
In pratica il mio prof ha detto che risolvere un equazione di questo tipo:
[A]n . [X]n = n in Zn
equivale a risolvere l'equazione congruenziale:
a.x = b ( modulo n)
prima di tutto vorrei capirne il motivo..
poi ha detto che tale equazione congruenziale ammette infinite soluzioni se esiste il MCD(a,n) ed esso divide b,altrimenti non esistono..
ma perchè infinite??
grazie
Risposte
in una classe $[A]_n$ ci sono infiniti elementi (sei d'accordo?). $[A]_n=A + kn$ quindi $[a]_n \cdot [x]_n = ax+k_1an+k_2xn+k_1k_2n^2 = b + k_3 n$ l'ultima uguaglianza si ha solo se $ax=b$ mod n (mi pare evidente, sei d'accordo?)
Inoltre se d è soluzione della congruenza, lo è anche $d + kn$ (prova con dei numeri e te ne accorgi). Chiarito adesso?
Inoltre se d è soluzione della congruenza, lo è anche $d + kn$ (prova con dei numeri e te ne accorgi). Chiarito adesso?
Beh si ha che $[ax]_n=_n$ che per definizione vuol dire che $ax$ è relazione mod$n$ con $b$ ovvero che $ax-b=kn$ con $k in ZZ$ che è un modo equivalente per dire che $ax \equiv b mod n$
Il fatto che ne siano infinite invece deriva dal fatto che puoi prendere qualsiasi elemento della classe di equivalenza mod $n$ per rendere ancora vera l'uguaglianza. Essendo la relazione definita sugli interi, ogni classe ammette infiniti elementi e quindi, infinite soluzioni.
Prendi ad esempio la congruenza $2x \equiv 1 mod 5$ ammette soluzione per $x=3$, ma ammette soluzione anche per $x=8$ o per $x=13$ e così via. In pratica le soluzioni sono del tipo $x=3+5k$ con $k in ZZ$
Spero di essere stato chiaro.
Il fatto che ne siano infinite invece deriva dal fatto che puoi prendere qualsiasi elemento della classe di equivalenza mod $n$ per rendere ancora vera l'uguaglianza. Essendo la relazione definita sugli interi, ogni classe ammette infiniti elementi e quindi, infinite soluzioni.
Prendi ad esempio la congruenza $2x \equiv 1 mod 5$ ammette soluzione per $x=3$, ma ammette soluzione anche per $x=8$ o per $x=13$ e così via. In pratica le soluzioni sono del tipo $x=3+5k$ con $k in ZZ$
Spero di essere stato chiaro.
si ok quindi un equazione di quel tipo ha infinite soluzioni proprio perchè una classe resto contiene all'interno di essa infiniti numeri e visto che quella stessa classe si puo esprimere scegliendo come rappresentanti proprio quei numeri, le soluzioni sono infinite giusto?
direi di si
ok poi ho un altra domanda..
perchè nei miei appunti c ho scritto che se io divido l equazione a. x = b ( modulo n ) per il MCD tra a ed n e quindi mi viene un equazione congruenziale equivalente ad essa tale che a ed n sono coprimi, la soluzione di questa nuova equazione sarà unica?? non capisco.. non sono sempre infinite??
perchè nei miei appunti c ho scritto che se io divido l equazione a. x = b ( modulo n ) per il MCD tra a ed n e quindi mi viene un equazione congruenziale equivalente ad essa tale che a ed n sono coprimi, la soluzione di questa nuova equazione sarà unica?? non capisco.. non sono sempre infinite??
che siano infinite ne sono sicuro. non capisco bene cosa intendesse il professore in questo caso, a meno che tu abbia preso male gli appunti...
Ah ok. Se (a,b) è diverso da 1 ci sono più classi soluzione. Ad esempio 2x=0 mod 6 ha per soluzione sia la classe 0 che la classe 3. Capito la differenza?
vorrai dire (a,n) diverso da 1..
ma quindi un equazione di questop tipo:
a x = b (modulo n)
ha infinite soluzioni non solo perchè i rappresentanti della classe [x] sono infiniti ma anche perchè puo avere piu di una classe resto come soluzione?? intesa come classe resto diversa??
mentre invece se MCD(a,n)=1 la classe resto che c è come soluzione è unica, anche se è anch'essa infinita??
ma quindi un equazione di questop tipo:
a x = b (modulo n)
ha infinite soluzioni non solo perchè i rappresentanti della classe [x] sono infiniti ma anche perchè puo avere piu di una classe resto come soluzione?? intesa come classe resto diversa??
mentre invece se MCD(a,n)=1 la classe resto che c è come soluzione è unica, anche se è anch'essa infinita??
Esatto!
si ma non ho capito una cosa se io trovo la soluzione di quella soluzione poi per trovare la soluzione dell equazione congruenziale di partenza devo moltiplicare il risultato di quest ultima per b e ok..
quindi quella sarà una soluzione della classe resto, ma non esisteranno sempre altre classi resto diverse (e nonmi riferisco semplicemente di diversi rappresentanti) di tale equazione??
quindi a che pro facciamo questo ?? ossia MCD(a,n)??
quindi quella sarà una soluzione della classe resto, ma non esisteranno sempre altre classi resto diverse (e nonmi riferisco semplicemente di diversi rappresentanti) di tale equazione??
quindi a che pro facciamo questo ?? ossia MCD(a,n)??
allora ricapitolando vi posto l'algoritmo:
se io devo risolvere tale equazione:
[A]n . [X]n = n
posso riscriverla in questo modo:
che avrà le stesse soluzioni della suddetta:
a . x = b (modulo n)
dopodichè controllo se esistono soluzioni o non esistono facendo il MCD(a,n)=d e vedendo che esso divide b.
se ciò accade vuol dire che esistono infinite soluzioni(ossia una classe resto unica, che puo essere espressa con infiniti rappresentanti).
dopodichè divido tutto tutto per di ottenendo una nuova equazione congruenziale con a ed n primi tra loro, ossia:
a/d . x = b/d (modulo n/d)
ora mi trovo la x sfruttando l'algoritmo di euclide che sarà soluzione della suddetta, e moltiplico questa soluzione per b ed ottengo la soluzione dell'equazione di partenza:
ax = b (modulo n) che naturalmente sarà la stessa soluzione di
[A]n . [X]n= n
ho fatto tutto bene? manca qualcosa?
grazie
se io devo risolvere tale equazione:
[A]n . [X]n = n
posso riscriverla in questo modo:
che avrà le stesse soluzioni della suddetta:
a . x = b (modulo n)
dopodichè controllo se esistono soluzioni o non esistono facendo il MCD(a,n)=d e vedendo che esso divide b.
se ciò accade vuol dire che esistono infinite soluzioni(ossia una classe resto unica, che puo essere espressa con infiniti rappresentanti).
dopodichè divido tutto tutto per di ottenendo una nuova equazione congruenziale con a ed n primi tra loro, ossia:
a/d . x = b/d (modulo n/d)
ora mi trovo la x sfruttando l'algoritmo di euclide che sarà soluzione della suddetta, e moltiplico questa soluzione per b ed ottengo la soluzione dell'equazione di partenza:
ax = b (modulo n) che naturalmente sarà la stessa soluzione di
[A]n . [X]n= n
ho fatto tutto bene? manca qualcosa?
grazie
spero non vi stia scocciando molto..ma io se non capisco una cosa non trovo pace 
scusatemi..
scusatemi..
per piacere aiutatemi a capire questa cosa..
Leggiti il cattaneo 'algebra' pagina 74-75-76, probabilmente lo trovi su google libri. È chiaro
ok ma mi confermi che un equazione sulle classi resto puo avere anche piu classi resto come soluzioni
mentre invece se un equazione sulle classi resto abbiamo che la a è invertibile, la classe resto della soluzione è unica (anche se pur sempre infinita)??
mentre invece se un equazione sulle classi resto abbiamo che la a è invertibile, la classe resto della soluzione è unica (anche se pur sempre infinita)??
Ciao Leonardo 20, non sono un moderatore, però penso sia giusto dirti che trovo irrispettoso il tuo comportamento nei confronti degli altri utenti. C'è una regola del forum che infrangi ripetutamente e cioè quella di fare up prima delle 24 ore. Se davvero non ti dai pace finchè non capisci una cosa cerca anche tu, da solo, di sforzarti.
Te lo dico veramente con molta tranquillità e ho fiducia che tu possa non fare più così in futuro.
Buono studio!
Te lo dico veramente con molta tranquillità e ho fiducia che tu possa non fare più così in futuro.
Buono studio!
Si è corretto quello che dici. Cmq se leggi il cattaneo ti chiarisci le idee
non lo trovo questo libro.. se mi mandi il link mi faresti un piacere
[mod="Martino"]Leonardo20, ti avviso formalmente che al prossimo UP che farai a distanza di meno di 24 ore proporro' la tua sospensione settimanale dal forum.[/mod]
ma chi lo sta facendo questo up sto rispondendo!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo