Equazioni di congruenze

[Timmy1]

Ciao ragazzi,
il prof di Discreta 2 ha spiegato le equazioni ed i sistemi di equazioni delle congruenze ma io, essendo stato assente per motivi di salute, c'ho capito ben poco.

Chi mi aiuta a capirci qualcosa?

GRAZIEEEEEEEEEEE

[Luca.Lussardi]

Prova a cercare il Teorema cinese del resto; e' praticamente l'unico risultato interessante che permette la risoluzione dei sistemi di congruenze.

[Timmy1]

E per le equazioni?

[Luca.Lussardi]

Le equazioni sono abbastanza elementari, si sfruttano proprieta' di base delle congruenze. A quanto ricordo io l'unico strumento non banale in questa teoria e' solo il Teorema cinese del resto. Ma se hai capito bene le congruenze, non dovresti aver problemi sulle equazioni con congruenze.

[Timmy1]

Data una congruenza del tipo:

ax = b (mod n)

I passi per risolverla sono:
1) MCD tra a ed n
2) Controllare se ha soluzioni (quindi se il MCD divide b)
3) E poi come devo continuare?

[TomSawyer1]

A questo punto, $x'$ è una soluzione sse $x\equiv x'(mod n/d)$, con $x$ una soluzione specifica.

[TomSawyer1]

Due possibilità:

1) $\gcd(a,n)=1$. In questo caso, basta moltiplicare tutto per l'inverso di $a$ modulo $n$ e arrivi ad avere $x\equiv a^(-1)b(modn)$.

2) $d:=\gcd(a,n)>1$. Verifichi se $d|b$, e, se è vero, allora puoi ridurre la congruenza a $a/d x\equiv b/d (mod n/d)$.