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...
