Criteri di divisibilità

Da Wikipedia, l'enciclopedia libera.

In aritmetica, i criteri di divisibilità sono degli algoritmi che permettono di verificare la divisibilità di un numero per un fattore senza eseguire la divisione esplicita.

Consistono in una serie di operazioni sulle cifre che compongono il numero. Tali operazioni dovrebbero essere sufficientemente semplici da potersi fare a mente, o comunque essere più rapide rispetto alla divisione.

Poiché i criteri di divisibilità manipolano direttamente le cifre del numero, dipendono dalla base in cui il numero viene espresso. In pratica però si considerano solamente i criteri per i numeri in base 10. Alcuni criteri permettono anche di conoscere il resto della divisione, e quindi calcolano il modulo, altri si limitano a dare un risultato sì / no.

Inoltre, vale la regola generale per cui un numero è divisibile per X se lo è contemporaneamente per tutti i fattori di X. Così si può affermare ad esempio che un numero è divisibile per 6 se lo è sia per 2 che per 3. Nel caso il criterio parli di "ultime cifre", si intende sempre quelle più a destra.

[modifica] Principali criteri di divisibilità dei numeri interi

[modifica] Divisibilità per 2

Un numero è divisibile per 2 se e solo se la sua ultima cifra decimale è pari, vale a dire 0, 2, 4, 6, 8.

dimostrazione: consideriamo un numero N, le sue cifre decimali sono i coefficienti a_i che compaiono nella somma

N = a 0 + a 1 10 + a 2102 + a 3103 + ... + a k 10 k

i termini a_i10ⁱ sono tutti divisibili per 2 se i>0, quindi se N è divisibile per 2 lo è anche

N - (a 1 10 + a 2102 + a 3103 + ... + a k 10 k)

cioè a₀, che quindi è 0, 2, 4, 6 o 8.

Viceversa se a₀ è 0, 2, 4, 6 o 8 una volta che lo sommiamo al numero

(a 1 10 + a 2102 + a 3103 + ... + a k 10 k)

che è anc'esso divisibile per 2 otteniamo ancora un multiplo di 2, dunque N sarà divisibile per 2.

[modifica] Divisibilità per una potenza di 2

Più in generale, un numero è divisibile per $2 k$ se lo sono le k cifre decimali più a destra del numero.

[modifica] Divisibilità per 3

Un numero è divisibile per 3 se lo è la somma delle sue cifre. Nel caso tale somma sia un numero maggiore di 9, si può reiterare l'operazione. Quindi ad esempio da 493827 si ottiene 33 e da qui 6. Il risultato è pari al resto modulo 9, e se lo si divide per 3 si può anche ottenere il resto modulo 3; inoltre non è necessario sommare eventuali cifre 9 presenti nel numero.

dimostrazione: consideriamo un numero N, le sue cifre decimali sono i coefficienti a_i che compaiono nella somma

N = a 0 + a 1 10 + a 2102 + a 3103 + ... + a k 10 k

supponiamo che la somma

a 0 + a 1 + a 2 + a 3 + ... + a k

sia divisibile per 3, questo si può tradurre in aritmetica modulare dicendo che

$a_0+a_1+a_2+a_3+...+a_k\equiv 0 \pmod{3}$

ovvero

$a_0\equiv -(a_1+a_2+a_3+...+a_k)\pmod{3}$

sostituendo in N si ha

$N\equiv -(a_1+a_2+a_3+...+a_k)+a_1 10+a_2 10^2+a_3 10 ^3+...+a_k 10^k\equiv 9 a_1+99a_2+...+(10^k-1)a_k$

che risulta evidentemente essere un multiplo di 3.

[modifica] Divisibilità per 4

Un numero è divisibile per 4 se le ultime due cifre sono 00 oppure formano un numero multiplo di 4, o equivalentemente le ultime due cifre sono tali che la sua penultima è dispari e l'ultima è 2 oppure 6, oppure la sua penultima cifra è pari e l'ultima è 0, 4, 8.

dimostrazione: consideriamo un numero N, le sue cifre decimali sono i coefficienti a_i che compaiono nella somma

N = a 0 + a 1 10 + a 2102 + a 3103 + ... + a k 10 k

Se il numero finisce per 00 è divisibile per 100 che a sua volta è divisibile per 4.

Supponiamo che le ultime due cifre

a 0 + a 110

formino un multiplo di 4; in ogni caso anche le cifre rimanenti

a 2102 + a 3103 + ... + a k 10 k

formeranno un multiplo di 4 (in quanto formano un multiplo di 100), quindi anche la loro somma, cioè N, è multiplo di 4.

[modifica] Divisibilità per 5

Un numero è divisibile per 5 se la sua ultima cifra è 0 oppure 5.

dimostrazione: consideriamo un numero N, le sue cifre decimali sono i coefficienti a_i che compaiono nella somma

N = a 0 + a 1 10 + a 2102 + a 3103 + ... + a k 10 k

i termini a_i10ⁱ sono tutti divisibili per 5 se i>0, quindi se N è divisibile per 5 lo è anche

N - (a 1 10 + a 2102 + a 3103 + ... + a k 10 k)

cioè a₀, che quindi è 0 o 5.

Viceversa se a₀ è 0o 5 una volta che lo sommiamo al numero

(a 1 10 + a 2102 + a 3103 + ... + a k 10 k)

che è anc'esso divisibile per 5 otteniamo ancora un multiplo di 5, dunque N sarà divisibile per 5.

[modifica] Divisibilità per una potenza di 5

Similmente al caso con le potenze di 2, un numero è divisibile per $5 k$ se lo sono le k cifre più a destra del numero.

[modifica] Divisibilità per 6

Un numero è divisibile per 6 se lo è contemporaneamente per 2 e per 3.

[modifica] Divisibilità per 7

Il criterio di divisibilità per 7, come quello per 13, sfrutta 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. 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.

Partendo ad esempio da 493827, otteniamo pertanto prima 334, poi (4 × 1 + 3 × 3 + 3 × 2) = 4 + 9 + 6 = 19, da cui ricaviamo che il resto della divisione per 7 è 5. Se ci si ricorda di cambiare il segno a ogni gruppo di cifre, è anche possibile saltare la prima riduzione del numero a uno di tre cifre.

Un altro criterio di divisibilità per 7 consiste nel prendere 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 493837, le operazioni da compiere sono:

4 × 3 + 9 = 21 $\rarr$ 0;
0 × 3 + 3 = 3;
3 × 3 + 8 = 17 $\rarr$ 3;
3 × 3 + 2 = 11 $\rarr$ 4;
4 × 3 + 7 = 19 $\rarr$ 5.

La stessa operazione si può anche fare da destra a sinistra; in questo caso il moltiplicatore è 5.

[modifica] Divisibilità per 8

Un numero è divisibile per 8 se termina con tre zeri o se lo è il numero formato dalle sue ultime 3 cifre.

[modifica] Divisibilità per 9

Un numero è divisibile per 9 se lo è la somma delle sue cifre. Nel caso tale somma sia un numero maggiore di 9, si può reiterare l'operazione.

Quindi ad esempio da 493827 si ottiene 33 e da qui 6. Il risultato è pari al resto modulo 9, e se lo si divide per 3 si può anche ottenere il resto modulo 3; inoltre non è necessario sommare eventuali cifre 9 presenti nel numero.

[modifica] Divisibilità per 10

Un numero è divisibile per 10 se la sua ultima cifra è 0.

[modifica] Divisibilità per 11

Un numero è divisibile per 11 se lo è la somma delle sue cifre prese con segno alterno.

Prendendo ad esempio 493827, bisogna fare 7 - 2 + 8 - 3 + 9 - 4, che dà 15, che a sua volta dà 4. Se si fanno le operazioni nell'ordine corretto, il risultato ottenuto è il resto modulo 11. Nel caso durante l'operazione si ottenga un numero negativo si può sempre sommare 11 per rimanere con valori positivi.

dimostrazione: consideriamo un numero N, le sue cifre decimali sono i coefficienti a_i che compaiono nella somma

N = a 0 + a 1 10 + a 2102 + a 3103 + ... + a k 10 k

supponiamo che la somma delle sue cifre prese con segno alterno sia un multiplo di 11 ovvero, nel linguaggio dell'aritmetica modulare

$a_0+a_1 (-1)+a_2 (-1)^2+a_3 (-1) ^3+...+a_k (-1)^k \equiv 0 \pmod{11}$

ma d'altra parte vale

$10 \equiv -1 \pmod{11}$

quindi rimpiazzando 10 al posto di (-1) nella congruenza abbiamo che

$N=a_0+a_1 10+a_2 10^2+a_3 10 ^3+...+a_k 10^k \equiv 0 \pmod{11}$

cioè N è divisibile per 11. Analogamente si può dmostrare l'implicazione opposta.

