Criteri di divisibilità: differenze tra le versioni

Versione delle 22:09, 28 nov 2016

Versione attuale delle 12:06, 29 giu 2025

(238 versioni intermedie di oltre 100 utenti non mostrate)

Riga 1:

{{F|numeri|luglio 2017}}

In [[aritmetica]], i '''criteri di divisibilità''' sono degli [[algoritmo|algoritmi]] che permettono di verificare la [[divisibilità]] di un [[numero intero]] per un [[Moltiplicazione|fattore]] senza eseguire la [[divisione (matematica)|divisione]] esplicita.

In [[aritmetica]], i '''criteri di divisibilità''' sono degli [[algoritmo|algoritmi]] utilizzati per determinare la [[divisibilità]] di un [[numero intero]] per un certo [[Moltiplicazione|fattore]], senza la necessità di eseguire una [[divisione (matematica)|divisione]] esplicita.

ConsistonoQuesti incriteri si basano su una serie di operazioni eseguite sulle [[cifra|cifre]] che compongono il numero. Tali operazioni dovrebbero essere sufficientemente semplici da potersi fare a mente, o comunque essere più rapideveloci rispetto alla divisione.

Poiché i criteri di divisibilità manipolanooperano direttamente lesulle cifre del numero, dipendonola loro applicabilità dipende dalla [[Base (aritmetica)|base]] in cui il numero vieneè espresso. In pratica però, si considerano solamente i criteri per i numeri espressi in [[sistema numerico decimale|base 10]]. NelQuando caso ilun criterio parlisi riferisce dialle "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 conosceredeterminare il [[resto]] della [[Divisione euclidea|divisione]], perchépoiché calcolano il [[aritmetica modulare|modulo]], e il numero dato è divisibile [[se e solo se]] tale resto è 0. Può essere necessaria una lieve modifica rispetto alla loro formulazione tradizionale,. adAd esempio, il criterio di divisibilità per 2 può essere espresso nella forma: il resto della divisione di un numero ''<math>n''</math> per 2 è uguale al resto della divisione dell'ultima cifra di ''<math>n''</math> per 2 (e quindi ''<math>n''</math> è divisibile per 2 se e solo se tale resto è 0).

Inoltre, vale la regola generale persecondo cui, se un numero ''<math>n''</math> è divisibile per ''<math>m'',</math> allora ''<math>n''</math> è divisibile anche per ogni [[divisore]] di ''<math>m''.</math> Viceversa, se ''<math>n''</math> è divisibile per ''m''<math>m_1</math>, e<math>m_2, per ''l''\ldots,m_l</math>, allora ''<math>n''</math> è divisibile anche per il [[minimo comune multiplo]] di ''m''<math>m_1</math>, e ''l''<math>m_2,\ldots,m_l</math>. Ad esempio, un numero è divisibile per 6 se e solo se lo è divisibile sia per 2 sia per 3. Usando questa regola, se la [[fattorizzazione]] di ''<math>m''</math> in primi distinti è <math>m = p_1^{e_1} p_2^{e_2} \cdots p_l^{e_l}</math>, allora un numero è divisibile per ''<math>m''</math> se èe solo se è divisibile per ognuno dei fattori <math>p_1^{e_1}, p_2^{e_2}, \cdots, p_l^{e_l}</math>. È quindi sufficiente considerare i criteri di divisibilità per i numeri primi e per le potenze di primi. Ad esempio, poiché <math>792 = 2^3 \cdot 3^2 \cdot 11</math>, un numero è divisibile per 792 se e solo se è divisibile per 8, per 9 e per 11.

== Principali criteri di divisibilità dei numeri interi ==

