Congruenze

Messaggioda Robin » 24/11/2003, 15:29

Qualcuno è così gentile da spiegarmi come si possono risolvere le equazioni alle congruenze modul m?
Robin
Starting Member
Starting Member
 
Messaggio: 2 di 41
Iscritto il: 20/11/2003, 12:42

Messaggioda karl » 24/11/2003, 17:06

Ecco quanto ho racimilato(il segno "=" sta per "congruente"):
1) Se f(x)=0 (mod m) allora i coefficienti di f(x) si possono
sostituire ( in valore e segno) con i loro resti rispetto ad m.
Es: 3x^3-5x+4=0,(mod m)-->-4x^3+2x-3=0 (mod m).
2)Due radici di f(x)=0 (mod m) che siano congrue rispetto
ad m non vengono considerate distinte.Ne segue che
la congruenza (condizionale) f(x)=0 ( mod m) non puo'
avere piu' di m radici che sono (eventualmente)
0,1,2,.....,m-1).
Pertanto si puo' risolvere la congruenza per tentativi
provando quale di questi numeri siddisfa la congr.
Se poi "a" e' una radice si ottiene
una classe di soluzioni con la formula x=a+t*m (t= intero
relativo qualunque).
3) per le congruenze di primo grado(ax=b ,mod m) esistono procedimenti predefiniti:
a)se mcd(a,m) =1 ,cioe' se a ed m sono primi tra loro,allora
la soluzione e':x=b*a^(w(m)-1) dove w(m) e' l'indicatore di
Gauss ovvero il numero dei numeri primi con m e <=m.
Es 16x=9 ,mod 19--->x=9*16^(17) perche' w(19)=18.Successivamente
riducendo risulta (x=-3 ,mod 19)-->soluzione generale=16+t*19.
b)se mcd(a,m)<>1 allora vi sono soluzioni solo se b e' divisibile per
d= mcd(a,m) e la soluzione e' :
(x=(b/d)*(a/d)^(w(m)-1)+t*(m/d) ,mod m t=0,1,2 d-1).
Es.:
72x=132 ,mod 156
d=mcd(72,156)=12.Poiche' 132 e' divisibile per 12 vi sono soluz.
Si ha:
6x=11,mod 13( ora a ed m sono primi tra loro e si ricade nel caso a)
x=11*6^(11)-->x=4,mod 13.Soluzione generale=4+13t,mod 156 con t=0,1,2,...,12.
Scusa l'esposizione un po' confusa.
karl
 


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite