Oooooocchei... Forse commosso dalle disperate richieste d'aiuto di alcuni utenti (vedi ad esempio qui!), mi prendo io la briga di buttare giù un po' di roba che riguardi la teoria di base delle congruenze e della divisibilità sugli interi. Spero quantomeno che possa risultare utile e gradito...
Definizione: se $ m, n \in\mathbb{Z} $, diciamo che $ m $ divide $ n $, o ancora che $ m $ è un divisore di $ n $, ovvero che $ n $ è divisibile per $ m $, e scriviamo $ m \mid n $, sse esiste $ q\in\mathbb{Z} $ tale che $ n = mq $.
Sussiste allora il seguente risultato fondamentale, su cui si basa sostanzialmente tutta la teoria delle congruenze.
Teorema (del quoziente): se $ m, n \in \mathbb{Z} $ ed $ m \neq 0 $, esistono univocamente determinati $ q, r \in \mathbb{Z} $, con $ 0 \leq r < |\, m \,| $, tali che $ n = mq + r $.
Con riferimento all'enunciato precedente, si dice che $ q $ è il quoziente ed $ r $ è il resto della divisione (intera) di $ n $ per $ m $. Ebbene...
Definizione: se $ a, b, m \in \mathbb{Z} $ ed $ m \neq 0 $, si dice che $ a $ è congruo (o congruente) a $ b $ modulo $ m $, e si scrive $ a \equiv b \bmod m $, sse $ m \mid (a-b) $.
Valgono le seguenti proprietà fondamentali:
Proprietà 1: se $ a, m \in \mathbb{Z} $, con $ m \neq 0 $: $ a \equiv a \bmod m $.
Proprietà 2: se $ a, b, m \in \mathbb{Z} $, con $ m \neq 0 $: $ a \equiv b \bmod m $ sse $ b \equiv a \bmod m $.
Proprietà 3: se $ a, b, c, m \in \mathbb{Z} $, con $ m \neq 0 $: $ a \equiv b \bmod m $ e $ b \equiv c \bmod m\mbox{ }\;\,\Longrightarrow\mbox{ }a \equiv c \bmod m $.
Le proprietà 1), 2) e 3) stabiliscono che la relazione di congruenza modulo $ m $, per ogni fissato intero $ m \neq 0 $, è una relazione di equivalenza sull'insieme $ \mathbb{Z} $. Per quelli (come me) che giusto un poco se n'intendonodi insiemistica, dico che l'insieme quoziente corrispondente si denota con $ \mathbb{Z}/m\mathbb{Z} $, o talvolta con $ \mathbb{Z}_m $, sebbene questa notazione sia per lo più deprecata, poiché si riserva piuttosto per indicare l'insieme degli interi $ m $-adici, quando $ m $ sia un numero primo.
Proprietà 4: se $ a, b, c, m \in \mathbb{Z} $ ed $ m \neq 0 $: $ a \equiv b \bmod m $ sse $ a + c \equiv b + c \bmod m $.
Proprietà 5: se $ a, b, c, d, m \in \mathbb{Z} $ ed $ m \neq 0 $: $ a \equiv b \bmod m $ e $ c \equiv d \bmod m\mbox{ }\;\,\Longrightarrow\mbox{ }a + c \equiv b + d \bmod m $.
Proprietà 6: se $ a, b, c, m \in \mathbb{Z} $ ed $ mc \neq 0 $: $ a \equiv b \bmod m\mbox{ }\;\,\Longrightarrow\mbox{ }ac \equiv bc \bmod mc $.
Proprietà 7: se $ a, b, m, n \in \mathbb{Z} $, $ mn \neq 0 $ ed $ n \mid m $: $ a \equiv b \bmod m\mbox{ }\;\,\Longrightarrow\mbox{ }a \equiv b \bmod n $.
Proprietà 8: se $ a, b, c, m \in \mathbb{Z} $ ed $ m \neq 0 $: $ a \equiv b \bmod m\mbox{ }\;\,\Longrightarrow\mbox{ }ac \equiv bc \bmod m $.
Proprietà 9: se $ a, b, c, m \in \mathbb{Z} $ ed $ mc \neq 0 $: $ ac \equiv bc \bmod m\mbox{ }\;\,\Longrightarrow\mbox{ }a \equiv b \bmod m/\gcd(m,c) $.
Proprietà 10 (MOLTO UTILE): se $ a, b, c, m \in \mathbb{Z} $, $ m \neq 0 $ e $ c $ è primo con $ m $: $ ac \equiv bc \bmod m\mbox{ }\;\,\Longrightarrow\mbox{ }a \equiv b \bmod m $.
Proprietà 11: se $ a, b, c, d, m \in \mathbb{Z} $ ed $ m \neq 0 $: $ a \equiv b \bmod m $ e $ c \equiv d \bmod m\mbox{ }\;\,\Longrightarrow\mbox{ }ac \equiv bd \bmod m $.
Proprietà 12: se $ a, b, m \in \mathbb{Z} $, $ k\in\mathbb{N} $ ed $ m \neq 0 $: $ a \equiv b \bmod m\mbox{ }\;\,\Longrightarrow\mbox{ }a^k \equiv b^k \bmod m $.
Proprietà 13: se $ a, b, m, n \in \mathbb{Z} $ ed $ mn \neq 0 $: $ a \equiv b \bmod m $ ed $ a \equiv b \bmod n\mbox{ }\;\,\Longrightarrow\mbox{ }a \equiv b \bmod \mbox{mcm}(m,n) $.
Bene, siete invitati a dimostrare una per una le 13 proprietà che ho qui sopra elencato. Vi raccomando d'essere altamente "sequenziali": non è un caso se le ho riportate giusto secondo quest'ordine... Ah, per concludere:
Proprietà 14 (SPESSO UTILE): se $ m,n \in \mathbb{Z} $ ed $ m \neq 0 $, allora $ n \equiv r \bmod m $, dove $ r $ è il resto della divisione intera di $ n $ per $ m $. Dunque $ m \mid n $ sse $ n \equiv 0 \bmod m $.
P.S.: segnalate pure eventuali inconsistenze notazionali, svarioni tipografici ed errori di ogni sorta. Grazie...