{{U|Divisore#Regole_per_piccoli_divisori|matematica|marzo 2024}}

=== Divisibilità per 0 ===

{{Vedi anche|Divisione per zero}}

Nessun numero (diverso da 0) è divisibile per 0.

=== Divisibilità per 1 ===

Riga 18 ⟶ 21:

=== Divisibilità per 2 ===

Un numero è divisibile per 2 se e solo se la sua ultima cifra decimale è [[numeri pari e dispari|pari]], valeovvero ase direla sua ultima cifra è 0, 2, 4, 6, oppure 8.

*''dimostrazione'''Dimostrazione''''': consideriamosi consideri un numero <math>N,</math>; le sue [[base numerica|cifre decimali]] sono i coefficienti ''a''_i che compaiono nella somma:

::<math>N=a_0+a_1 10+a_2 10^2+a_3 10 ^3+\cdots+a_k 10^k</math>

:i termini ''a''<submath>a_i10^i</sub>10<sup>i</supmath> sono tutti divisibili per 2 se <math>i>0</math>, quindi se <math>N</math> è divisibile per 2 lo è anche :

::<math>N-(a_1 10+a_2 10^2+a_3 10 ^3+\cdots+a_k 10^k)</math>

:cioè ''a''<submath>0a_0</submath>, che quindi è 0, 2, 4, 6 o 8.

:Viceversa se ''a''<submath>0a_0</submath> è 0, 2, 4, 6 o 8, una volta che lo sommiamo al numero:

::<math>(a_1 10+a_2 10^2+a_3 10 ^3+\cdots+a_k 10^k)</math>

:che è anch'esso divisibile per 2, otteniamo ancora un multiplo di 2, dunque ''<math>N''</math> 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 [[Numero intero|numeri interi]] in due categorie: i [[Numeri pari e dispari|numeri pari]], che sono divisibili per 2, e i [[Numeri pari e dispari|numeri dispari]], che non lo sono.

Un numero intero si dice '''pari''' se è divisibile per 2, altrimenti di dice '''dispari'''. Vedi anche [[Numeri pari e dispari]].

==== Divisibilità per una potenza di 2 ====

Più in generale, un numero è divisibile per <math>2^k</math> se lo è il numero compostocostituito dalle ''<math>k''</math> cifre più a destra del numero.

Dimostrazione: rappresentiamo un qualunque numero naturale <math>n</math> nella forma <math>n=m_k10^k+n_k</math> dove <math>n_k</math> indica il numero costituito dalle prime k cifre di destra ed <math>m_k</math> il numero costituito dalle rimanenti cifre alla sinistra di <math>n_k</math>. Se dividiamo entrambi i membri per <math>2^k</math> risulta che, poiché <math>m_k10^k/2^k= m_k5^k</math> è un numero intero, la divisibilità di <math>n</math> per <math>2^k</math> dipende solo dalla divisibilità di <math>n_k/2^k</math>. Nel caso infine in cui <math>n_k</math> sia costituito da tutti zeri, si avrà <math>n=m_k10^k+0=m_k5^k2^k</math> che ne indica la divisibilità per <math>2^k</math>.

* '''''Dimostrazione''''': si rappresenti un qualunque numero naturale <math>n</math> nella forma <math>n=m_k10^k+n_k</math> dove <math>n_k</math> indica il numero costituito dalle prime k cifre di destra ed <math>m_k</math> il numero costituito dalle rimanenti cifre alla sinistra di <math>n_k</math>. Se si dividono entrambi i membri per <math>2^k</math> risulta, poiché <math>m_k \frac {10^k} {2^k}= m_k5^k</math> è un numero intero, che la divisibilità di <math>n</math> per <math>2^k</math> dipende solo dalla divisibilità di <math> \frac{n_k} {2^k}</math>.

=== Divisibilità per 3 ===

Un numero è divisibile per 3 se la somma delledi tutte le sue cifre è pari a 3 o ad un suo multiplo. Nel(6, 9); nel caso in cui tale somma sia un numero maggiore di 9, sise puòne eseguiresommano dinuovamente nuovole lcifre e si verifica che quest'operazioneultimo risultato sia divisibile per 3.

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 le eventuali cifre divisibili per 3 (ossia 0, 3, 6, 9) presenti nel numero. Ad esempio, per verificare se 32565 è divisible per 3 basta eseguire la somma 2+5+5 = 12. Dato che 12 è divisibile per 3, allora anche 32565 lo è.

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.

*''dimostrazione'': consideriamo un numero N, le sue [[base numerica|cifre decimali]] sono i coefficienti ''a''_i che compaiono nella somma

::<math>N=a_0+a_1 10+a_2 10^2+a_3 10 ^3+\cdots+a_k 10^k</math>

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

:supponiamo che la somma

*'''''Dimostrazione''''': si consideri un numero <math>N,</math>; le sue [[base numerica|cifre decimali]] sono i coefficienti <math>a_i</math> che compaiono nella somma:

::<math>N=a_0+a_1 10+a_2 10^2+a_3 10 ^3+\cdots+a_k 10^k</math>.

:Supponiamo che la somma

::<math>a_0+a_1+a_2+a_3+\cdots+a_k</math>

:sia divisibile per 3,; questo si può tradurre in [[aritmetica modulare]] dicendo che:

::<math>a_0+a_1+a_2+a_3+\cdots+a_k\equiv 0 \pmod{3}</math>

:ovvero:

::<math>a_0\equiv -(a_1+a_2+a_3+\cdots+a_k)\pmod{3}</math>.

:sostituendoSostituendo in ''<math>N''</math> si ha:

::<math>N\equiv -(a_1+a_2+a_3+\cdots+a_k)+a_1 10+a_2 10^2+a_3 10 ^3+\cdots+a_k 10^k\equiv 9 a_1+99a_2+\cdots+(10^k-1)a_k\;\;,</math>

:che risulta evidentemente essere un multiplo di 3.

=== Divisibilità per 4 ===

Un numero è divisibile per 4 se le ultime due cifre sono 00due zeri oppure formano un numero multiplo di 4, ooppure equivalentementese 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, oppure 8.

*''dimostrazione'''Dimostrazione''''': consideriamosia un numero <math>N,;</math> le sue [[base numerica|cifre decimali]] sono i coefficienti ''a''<submath>ia_i</submath> che compaiono nella somma:

::<math>N=a_0+a_1 10+a_2 10^2+a_3 10 ^3+\cdots+a_k 10^k</math>.

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

:Supponiamo che le ultime due cifre

::<math>a_0+a_1 10</math>

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

::<math>a_2 10^2+a_3 10 ^3+\cdots+a_k 10^k</math>

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

Esempio: ''424'' è divisibile per 4 perché le ultime 2 cifre sono 2 e 4, che formano 24, che è multiplo di 4.

Riga 71 ⟶ 80:

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

*''dimostrazione'''Dimostrazione''''': consideriamosi consideri un numero <math>N,;</math> le sue [[base numerica|cifre decimali]] sono i coefficienti ''a''<submath>ia_i</submath> che compaiono nella somma:

::<math>N=a_0+a_1 10+a_2 10^2+a_3 10 ^3+\cdots+a_k 10^k</math>

:i termini ''a''<submath>a_i10^i</sub>10<sup>i</supmath> sono tutti divisibili per 5 se <math>i>0,</math> quindi se <math>N</math> è divisibile per 5 lo è anche :

::<math>N-(a_1 10+a_2 10^2+a_3 10 ^3+\cdots+a_k 10^k)</math>

:cioè ''a''<submath>0a_0</submath>, che quindi è 0 o 5.

:Viceversa se <math>a_0</math> è 0 o 5 una volta che lo si somma al numero:

::<math>(a_1 10+a_2 10^2+a_3 10 ^3+\cdots+a_k 10^k)\;\;,</math>

:che è anch'esso divisibile per 5, si ottiene ancora un multiplo di 5, dunque <math>N</math> sarà divisibile per 5.

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

::<math>(a_1 10+a_2 10^2+a_3 10 ^3+\cdots+a_k 10^k)</math>

:che è anch'esso divisibile per 5 otteniamo ancora un multiplo di 5, dunque ''N'' 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 <math>5^k</math> se lo sonoè leil ''numero formato dalle <math>k''</math> cifre più a destra del numero.

=== Divisibilità per 6 ===

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

=== Divisibilità per 7 ===

Analizzeremo di seguito tre differenti criteri di divisibilità per questo caso, con il primo caso suddivisibile in due sottovarianti.

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) è 7 o un multiplo di 7.

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&times;5 = 6853; non sapendo se 6853 sia divisibile per 7 basta ripetere la procedura. 685 + 3&times;5 = 700, che è evidentemente un multiplo di sette. Pertanto 68089 è multiplo di 7.

*''dimostrazione'''Dimostrazione''''': consideriamosi consideri un numero <math>N,;</math> le sue [[base numerica|cifre decimali]] sono i coefficienti ''a''<submath>ia_i</submath> che compaiono nella somma:

::<math>N=a_0+a_1 10+a_2 10^2+a_3 10 ^3+\cdots+a_k 10^k\;\;,</math>

:che possiamo scrivere più sintenticamentesinteticamente:

::<math>N=a_0+10 \times b</math>.

:nelNel linguaggio dell'[[aritmetica modulare]] sappiamoè noto che ''<math>N''</math> è divisibile per 7 se e solo se:

::<math>N\equiv 0 \pmod{7}\;\;,</math>

:ovvero:

::<math>a_0+10 \times b\equiv 0 \pmod{7}</math>.

:eSe sesi moltiplichiamomoltiplica tutto per ''5'' (che è l'inverso aritmetico di 10 modulo 7) abbiamo :

::<math>5\times a_0+5 \times 10 \times b\equiv 0 \pmod{7}\;\;,</math>

:ovvero:

::<math>5\times a_0+b+\cancel{49 \times b}\equiv 0 \pmod{7}</math>

:da cui:

:poiché

::<math>505\times a_0+ b\equiv 10 \pmod{7}.</math>.

Dato che <math>-2</math> appartiene alla stessa [[Aritmetica modulare#Le classi di resto modulo n|Classeclasse di Restoresto]] di 5 modulo 7, il criterio sopra definito può essere ''modificato comein una seconda variante'', secondo quanto segue:.

''A.2) Primo criterio, seconda variante: con separazione dell'ultima cifra (quella delle unità).''

Un numero è divisibile per 7 se la differenza tra il numero ottenuto escludendo la cifra delle unità e il doppio della cifra delle unità è 0, 7 o un multiplo di 7.

''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"; 6808-9&times;2=6790; 679-0&times;2=679; 67-9&times;2=49; da cui la divisibilità del numero iniziale per 7.

Utilizzando lo stesso esempio "68089" è possibile infatti vedere che: 6808-9&times;2=6790; 679-0&times;2=679; 67-9&times;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à.

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 secondo criterio di divisibilità per 7, come quello per 13, sfrutta anche il fatto che 1001 è fattorizzabile come 7 &times; 11 &times; 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.

Un altro metodo per determinare la divisibilità per 7, come quello per 13, sfrutta anche il fatto che 1001 è fattorizzabile come 7 &times; 11 &times; 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.

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 493827, le operazioni da compiere sono:

*4 &times; 3 + 9 = 21 <math>\rarr</math> 0;

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.

*0 &times; 3 + 3 = 3;

*3 &times; 3 + 8 = 17 <math>\rarr</math> 3;

Nell'esempio del numero 493827, le operazioni da compiere sono:

*3 &times; 3 + 2 = 11 <math>\rarr</math> 4;

*4 &times; 3 + 7 = 19 <math>\rarr</math> 5.

×4 &times; 3 + 9 = 21 <math>\rarr</math> 0;

×0 &times; 3 + 3 = 3;

×3 &times; 3 + 8 = 17 <math>\rarr</math> 3;

×3 &times; 3 + 2 = 11 <math>\rarr</math> 4;

×4 &times; 3 + 7 = 19 <math>\rarr</math> 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''Numeri grandiGrandi'', è 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.

Ad esempio "1491826": 826 - 491 + 1 = 336 e, utilizzando uno dei criteri precedenti, 33 + (6 &times; 5) = 63 quindi è divisibile.

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 &times; 5) = 63 quindi è divisibile.

Un ulteriore criterio di divisibilità per 7 è il seguente, assai facile da usare.

Un ulteriore criterio di divisibilità per 7 è il seguente, assai facile da usare:

Si divide il numero in esame in gruppi di tre cifre (da destra a 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. Sembra complicato ma non lo è: basta fare un esempio. Prendiamo 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 facilmente 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òsi anche divideredivide il numero in esame in due gruppi di cifre, le tre cifre dioperando ''da destra everso lesinistra'' rimanenti cifre, ed applicare il medesimo criterio. Prendiamo il numero 123457789 (già considerato sopra): il restoe di 123457:7ciascuno èsi 5,calcola il resto didella 789:7 è 5; la differenza dei resti è nulla e pertanto il numero di partenza è divisibiledivisione 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:'''''

senza perdita di generalità sulla lunghezza del numero iniziale, potremmo dire che il numero <math>N</math> di cui vogliamo verificare la divisibilità per 7 si può scrivere come ''abcdef'', dove ogni lettera rappresenta una cifra numerica (se il numero <math>N</math> fosse più lungo o più corto è sufficiente prendere in considerazione ulteriori lettere per rappresentarlo). In simboli, sia <math>N</math> = ''abcedf'', allora:

<math>N</math> = ''abcdef'' = ''abcd'' × 100 + ''ef'' = ''abcd'' × (98 + 2) + ''ef'' = 98 × ''abcd'' + 2 × ''abcd'' + ''ef'' = 98 × ''abcd'' + <math>M</math>,

dove si è posto <math>M</math> = 2 × ''abcd'' + ''ef''.

Siccome 98 × ''abcd'' è divisibile per 7 (per ben due volte dato che è divisibile anche per 49), <math>N</math> è divisibile per 7 se e solo se lo è anche <math>M,</math> che è proprio quanto sostenuto in questo criterio di divisibilità.

''C) terzo criterio: con somma delle cifre moltiplicate per opportuni scalari.''

''Enunciato: "Un numero è divisibile per sette se lo è la somma delle somme con segni alterni: delle cifre di posizione congrua a zero (mod 3), delle cifre di posizione congrua a 1 (mod 3) per tre e delle cifre di posizione congrua a 2 (mod 3) per due".''

Esempio: verificare che il numero 777213213 sia divisibile per 7.

(3-3+7)+3*(1-1+7)+2*(2-2+7)=42

poiché 42 è divisibile per 7, anche 777213213 lo sarà.

* '''''Dimostrazione:'''''

Sia <math>N=a_010^0+a_1 10^1+a_2 10^2+...+a_k 10^k</math> si ha:

<math>10^0\equiv 1\; (mod \,\,7)

</math>

<math>10^1\equiv 3\, (mod\,\,7)

</math>

<math>10^2\equiv 2\, (mod\,\,7)

</math>

<math>10^3\equiv6\equiv-1 \,(mod\,\,7)

</math>

<math>10^4\equiv4\equiv-3\,(mod\,\,7)

</math>

<math>10^5\equiv 5 \equiv-2\,(mod\,\,7)

</math>

<math>10^6\equiv 1\, (mod\,\,7)

</math> per il [[Piccolo teorema di Fermat]]

<math>10^7=10^1\cdot10^6\equiv10^1\equiv3\,(mod\,\,7)

</math>

<math>10^8=10^2\cdot10^6\equiv10^2\equiv2\, (mod\,\,7)

</math>

e così via...

quindi <math>N\equiv a_0+3a_1+2a_2-a_3-3a_4-2a_5+a_6+3a_7+2a_8+...=(a_0-a_3+a_6-...)+3(a_1-a_4+a_7-...)+2(a_2-a_5+a_8-...).

</math>

Curiosità: il metodo C) consente il calcolo del resto della divisione di N per 7.

Curiosità: in modo analogo al metodo B) si deriva un altro criterio di divisibilità per il numero 17; l'unica differenza che il numero residuale ''ef'' (cioè quello composto dalle sole cifre della decina e dell'unità) deve essere sottratto e non aggiunto; attenzione: in questo caso il risultato finale potrebbe venire negativo, ma questo non deve preoccupare, il risultato finale può essere considerato in [[valore assoluto]].

Il criterio appena esposto ben si adatta ad una rapida determinazione della divisibilita` per 7 sui ''Numeri Grandi''.

Infatti in maniera del tutto identica a quanto scritto nel primo criterio, è possibile dividerli in gruppi di tre cifre da destra a sinistra, inserendo ''segni alternati'' fra ogni gruppo: il risultato dev'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 il ''secondo criterio'' appena esposto:

3×2 + 36 = 42 che, essendo divisibile per 7, conferma la divisibilità per 7 anche del numero di partenza.

Altro esempio: analizziamo la divisibilità per 7 di 123457789:

123457789: +789 -457 +123 = 455;

e, per il ''secondo criterio B):''

455: 4×2 + 55 = 63, ovvero il numero di partenza è divisibile per 7.

=== Divisibilità per 8 ===

Un numero è divisibile per 8 se termina con tre zeri o se lo è il numero formato dalle sue ultime 3 cifre. Per esempio: [[1128 (numero)|1128]] è divisibile per 8 perché anche 128 lo è.

Esempio: [[1128]] è divisibile per 8 perché anche 128 lo è

Un'altra possibilità è data dal prendere la terzultimaterz'ultima cifra, raddoppiarla, sommarla alla penultima, raddoppiare il risultato e sommarlo all'ultima: se il risultato finale è multiplo di 8, allora anche il numero originale lo è.

Esempio: ''15736''. siSi faesegue il conto: 7&times;2 = 14; 14+3 = 17; 17&times;2 = 34; 34+6 = 40. Dato che 40 è un multiplo di 8, anche 15736 lo è.

=== Divisibilità per 9 ===

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

Si consideri ad esempio il numero 493827,: sommando le sue cifre si ottiene 33. Ripetendo ulteriormente l'operazione si ottiene 6, da cui risulta che il numero 493827 non è divisibile per 9. Il risultato dell'operazione (6 nell'esempio) è pari al resto modulo 9 (dividendo il risultato per 3 si otterrebbe il resto modulo 3).

Da notare che non è necessario sommare eventuali cifre 9 presenti nel numero.

Dal criterio appena descritto si ricava una delle tante proprietà curiose legate al numero 9. Se si sottrae ad un qualunque numero la somma delle sue cifre prese singolarmente si ottiene sempre un numero divisibile per 9.

Riprendendo l'esempio precedente, se a 493827 si sottraggono le sue cifre si ottiene: 493827-(4+9+3+8+2+7)=493794, la cui divisibilità per 9 può facilmente essere dimostrata col precedente criterio. Questo è dovuto al fatto che, come descritto in precedenza, la somma delle cifre di un numero è pari proprio al resto modulo 9.

Questo è dovuto al fatto che, come descritto in precedenza, la somma delle cifre di un numero è pari proprio al resto modulo 9.

Vedi anche [[Prova del nove]] e [[Radice numerica]].

Riga 164 ⟶ 287:

==== Divisibilità per una potenza di 10 ====

Un numero è divisibile per <math>10^m</math> (10, 100, 1000, ...) quando le sue ultime <math>m</math> (1, 2, 3, ..., rispettivamente) cifre a destra sono tutti zeri. Ad esempio, 40 è divisibile per 10, 300 è divisibile per 100 e 4000 è divisibile per 1000.

*'''''Dimostrazione''''': un generico numero naturale <math>N</math> è, infatti, sempre esprimibile nella forma

::<math>N=a_0+a_1 10+a_2 10^2+\cdots+a_{k-1} 10^{k-1}+a_k 10^k</math>

:in cui i coefficienti <math>a_i</math> sono le <math>k+1</math> [[base numerica|cifre decimali]] di <math>N</math>. La precedente somma può essere scritta anche come

Riga 176 ⟶ 299:

=== Divisibilità per 11 ===

Un numero è divisibile per 11 se, contando da destra verso sinistra, la differenza (in valore assoluto) tra la somma delle sue cifre di posto dispari e la somma delle sue cifre di posto pari dà come risultato 0, 11 o un multiplo (anche intero) di 11.

Ad esempio, "8.291.778" è divisibile per 11 perché: (8+7+9+7+8)-(72+1+27) = 32-10 = 22.

=== Divisibilità per 12 ===

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

=== Divisibilità per 13 ===

Riga 187 ⟶ 307:

Esempio: ''12285''; calcoliamo 1228 + 5&times;4 = 1248; non sapendo se 1248 sia divisibile per 13 basta ripetere la procedura. 124 + 8&times;4 = 156. Anche qui si ripete la procedura: 15 + 6&times;4 = 39, cioè 13&times;3. Pertanto 12285 è multiplo di 13.

*''dimostrazione'''Dimostrazione''''': consideriamo un numero <math>N</math>, le sue [[base numerica|cifre decimali]] sono i coefficienti ''a''<submath>ia_i</submath> che compaiono nella somma

::<math>N=a_0+a_1 10+a_2 10^2+a_3 10 ^3+\cdots+a_k 10^k</math>

:che possiamo scrivereriscrivere più sintenticamentecome

::<math>N=a_0+10 (a_1+a_210+a_310^2+\times bldots+a_k10^{k-1})</math>

:nel linguaggio dell'[[aritmetica modulare]] sappiamo che ''<math>N''</math> è divisibile per 13 se e solo se

::<math>N\equiv 0 \pmod{13}</math>

:ovvero

::<math>a_0+10 (a_1+a_210+a_310^2+\times bldots+a_k10^{k-1})\equiv 0 \pmod{13}</math>

:e se moltiplichiamo tutto per ''4'' (che è l'inverso aritmetico di 10 modulo 13) abbiamo

::<math>4\times a_04a_0+40(a_1+a_210+a_310^2+4 \times 10 \times bldots+a_k10^{k-1})\equiv 0 \pmod{13}</math>

::

:ovvero

::poiché

::<math>4\times a_0+ b\equiv 0 \pmod{13}</math>

::<math>40\equiv 1 \pmod{13}</math>

:poiché

:si ha

::<math>40 \equiv 1 \pmod{13}.</math>

::<math>4a_0+a_1+a_210+a_310^2+\ldots+a_k10^{k-1}\equiv 0 \pmod{13}</math>

Va ricordato che questo criterio, analogamente al criterio di divisibilità per 7, '''non''' consente il calcolo del resto della divisione per 13, ma solo la verifica della divisibilità.

Un ulteriore criterio di divisibilità per 13 è il seguente, assai facile da usare.:

* si divide il numero in esame in gruppi di tre cifre (da destra a sinistra) e di ciascuno si calcola il resto della divisione per 13;

Si divide il numero in esame in gruppi di tre cifre (da destra a sinistra) e di ciascuno si calcola il resto della divisione per 13; 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 13 il numero di partenza è divisibile per 13. Sembra complicato ma non lo è: basta fare un esempio. Prendiamo il numero 123457789: il resto di 123:13 è 6, il resto di 457:13 è 2, il resto di 789:13 è 9; la somma dei resti dei gruppi di posto dispari è 6+9=15 e la somma dei resti dei gruppi di posto pari è 2 (c'è un solo gruppo); poiché 15-2=13 il numero di partenza è divisibile per 13. Per calcolare facilmente il resto della divisione di un numero per 13 si ricordi che il resto non cambia se si sottrae al numero di partenza un multiplo di 13: ad esempio 543:13 dà lo stesso resto di (543-520):13 ovvero 23:13 il cui resto è assai più facile da calcolare.

* 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 13 il numero di partenza è divisibile per 13.

Si consideri per esempio il numero 123457789: il resto di 123:13 è 6, il resto di 457:13 è 2, il resto di 789:13 è 9; la somma dei resti dei gruppi di posto dispari è 6+9=15 e la somma dei resti dei gruppi di posto pari è 2 (c'è un solo gruppo); poiché 15-2=13, il numero di partenza è divisibile per 13. Per calcolare facilmente il resto della divisione di un numero per 13 si ricordi che il resto non cambia se si sottrae al numero di partenza un multiplo di 13: ad esempio 543:13 dà lo stesso resto di (543-520):13 ovvero 23:13 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. Prendiamo il numero 123457789 (già considerato sopra): il resto di 123457:13 è 9, il resto di 789:13 è 9; la differenza dei resti è nulla e pertanto il numero di partenza è divisibile per 13.

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:13 è 9, il resto di 789:13 è 9; la differenza dei resti è nulla e pertanto il numero di partenza è divisibile per 13.

Per i numeri non divisibili per 13, 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 13 (con l'accortezza di aggiungere 13 in caso di differenza negativa e di sottrarre 13 - o multipli di 13 - in caso di differenza maggiore di 12).

=== Divisibilità per 14 ===

Un numero è divisibile per 14 se è divisibile contemporaneamente per 2 e per 7

=== Divisibilità per 17 ===

''Primo metodo:''

Un numero è divisibile per 17 se il valore assoluto della differenza 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: 1 003 è divisibile per 17 se lo è il numero <math>|100 - 5 \cdot 3| = 85</math>. Questo è divisibile per 17 se lo è il numero <math>|8 - 5 \cdot 5| = 17</math>

::<math>100 - 5 \cdot 3 = 85</math>

Questo è divisibile per 17 se lo è il numero

::<math>|8 - 5 \cdot 5| = 17</math>

* '''''Dimostrazione''''': esprimiamo <math>N</math> come <math>N=\overline{a_{k}a_{k-1}a_{k-2}\ldots a_{1}a_0}=a_0+a_1 10+a_2 10^2+a_3 10 ^3+\ldots+a_k 10^k</math>, quindi <math>N</math> sarà divisibile per 17 se e solo se <math>N\equiv_{17} 0 </math>

=== Divisibilità per 20 ===

# <math>a_0+a_1 10+a_2 10^2+a_3 10 ^3+\cdots+a_k 10^k \equiv_{17}0</math> (il coefficiente di <math>a_0</math> può essere sostituito con un altro numero appartenente alla classe di equivalenza di 1, cioè <math>[1]_{17}=[18]_{17}</math> );

# <math>18a_0+a_1 10+a_2 10^2+a_3 10 ^3+\cdots+a_k 10^k \equiv_{17}0</math> (si dividono entrambi i membri per 2: cosa possibile visto che 2 e 17 sono coprimi);

# <math>9a_0+5(a_1 +a_2 10+a_3 10 ^2+\cdots+a_k 10^{k-1}) \equiv_{17}0</math> (si sostituisce al coefficiente di <math>a_0</math> un altro numero appartenente alla classe di equivalenza di 9, cioè <math>[9]_{17}=[-25]_{17}</math> );

# <math>-25a_0+5(a_1 +a_2 10+a_3 10 ^2+\cdots+a_k 10^{k-1}) \equiv_{17}0</math> (si dividono entrambi i membri per 5: cosa possibile visto che 5 e 17 sono coprimi);

# <math>-5a_0 + a_1 +a_2 10+a_3 10 ^2+\cdots+a_k 10^{k-1} \equiv_{17}0</math> cioè <math>\overline{a_ka_{k-1}a_{k-2}\ldots a_1} - 5a_0= 17k \qquad k\in \mathbb {Z} </math>

Quindi con questo criterio è possibile ottenere 17 quando <math>k=1</math>, oppure qualche multiplo di 17: in questo caso il criterio può essere reiterato con il numero appena ottenuto (proprio come nell'esempio qua sopra).

''Secondo metodo:''

Un numero è divisibile per 17, se la somma tra il numero ottenuto dall'unità moltiplicata per 9 (si parte da 1 a 10, escludendo lo zero) e il restante numero (dedotto di uno nel caso si consideri prima il numero 10) moltiplicato per 5 è divisibile per 17. È possibile rifare il calcolo.

Esempio:

Sia il numero 143990:

(10×9) + (14398×5) = 90 + 71990 = 72080

Si reitera il conto con il numero appena ottenuto (e via di seguito): 72080

(10×9) + (7207×5) = 90 + 36035 = 36125

36125:

(5×9) + (3612×5) = 45 + 18060 = 18105

18105:

(5×9) + (1810×5) = 45 + 9050 = 9095

9095:

(5×9) + (909×5) = 45 + 4545 = 4590

4590:

(10×9) + (458×5) = 90 + 2290 = 2380

2380:

(10×9) + (237×5) = 90 + 1185 = 1275

1275:

(5×9) + (127×5) = 45 + 635 = 680

680:

(10×9) + (67×5) = 90 + 335 = 425

425:

(5×9) + (42×5) = 45 + 210 = 255

255:

(5×9) + (25×5) = 45 + 125 = 170

170 è divisibile per 17.

=== Divisibilità per 20 ===

Un numero è divisibile per 20 se è composto da almeno due cifre e le sue ultime due cifre a destra sono 00, 20, 40, 60, 80.

=== Divisibilità per 25 ===

Un numero è divisibile per 25, se è composto da almeno due cifre e le sue ultime 2 cifre a destra sono 00, 25, 50 o 75.

Ad esempio 1550 è divisibile per 25 perché le ultime 2 cifre, 50, formano un numero divisibile per 25.

=== Divisibilità per 27 ===

Per verificare se un numero è divisibile per 27, lo si divide in terzetti di cifre (a partire da destra). Se la somma di tutti i terzetti dà come risultato un multiplo di 27 allora il numero di partenza è divisibile per 27. In alternativa, se risulta più agevole, si possono calcolare i resti delle divisioni per 27 dei vari terzetti e sommare infine tutti i resti ottenuti: se tale somma dà come risultato un multiplo di 27 allora il numero di partenza è divisibile per 27.

Ad esempio "514.291.761" è divisibile perché: 761+291+514 = 1566 che è un multiplo di 27; ovvero, in alternativa, 761=28x27+5 291=10x27+21 514=19x27+1 e 5+21+1=27.

Ad esempio ''514.291.761'' è divisibile per 27 perché: 761+291+514 = 1566 che è un multiplo di 27; ovvero, in alternativa, 761=28x27+5 291=10x27+21 514=19x27+1 e 5+21+1=27.

=== Divisibilità per 37 ===

<nowiki> </nowiki>Analogamente per verificare se un numero è divisibile per 37, lo si divide in terzetti di cifre (a partire da destra). Se la somma di tutti i terzetti dà come risultato un multiplo di 37 allora il numero di partenza è divisibile per 37. In alternativa, se risulta più agevole, si possono calcolare i resti delle divisioni per 37 dei vari terzetti e sommare infine tutti i resti ottenuti: se tale somma dà come risultato un multiplo di 37 allora il numero di partenza è divisibile per 37. Ad esempio "''514.291.749"'' è divisibile perché: 749+291+514 = 1554 che è un multiplo di 37; ovvero, in alternativa, 749=20x37+9 291=7x37+32 514=13x37+33 e 9+32+33=74 che è evidentemente un multiplo di 37. Per comprendere la similarità dei criteri di divisibilità per 27 e per 37 e capire perché per tali criteri si dividono i numeri in gruppetti di tre cifre si fa riferimento alla scomposizione di 999 che è pari a 27x37.

=== Divisibilità per 101 ===

Per verificare se un numero è divisibile per 101, lo si divide in coppie di cifre a partire da destra. Se, contando da destra verso sinistra, la differenza tra la somma delle coppie che occupano posto dispari e la somma delle coppie che occupano posto pari dà come risultato 0, 101, un multiplo di 101 (anche intero), allora il numero di partenza è divisibile per 101.

Ad esempio ''514.300.787'' è divisibile perché: (87+30+5)-(7+14) = 122-21 = 101.

Per verificare se un numero è divisibile per 101, lo si divide in coppie di cifre a partire da destra. Se contando da destra verso sinistra la differenza (in valore assoluto) tra la somma delle coppie che occupano posto pari e la somma delle coppie che occupano posto dispari dà come risultato 0, 101, un multiplo di 101, allora il numero di partenza è divisibile per 101. Ad esempio "514.300.787" è divisibile perché: (87+30+5)-(7+14) = 122-21 = 101.

=== Divisibilità per 1001 ===

Per verificare se un numero è divisibile per 1001, lo si divide in terzetti di cifre a partire da destra. Se contando da destra verso sinistra, la differenza tra la somma dei terzetti che occupano posto dispari e la somma dei terzetti che occupano posto pari dà come risultato un multiplo intero di 1001, allora il numero di partenza è divisibile per 1001. Se non è della forma <math>1001k</math>, con <math>k\in\mathbb{Z}</math>, il numero ottenuto (compreso tra 1 e 1000) è il resto della divisione per 1001 (se lo otteniamo negativo dobbiamo aggiungere 1001). Questo criterio può essere utilizzato per verificare anche la divisibilità per 7, 11 e 13 quando il numero ha molte cifre (si può utilizzare questo criterio per ridurre il numero di cifre fino a 4 e poi terminare con i criteri sopra esposti).

Ad esempio ''514.291.778'' è divisibile perché: (778+514)-(291) = 1292-291 = 1001.

Per verificare se un numero è divisibile per 1001, lo si divide in terzetti di cifre a partire da destra. Se contando da destra verso sinistra la differenza (in valore assoluto) tra la somma dei terzetti che occupano posto pari e la somma dei terzetti che occupano posto dispari dà come risultato 0, 1001, un multiplo di 1001, allora il numero di partenza è divisibile per 1001. Ad esempio "514.291.778" è divisibile perché: (778+514)-(291) = 1292-291 = 1001.

=== Divisibilità in altre basi ===

Sia <math>n</math> un numero espresso in [[Base (aritmetica)|base]] <math>b</math>, e sia <math>m</math> un [[divisore]] di <math>b</math>. Si possono generalizzare il criterio di divisibilità per le potenze di 2, 5, 10 e il criterio di divisibilità per 9 (o per 3) nel modo seguente:

* il resto della divisione di <math>n</math> per <math>m^e</math> è lo stesso della divisione delle ultime <math>e</math> cifre di <math>n</math> per <math>m^e</math>;

* il resto della divisione di <math>n</math> per <math>b-1</math> (o un divisore di <math>b-1</math>) è lo stesso della divisione della somma delle cifre di <math>n</math> per <math>b-1</math>.

Sia <math>n</math> un numero espresso in base <math>b</math>, e sia <math>m</math> un divisore di <math>b</math>. Si possono generalizzare il criterio di divisibilità per le potenze di 2, 5, 10 e il criterio di divisibilità per 9 (o per 3) nel modo seguente.

Il resto della divisione di <math>n</math> per <math>m^e</math> è lo stesso della divisione delle ultime <math>e</math> cifre di <math>n</math> per <math>m^e</math>.

Il resto della divisione di <math>n</math> per <math>b-1</math> (o un divisore di <math>b-1</math>) è lo stesso della divisione della somma delle cifre di <math>n</math> per <math>b-1</math>.

Anche il criterio di divisibilità per 11 può essere facilmente generalizzato a <math>b+1</math>.

== Divisibilità in altri anelli ==

È possibile considerare la divisibilità anche su altri anelli oltre agli interi.

=== Interi di Gauss ===

Tenendo presente che 2 e 5 si scompongono in fattori primi come <math>2=-i(1+i)^2</math> e <math>5=(2-i)(2+i),</math> si possono dare criteri di divisibilità per gli [[Intero di Gauss|interi di Gauss]]: <math>1+i</math> (ed equivalentemente per <math>1-i=-i(1+i)</math>), <math>2-i</math> e <math>2+i</math>. Infatti, un intero di Gauss è divisibile:

* per <math>1+i</math> se e solo se la somma della [[parte reale]] e di quella immaginaria è divisibile per 2,

* per <math>2-i</math> se e solo se la differenza del doppio della parte reale con quella immaginaria è divisibile per 5,

* per <math>2+i</math> se e solo se la somma del doppio della parte reale e di quella immaginaria è divisibile per 5.

=== Polinomi ===

Il [[teorema del resto]] fornisce un criterio di [[divisibilità dei polinomi]] per polinomi di grado 1.

== Voci correlate ==

* [[Divisore]]

* [[Teorema del resto]] fornisce un criterio di [[divisibilità dei polinomi]]

== Altri progetti ==

{{interprogetto|preposizione=sui}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{Algebra}}

{{Teoria dei numeri}}