In aritmetica, i criteri di divisibilità sono degli algoritmi utilizzati per determinare la divisibilità di un numero intero per un certo fattore, senza la necessità di eseguire una divisione esplicita.
Questi criteri si basano su una serie di operazioni eseguite sulle cifre che compongono il numero. Tali operazioni dovrebbero essere sufficientemente semplici da potersi fare a mente o comunque essere più veloci rispetto alla divisione.
Poiché i criteri di divisibilità operano direttamente sulle cifre del numero, la loro applicabilità dipende dalla base in cui il numero è espresso. In pratica, si considerano solamente i criteri per i numeri espressi in base 10. Quando un criterio si riferisce alle "ultime cifre", si intende sempre quelle posizionate più a destra.
Alcuni criteri si limitano a dare un risultato sì/no, mentre altri permettono anche di determinare il resto della divisione, poiché calcolano il modulo, e il numero dato è divisibile se e solo se tale resto è 0. Può essere necessaria una lieve modifica rispetto alla loro formulazione tradizionale. Ad esempio, il criterio di divisibilità per 2 può essere espresso nella forma: il resto della divisione di un numero per 2 è uguale al resto della divisione dell'ultima cifra di per 2 (quindi è divisibile per 2 se e solo se tale resto è 0).
Inoltre, vale la regola generale secondo cui, se un numero è divisibile per allora è divisibile anche per ogni divisore di Viceversa, se è divisibile per , , allora è divisibile anche per il minimo comune multiplo di , . Ad esempio, un numero è divisibile per 6 se e solo se è divisibile sia per 2 sia per 3. Usando questa regola, se la fattorizzazione di in primi distinti è , allora un numero è divisibile per se e solo se è divisibile per ognuno dei fattori . È quindi sufficiente considerare i criteri di divisibilità per i numeri primi e per le potenze di primi. Ad esempio, poiché , un numero è divisibile per 792 se e solo se è divisibile per 8, per 9 e per 11.
Principali criteri di divisibilità dei numeri interi
Divisibilità per 0
Nessun numero è divisibile per 0.
Divisibilità per 1 Tutti i numeri sono divisibili per 1.
Divisibilità per 2 Un numero è divisibile per 2 se e solo se è pari, ovvero se la sua ultima cifra è 0, 2, 4, 6 oppure 8.
Dimostrazione: si consideri un numero ; le sue cifre decimali sono i coefficienti ai che compaiono nella somma:
i termini sono tutti divisibili per 2 se , quindi se è divisibile per 2 lo è anche:
cioè , che quindi è 0, 2, 4, 6 o 8.
Viceversa se è 0, 2, 4, 6 o 8, una volta che lo sommiamo al numero:
che è anch'esso divisibile per 2, otteniamo ancora un multiplo di 2, dunque sarà divisibile per 2.
Esempio: 26 è divisibile per 2 perché finisce con 6.
Vedi anche divisione per due.
La divisibilità o meno per 2, divide i numeri interi in due categorie: i numeri pari, che sono divisibili per 2, e i numeri dispari, che non lo sono.
Divisibilità per una potenza di 2 Più in generale, un numero è divisibile per se lo è il numero costituito dalle cifre più a destra del numero.
Dimostrazione: si rappresenti un qualunque numero naturale nella forma dove indica il numero costituito dalle prime k cifre di destra ed il numero costituito dalle rimanenti cifre alla sinistra di . Se si dividono entrambi i membri per risulta, poiché è un numero intero, che la divisibilità di per dipende solo dalla divisibilità di .
Divisibilità per 3 Un numero è divisibile per 3 se la somma di tutte le sue cifre è pari a 3 o ad un suo multiplo (6, 9); nel caso in cui tale somma sia un numero maggiore di 9, se ne sommano nuovamente le cifre e si verifica che quest'ultimo risultato sia divisibile per 3.
Esempio: per verificare se 493827 è divisibile per 3, sommando le cifre che compongono il numero (4+9+3+8+2+7), si ottiene 33, che è maggiore di 9, quindi si sommano le cifre di 33 (3+3), ottenendo 6: poiché 6 è un multiplo intero di 3, il numero di partenza è divisibile per 3.
Altro esempio: per verificare se 32565 è divisibile per 3, basta eseguire la somma: 3+2+5+6+5 = 21, che è maggiore di 9, e sommando nuovamente le sue cifre si ha 2+1 = 3; dato che 3 è divisibile per 3, allora anche 32565 lo è.
Dimostrazione: si consideri un numero ; le sue cifre decimali sono i coefficienti che compaiono nella somma: . Supponiamo che la somma
sia divisibile per 3; questo si può tradurre in aritmetica modulare dicendo che:
ovvero: . Sostituendo in si ha:
che risulta essere un multiplo di 3.
Divisibilità per 4 Un numero è divisibile per 4 se le ultime due cifre sono due zeri oppure formano un numero multiplo di 4, oppure se le ultime due cifre sono tali che la penultima è dispari e l'ultima è 2 oppure 6, oppure la sua penultima cifra è pari e l'ultima è 0, 4 oppure 8.
Dimostrazione: sia un numero le sue cifre decimali sono i coefficienti che compaiono nella somma: . Se il numero finisce per 00 è divisibile per 100, che a sua volta è divisibile per 4. Supponiamo che le ultime due cifre
formino un multiplo di 4; in ogni caso anche le cifre rimanenti:
formeranno un multiplo di 4 (in quanto formano un multiplo di 100) quindi anche la loro somma, cioè è multiplo di 4.
Esempio: 424 è divisibile per 4 perché le ultime 2 cifre sono 2 e 4, che formano 24, che è multiplo di 4.
Divisibilità per 5 Un numero è divisibile per 5 se la sua ultima cifra è 0 oppure 5.
Dimostrazione: si consideri un numero le sue cifre decimali sono i coefficienti che compaiono nella somma:
i termini sono tutti divisibili per 5 se quindi se è divisibile per 5 lo è anche:
cioè , che quindi è 0 o 5.
Viceversa se è 0 o 5 una volta che lo si somma al numero:
che è anch'esso divisibile per 5, si ottiene ancora un multiplo di 5, dunque sarà divisibile per 5.
Esempio: 565 è divisibile per 5 perché finisce con 5.
Divisibilità per una potenza di 5 Similmente al caso con le potenze di 2, un numero è divisibile per se lo è il numero formato dalle cifre più a destra del numero.
Divisibilità per 7 Analizzeremo di seguito tre differenti criteri di divisibilità per questo caso, con il primo caso suddivisibile in due sottovarianti.
Vale la pena anticipare che, per rapidità di calcolo, l'uso del secondo criterio B) risulta essere il migliore, ancor più se accoppiato alla variante per i Numeri Grandi, come verrà mostrato.
A.1) Primo criterio, prima variante: con separazione dell'ultima cifra (quella delle unità).
Enunciato: "Un numero è divisibile per 7 se la somma tra il numero ottenuto escludendo la cifra delle unità (prenumero) e il quintuplo della cifra delle unità (coda numerica) è multiplo di 7".
Esempio: 68089; calcoliamo 6808 + 9×5 = 6853; non sapendo se 6853 sia divisibile per 7 basta ripetere la procedura. 685 + 3×5 = 700, che è evidentemente un multiplo di sette. Pertanto 68089 è multiplo di 7.
Dimostrazione: si consideri un numero le sue cifre decimali sono i coefficienti che compaiono nella somma:
che possiamo scrivere più sinteticamente: . Nel linguaggio dell'aritmetica modulare è noto che è divisibile per 7 se e solo se:
ovvero: . Se si moltiplica tutto per 5 (che è l'inverso aritmetico di 10 modulo 7) abbiamo:
ovvero:
da cui: .
Dato che appartiene alla stessa classe resto di 5 modulo 7, il criterio sopra definito può essere modificato in una seconda variante, secondo quanto segue.
A.2) Primo criterio, seconda variante: con separazione dell'ultima cifra (quella delle unità).
Enunciato: "Un numero è divisibile per 7 se la differenza tra il numero ottenuto escludendo la cifra delle unità (prenumero) ed il doppio della cifra delle unità (coda numerica) è multiplo di 7".
Utilizzando lo stesso esempio "68089" è possibile infatti vedere che: 6808-9×2=6790; 679-0×2=679; 67-9×2=49, numero divisibile per 7: da cui la divisibilità del numero iniziale per 7 è confermata.
Va ricordato che questi criteri (al contrario dei successivi) non consentono il calcolo del resto della divisione per 7, solo la verifica della divisibilità.
Un altro metodo per determinare la divisibilità per 7, come quello per 13, sfrutta anche il fatto che 1001 è fattorizzabile come 7 × 11 × 13, e quindi si può iniziare a ridurre il numero dato a uno con al più tre cifre (vedi sotto il criterio di divisibilità per 1001). Tali cifre, prese da destra a sinistra, devono essere moltiplicate rispettivamente per 1, 3 e 2 (mnemonicamente si può vedere la cosa come "legge 132") e i risultati sommati tra di loro.
La divisibilità per 7 può anche essere determinata prendendo la cifra più a sinistra del numero, moltiplicarla per 3 e sommarla a quella immediatamente più a destra, eliminando eventuali fattori 7 e continuando fino alla cifra più a destra.
Nell'esempio del numero 493827, le operazioni da compiere sono:
×4 × 3 + 9 = 21 0;
×0 × 3 + 3 = 3;
×3 × 3 + 8 = 17 3;
×3 × 3 + 2 = 11 4;
×4 × 3 + 7 = 19 5.
Il risultato finale è proprio il resto della divisione del numero per 7: se tale risultato è 0 il numero è dunque divisibile per 7. La stessa operazione si può anche fare da destra a sinistra; in questo caso il moltiplicatore è 5.
Per Numeri Grandi, è possibile dividerli in gruppi di tre cifre da destra a sinistra, inserendo segni alternati fra ogni gruppo: il risultato deve essere divisibile per 7.
Esempio: vediamo se 1491826 è divisibile per 7.
Scomponiamo il numero in gruppi di tre cifre, partendo da destra, alternandone i segni: 1491826: 826 - 491 + 1 = 336 e, utilizzando uno dei criteri precedenti, 33 + (6 × 5) = 63 quindi è divisibile.
Un ulteriore criterio di divisibilità per 7 è il seguente, assai facile da usare:
si divide il numero in esame in gruppi di tre cifre operando da destra verso sinistra e di ciascuno si calcola il resto della divisione per 7; si sommano i resti dei gruppi di posto dispari e dei gruppi di posto pari: se la differenza delle due somme è nulla o un multiplo di 7 il numero di partenza è divisibile per 7.
Si consideri come esempio il numero 123457789: il resto di 123:7 è 4, il resto di 457:7 è 2, il resto di 789:7 è 5; la somma dei resti dei gruppi di posto dispari è 4+5=9 e la somma dei resti dei gruppi di posto pari è 2 (c'è un solo gruppo); poiché 9-2=7 il numero di partenza è divisibile per 7. Per calcolare il resto della divisione di un numero per 7 si ricordi che il resto non cambia se si sottrae al numero di partenza un multiplo di 7: ad esempio 723:7 dà lo stesso resto di (723-700):7 ovvero 23:7 il cui resto è assai più facile da calcolare.
Si può anche dividere il numero in esame in due gruppi di cifre, le tre cifre di destra e le rimanenti cifre, ed applicare il medesimo criterio. Sia il numero 123457789 (già considerato sopra): il resto di 123457:7 è 5, il resto di 789:7 è 5; la differenza dei resti è nulla e pertanto il numero di partenza è divisibile per 7.
Per i numeri non divisibili per 7, la citata differenza tra le somme dei resti dei gruppi di posto dispari e dei gruppi di posto pari fornisce anche il resto della divisione del numero di partenza per 7 (con l'accortezza di aggiungere 7 in caso di differenza negativa e di sottrarre 7 - o multipli di 7 - in caso di differenza maggiore di 6).
B) Secondo criterio: con separazione delle ultime due cifre (quella della decina e quella delle unità)
Enunciato: "Un numero è divisibile per 7 se e solo se la somma tra il doppio del numero ottenuto escludendo le ultime due cifre (decine ed unità) e il numero composto dalle sole ultime due cifre è 7 o un multiplo di 7; il criterio può essere ripetuto ricorsivamente".
Esempio: verificare se 53158 sia divisibile per 7.
53158: 531×2 + 58 = 1120;
e, ricorsivamente:
1120: 11×2 + 20 = 42;
poiché 42 è divisibile per 7, anche 53158 lo sarà.
Dimostrazione: