Mettiamo ordine, ok?
Def: Fissato $ m $ numero intero, due interi $ a,\ b $ si dicono
congrui modulo m e si scrive
$ a\equiv b\mod m $
se $ m\vert a-b $ (ovvero se m divide a-b).
Modi equivalenti di dirlo sono: $ a=b+km $ per qualche intero k; a,b hanno lo stesso resto nella divisione per m.
Somma, differenza, moltiplicazione
Se $ a\equiv b\mod m $ e $ c\equiv d\mod m $, allora
- $ a+c\equiv b+d\mod m $
- $ a-c\equiv b-d\mod m $
- $ ac\equiv bd\mod m $
Dim: Si ha $ a=b+km $ e $ c=d+hm $ per certi interi h,k. Allora
$ b+d=(a+c)+(h+k)m $
$ b-d=(a-c)+(k-h)m $
$ bd=ac+(ah+ck+hkm)m $
e queste sono proprio le tre conclusioni a cui volevamo arrivare.
Osservazione
Se $ p(x)=a_0x^n+\ldots+a_n $ è un polinomio a coefficienti interi, allora
$ a\equiv b\mod m $ implica $ p(a)\equiv p(b)\mod m $.
Dim: E' ben noto che $ a-b \vert p(a)-p(b) $ e dunque, se $ m\vert a-b $, allora $ m\vert p(a)-p(b) $.
(L'osservazione si può anche dimostrare osservando che valutare un polinomio in a vuol dire fare solo somme e prodotti; se dunque b è congruo ad a, facendo le stesse somme e gli stessi prodotti con b al posto di a si ottiene lo stesso risultato modulo m).
Generalizzazione 1
Se $ p(x,y) $ è un polinomio a coefficienti interi in due variabili, allora $ a\equiv b\mod m $ e $ c\equiv d\mod m $ implicano $ p(a,c)\equiv p (b,d)\mod m $.
Dim: Scriviamo
$ p(x,y)=\sum_{i,j} \alpha_{ij}x^iy^j $ (con $ \alpha_{ij} $ interi)
allora, se $ a\equiv b\mod m $ e $ c\equiv d\mod m $, si ha
$ a^i\equiv b^i\mod m $, $ c^j\equiv d^j\mod m $ e dunque
$ a^ic^j\equiv b^id^j\mod m $ e, poichè $ \alpha_{ij}\equiv \alpha_{ij}\mod m $ (ogni intero è congruo a se stesso), si ha
$ \alpha_{ij}a^ic^j\equiv \alpha_{ij}b^id^j\mod m $
per ogni monomio di p(x,y); quindi sommandoli tutti otteniamo
$ p(a,c)\equiv p(b,d)\mod m $.
(Questa cosa si estende al caso di polinomi in n variabili, purché a coefficienti interi).
Generalizzazione 2
Se $ a_i\equiv b_i\mod m $ per $ i=0,\ldots, n $, allora, posto
$ p(x)=a_0x^n+\ldots+a_n $ e $ q(x)=b_0x^n+\ldots+b_n $,
si ha che $ k\equiv h\mod m $ implica
$ p(k)\equiv q(h)\mod m $
Dim: $ k\equiv h\mod m $ e dunque $ k^i\equiv h^i\mod m $ e dunque $ a_{n-i}k^i\equiv b_{n-i}h^i\mod m $ e infine sommando su i si ottiene la tesi.
Si possono mettere assieme le due generalizzazioni, ma dovrebbe essere abbastanza ovvio, per cui evito di scriverlo con precisione; il succo è che se due polinomi in più variabili hanno i coefficienti dei monomi corrispondenti congrui modulo m e vengono calcolati in valori congrui modulo m, anche i risultati saranno congrui modulo m.
Esempi
1) $ x\equiv y\mod m $ implica $ x^n\equiv y^n\mod m $ per ogni n, quindi per sapere quali sono le n-esime potenze modulo m, basta calcolare quelle di m numeri che rappresentino tutti i possibili resti (ad esempio {0,1,...,m-1}).
2) $ (x+y)^p\equiv x^p+y^p\mod p $ con p numero primo.
Si ha $ (x+y)^p=\sum_{k=0}^p{p\choose k}x^ky^{p-k} $
e si osserva che $ p\not\vert k!(p-k)! $ se p>k>0 e dunque $ p\vert {p\choose k} $ se p>k>0. Quindi
$ (x+y)^p=x^p+ p(\ldots)+y^p $
ovvero
$ (x+y)^p\equiv x^p+y^p\mod p $
Esercizio Dimostrare che $ x^2-46x+1 $ è sempre un quadrato modulo 24. Ovvero che, per ogni x intero, esiste un y intero tale che $ x^2-46x+1\equiv y^2\mod 24 $.
Cosa non si può fare
Non si può dividere, in generale:
$ 2\equiv 12\mod 10 $ e $ 2\equiv 2\mod 10 $ ma $ 1\not\equiv6\mod 10 $.
$ 18\equiv 60\mod 14 $ e $ 6\equiv 6\mod 14 $ ma $ 3\not\equiv10\mod14 $
Non si può ridurre l'esponente di un elevamento a potenza modulo m:
$ 3\equiv 6\mod 3 $ e $ 2\equiv2\mod 3 $ ma $ 2^3\equiv2\mod 3 $ mentre $ 2^6\equiv1\mod 3 $
$ 9\equiv 2\mod 7 $ e $ 3\equiv 10\mod 7 $ ma $ 9^3\equiv1\mod 7 $ mentre $ 2^{10}\equiv2\mod 7 $
Quando si può dividere
Se $ (m,c)=1 $ allora esiste un numero $ d $ tale che $ cd\equiv 1\mod m $ (perché?); allora, se $ a\equiv b\mod m $, ha senso dire che $ a/c\equiv b/c\mod m $ intendendo che $ c^{-1}\equiv d\mod m $ (è quel numero che moltiplicato per c fa 1, è il suo inverso modulo m); dunque si sta solo dicendo che $ ad\equiv bd\mod m $.
Se dunque $ a\equiv b\mod m $ e $ x=(a,b) $, nel caso in cui $ (m,x)=1 $, allora si può dire $ a/x\equiv b/x\mod m $.
Ad esempio, $ 3\equiv24\mod 7 $ e poichè (3,7)=1 (dove 3=(3,24)), vale anche $ 1\equiv 8\mod 7 $.
Se invece c'è un fattore d comune ad a,b,m, ovvero se $ a=da',\ b=db',\ m=dm' $, e vale $ a\equiv b\mod m $ allora possiamo "dividere" solo dividendo anche il modulo:
$ (a/d)\equiv(b/d)\mod (m/d) $ ovvero $ a'\equiv b'\mod m' $.
Ad esempio, $ 2\equiv 10\mod 8 $ implica $ 1\equiv 5\mod 4 $.
Per ridurre gli esponenti il discorso si fa più complicato e probabilmente c'è già da qualche altra parte nel glossario.
...