Esiste un secondo sistema, più impegnativo: se il numero delle cifre che compongono il numero da esaminare è dispari, si aggiunge uno zero a sinistra del numero stesso; dopodiché, si sommano le coppie di cifre consecutive. Se il risultato è 11 od un suo multiplo, vuol dire che il numero è divisibile per 11. Se alcune coppie sono già 11 o multiple di 11 (esempi: 22, 33, 44, 55) è possibile ignorarle. Se il risultato dovesse essere troppo lungo, è possibile esaminarlo a sua volta, reiterando la procedura.

Esempio nel caso di 68090 -> 06 + 80 + 90 = 176; 01 + 76 = 77. Oppure, sempre nel caso di 68090, 68 + 09 = 77 (ignorando lo 0 finale, ho pareggiato il numero delle cifre, senza dover aggiungere lo 0 a sinistra). Nel caso di 493827 -> 49 + 38 + 27 = 114; 01 + 14 = 25.

Abbiamo così provato che 68090 è divisibile per 11, mentre 493827 non lo è.

Esistono infine due regole non generiche:

nel caso di un numero a tre cifre: se la cifra centrale è la somma delle due laterali, oppure il risultato della somma della due laterali meno 11, il numero è divisibile per 11 (esempi: 121, 132, 231, 176, 418, 814, 671, 187, 781, 407, 704, 979),
tutti i numeri palindromi composti da un numero pari di cifre sono divisibili per 11 (esempi: 1001, 1111, 2002, 2222, 456654, 40966904, 489823328984). Questo criterio è un corollario del criterio generale descritto in precedenza.

[modifica] Divisibilità per 12

Un numero è divisibile per 12 se è contemporaneamente divisibile per 3 e per 4.

[modifica] Divisibilità per 13

Il criterio di divisibilità per 13 è identico a quello per 7, tranne per i moltiplicatori, che in questo caso sono -1, 3 e 4.

[modifica] Divisibilità per 17

Un numero con più di due cifre è divisibile per 17 se la differenza (presa in valore assoluto) fra il numero ottenuto eliminando la cifra delle unità e il quintuplo della cifra delle unità è 0, 17 o un multiplo di 17.

Per esempio 2584 è divisibile per 17 se lo è il numero 258 - 5 × 4 = 238; questo è divisibile per 17 se lo è il numero 23 - 5 × 8 = 17.

[modifica] Divisibilità per 25

Un numero è divisibile per 25 se lo è il numero formato dalle ultime 2 cifre, cioè 00, 25, 50, 75.

[modifica] Divisibilità per 100

Un numero è divisibile per 100 se le ultime due cifre sono 00.

[modifica] Divisibilità per 125

Un numero è divisibile per 125 se lo è il numero formato dalle ultime 3 cifre, cioè 000, 125, 250, 375, 500, 625, 750, 875.

[modifica] Divisibilità per 1001

Il criterio è simile a quello per 11, solo che le cifre vanno prese a gruppi di tre.

Ad esempio, con 493827 si ottiene 827 - 493 = 334, e con 278491650 si ottiene 650 - 491 + 278 = 437. Il numero così ottenuto ha lo stesso resto modulo 1001 del numero originario, quindi entrambi i numeri nell'esempio non sono divisibili per 1001.

[modifica] Eliminazione degli zeri

Nel caso non siamo interessati a conoscere il resto della divisione, ma semplicemente a sapere se il numero è divisibile per il fattore dato, è anche possibile eliminare tutti gli zeri consecutivi a destra del numero, sempre che il fattore dato non sia divisibile né per 2 né per 5. Questo è utile soprattutto quando il fattore è un numero di due cifre. Ad esempio, invece che 349601700 possiamo considerare 3496017. È inoltre possibile sommare o sottrarre un multiplo fattore dato, visto che l'operazione non cambia il resto; se il nostro fattore fosse stato 17, sottraendolo otterremmo 3496000 e quindi eliminando gli zeri 3496; se ci viene in mente che 34 = 17 × 2 possiamo anche togliere 3400, rimanendo con 96 che a questo punto possiamo facilmente vedere non essere multiplo di 17.

Un'altra possibilità, se il fattore non è pari ma il numero sì, è quello di dimezzare il numero; nel caso precedente passeremmo da 96 a 48, a 24, e infine a 12, evitando anche l'ultima divisione.

[modifica] Generalizzazione dei criteri

In una qualunque base b, i criteri di divisibilità indicati sopra per 9 e 11 possono essere generalizzati alla divisibilità per b - 1 e b + 1.

[modifica] Voci correlate

Divisore

Estratto da "http://it.wikipedia.org../../../c/r/i/Criteri_di_divisibilit%C3%A0.html"

Categoria: Aritmetica

See also ebooksgratis.com: no banners, no cookies, totally FREE.