Criteri di divisibilità con le congruenze
I criteri di divisibilità dei numeri interi possono essere spiegati tramite le congruenze.
Nella notazione posizionale decimale un numero intero è composto da n cifre.
$$ z = a_n \: a_{n-1} \: ... \: a_2 \: a_1 \: a_0 $$
Esempio. Il numero z=1048 è composto da $$ a_3=1 \\ a_2=0 \\ a_1=4 \\ a_0 = 8 $$
Ogni cifra a è un numero intero compreso tra 0 e 9.
$$ a_n \cdot 10^n + a_{n-1} \cdot 10^{n-1} + ... + a_2 \cdot 10^2 + a_1 \cdot 10^1 + a_0 \cdot 10^0 $$
Esempio. Il numero z=1048 corrisponde alla somma $$ z= 1 \cdot 10^3 + 0 \cdot 10^2 + 4 \cdot 10^1 + 8 \cdot 10^0 $$
Criterio di divisibilità per 2
Un numero è divisibile per 2 se l'ultima cifra (a0) è divisibile per 2.
- 100 non è divisibile per 2 ( resto 2 )
- 101 è divisibile per 2 ( resto 0 )
La fattorizzazione di 10 è
$$ 10^1 = 2 \cdot 5 $$
Pertanto, qualsiasi numero moltiplicato per 101 o 10n con n≥1 è divisibile per 2 e per 5.
$$ a_n \cdot 10^n + ... + a_2 \cdot 10^2 + a_1 \cdot 10^1 $$
Quindi, dato un numero z qualsiasi
$$ z= a_n \cdot 10^n + ... + a_1 \cdot 10^1 + a_0 \cdot 10^0 $$
Sapendo che le cifre dalla posizione n≥1 sono tutte divisibili per 2, basta calcolare la differenza
$$ z - a_n \cdot 10^n + ... + a_2 \cdot 10^2 + a_1 \cdot 10^1 = $$
$$ = a_0 \cdot 10^0 $$
per capire che il numero z è divisibile per 2 se l'ultima cifra (a0) è divisibile per 2.
Nota. La stessa dimostrazione può essere usata per dimostrare che un numero z è divisibile per 5 se l'ultima cifra è divisibile per 5.
Criterio di divisibilità per 3
Un numero è divisibile per 3 se la somma delle sue cifre è divisibile per 3.
Ogni numero 10n-1 con n>0 è composto da n cifre 9. Quindi, è divisibile per 3 e per 9.
$$ 10^n - 1 = 999....99 $$
Esempio. Il numero 103-1 è composto da tre nove. $$ 10^3 - 1 = 1000 - 1 = 999 $$
E' una caratteristica molto importante perché mi permette di scrivere la congruenza
$$ 10^n - 1 \equiv 0 \:\:(mod \: 3) $$
Aggiungendo +1 a entrambi i membri ottengo
$$ 10^n - 1 + 1 \equiv 0 + 1 \:\:(mod \: 3) $$
$$ 10^n \equiv 1 \:\:(mod \: 3) $$
Pertanto, dato un numero intero qualsiasi
$$ z= a_n \cdot 10^n + a_{n-1} \cdot 10^{n-1} + ... + a_0 \cdot 10^0 $$
Se 10n equivale a 1 in modulo 3 posso sostituire tutti i fattori 10n con 1.
$$ z= a_n \cdot 1 + a_{n-1} \cdot 1 + ... + a_0 \cdot 1 $$
Quello che resta è la somma delle cifre del numero.
$$ z= a_n + a_{n-1} + ... + a_0 $$
Si deduce che z è divisibile per 3 se la somma delle sue cifre è divisibile per 3.
Nota. La stessa dimostrazione si può usare per il criterio di divisibilità per 9. Basta sostituire 9 a 3 per dimostrare che un numero è divisibile per 9 se la somma delle sue cifre è divisibile per 9.
Criterio di divisibilità per 4
Un numero è divisibile per 4 se le ultime due cifre a1a0 sono divisibili per 4.
- 100 non è divisibile per 4
- 101 non è divisibile per 4
- 102 è divisibile per 4
Pertanto, qualsiasi numero moltiplicato per 102 o 10n con n≥2 è divisibile per 4.
$$ a_n \cdot 10^n + a_{n-1} \cdot 10^{n-1} + ... + a_2 \cdot 10^2 \equiv 0 \:\:\: (mod \: 4) $$
Nota. La fattorizzazione del numero 100 è $$ 10^2 = 2^4 \cdot 5^2 $$.
Quindi, dato un numero qualsiasi z
$$ z = a_n \cdot 10^n + a_{n-1} \cdot 10^{n-1} + ... + a_1 \cdot 10^1 + a_0 \cdot 10^0 $$
Sapendo che le cifre dalla posizione n≥2 sono tutte divisibili per 4,
basta fare la differenza tra i due numeri
$$ z - a_n \cdot 10^n + a_{n-1} \cdot 10^{n-1} + ... + a_2 \cdot 10^2 = $$
$$ = a_1 \cdot 10^1 + a_0 \cdot 10^0 $$
Ho dimostrato che un numero z è divisibile per 4 se le ultime due cifre sono divisibili per 4.
Nota. Lo stesso criterio vale per la divisione di un numero per 25. Un numero z è divisibile per per 25 se le ultime due cifre sono divisibili per 25.
Criterio di divisibilità per 2k
Un numero è divisibile per 2k se 2k divide il numero composto dalle ultime k cifre.
Dimostrazione
Il numero 10n
$$ 10^n = 2^n \cdot 5^n $$
è divisibile per 2k per qualsiasi n≥k.
$$ a_n \cdot 10^n + ... + a_{k+1} \cdot 10^{k+1} + a_k \cdot 10^k $$
Quindi, un qualsiasi numero z
$$ z= a_n \cdot 10^n + ... + a_1 \cdot 10^1 + a_0 \cdot 10^0 $$
Sapendo che le cifre dalla posizione k sono tutte divisibili per 2k, basta calcolare la differenza
$$ z - a_n \cdot 10^n + ... + a_2 \cdot 10^2 + a_1 \cdot 10^1 = $$
$$ = a_{k-1} \cdot 10^{k-1} + ... + a_1 \cdot 10^1 + a_0 \cdot 10^0 $$
per capire che il numero z è divisibile per 2k se il numero composto dalle ultime k cifre è divisibile per 2k
Nota. Questo criterio è la generalizzazione della divisione per 2 e per 4. Può essere applicato per qualsiasi 2^k. Ad esempio, per verificare la divisibilità per 8, per 16, per 32, per 64, ecc.
Esempio
Il numero 41120 è divisibile per 8?
$$ z=41120 $$
Il numero 8 equivale a 23.
$$ 8 = 2^3 $$
Quindi analizzo le ultime k=3 cifre del numero 41120 ossia
$$ 120 $$
Il numero 120 è divisibile per 8.
$$ 8 | 120 $$
Pertanto, il numero 41120 è divisibile per 8
$$ 8 | 41120 $$
Criterio di divisione per 11
Un numero è divisibile per 11 se $$ a_0 - a_1 + a_2 - a_3 + ... + (-1)^n a_n $$ è divisibile per 11.
- 100 non è divisibile per 11 ( resto 1 )
- 101 non è divisibile per 11 ( resto 10 ossia -1 )
- 102 non è divisibile per 11 ( resto 1)
- 103 non è divisibile per 11 ( resto 10 ossia -1 )
Per n pari il coefficiente è 1 mentre per n dispari è -1.
$$ 10^{2n} \equiv 1 \mod 11 $$
$$ 10^{2n+1} \equiv -1 \mod 11 $$
Pertanto, dato un numero intero z qualsiasi
$$ z= a_n \cdot 10^n + ... + a_1 \cdot 10^1 + a_0 \cdot 10^0 $$
Sostituisco i parametri a0,a1, ... , an con i rispettivi valori 1 e -1,
$$ z= a_n \cdot (-1)^{n} + ... + a_1 \cdot (-1) + a_0 \cdot (1) $$
Il numero z è divisibile per z se la precedente somma algebrica è divisibile per 11.
Esempio
Il numero 1364 è divisibile per 11?
$$ z = 1364 $$
Calcolo la somma algebrica moltiplicando per -1 le posizioni dispari.
$$ 1 \cdot (-1) + 3 + 6 \cdot (-1) + 4 $$
$$ = -1 + 3 - 6 + 4 = 0 $$
Il numero 1364 è divisibile per 0 perché
$$ 0 \equiv 0 \mod 11 $$
E così via.
