I criteri di divisibilità, chi se li ricorda?

I criteri di divisibilità sono tra gli argomenti più angosciosi per i ragazzi delle scuole medie.
Mi sembra di vederli mentre, chini sul foglio, si chiedono a cosa possa servire quella sega mentale [ndr: inutile complessità], visto che le divisioni si fanno con la calcolatrice.
Tra non molti anni è probabile che anche la prova del nove, basata sulla divisibilità per 9, possa ridursi a un modo di dire di cui si sarà persa l’origine.
In questo secondo post dedicato agli studenti delle scuole medie (qui il primo), vediamo come lo studio dei criteri di divisibilità sia una buona occasione per imparare qualcosa sulla natura dei numeri.

---

Gli attrezzi di base

Premessa: in quello che segue è proibito utilizzare calcolatrici, fogli di calcolo e simili. Tutto va fatto utilizzando carta, matita e neuroni.
Un approccio a neuroni nudi, però, non porterebbe lontano, servono un po’ di attrezzi di base.
A fornirceli è l’aritmetica delle congruenze o modulare, studiata per la prima volta dal matematico tedesco Carl Friedrich Gauss (1777-1855).
È detta anche aritmetica dell’orologio, perché ne portiamo al polso un’applicazione pratica: se sommiamo due ore alle 23 otteniamo non 25 ma l’una del nuovo giorno. Questo fatto si rappresenta così:

23 + 2 ≡ 1, mod 24
e si legge: 23 + 2 è congruente a 1, modulo 24

Il simbolo della congruenza (≡) ricorda da vicino quello dell’uguaglianza (=), a rappresentare l’affinità dei due concetti. La novità è che due numeri saranno congruenti non solo se sono uguali, ma anche se differiscono di un multiplo del modulo. Esempio:

49 ≡ 25 ≡ 1 mod 24

Il primo attrezzo a nostra disposizione è quindi:

Nell’aritmetica modulare è possibile aggiungere o sottrarre un multiplo del modulo, senza alterare la congruenza del numero stesso.

Ne segue anche che un numero è congruente al resto della divisione del numero stesso per il modulo. Nell’esempio:

se divido 49 per 24 ottengo il resto di 1
49 = 24 * 2 + 1

e quindi che un numero congruente con 0 (resto = 0) è divisibile per il modulo.

I rimanenti attrezzi sono costituiti dalle seguenti proprietà:

Le congruenze secondo uno stesso modulo possono essere sommate, sottratte o moltiplicate, rimanendo congruenze.

La prova del nove

Breve riepilogo per gli smemorati.
Quando alle elementari moltiplicavamo due numeri, ad esempio 43 e 68, eravamo tenuti a verificare l’esattezza del risultato eseguendo la prova del nove:

• dopo aver eseguito in colonna la moltiplicazione, ottenendo nel nostro esempio il prodotto 2.924;
• sommavamo le cifre del primo termine (4 + 3 = 7) e del secondo termine (6 + 8 = 14, 1 + 4 = 5), ripetendo eventualmente la somma fino a ottenere una sola cifra;
• moltiplicavamo tra loro i due numeri ottenuti (7 * 5 = 35) e sommavamo le cifre del prodotto ( 3 + 5 = 8);
• sommavamo infine le cifre del risultato della moltiplicazione (2.924, 2 + 9 + 2 + 4 = 17, 1+7 = 8).

L’uguaglianza del risultato degli ultimi due passaggi (8) indicava la ragionevole sicurezza di aver eseguito correttamente la moltiplicazione. Risultati diversi, invece, ci avrebbero dato la certezza di aver sbagliato qualcosa.
Ad esempio, se nell’esecuzione in colonna erroneamente avessimo calcolato 3 * 8 = 28, allora il risultato sarebbe stato 2.928, che alla prova del nove avrebbe fornito 3 (2 + 9 + 2 + 8 = 21, 2 + 1 = 3), diverso dal risultato atteso 8. E ci saremmo subito accorti della presenza di un errore.

Su cosa si basa la prova del nove?

Per la sua vicinanza a 10, base del nostro sistema di numerazione, il calcolo della congruenza modulo 9 è molto semplice.
Se, in un qualunque numero intero N, si isola l’ultima cifra (che indichiamo con B) da quello che precede (che indichiamo con A), vale la relazione N = 10 A + B.
Esempio: 2.924 = 10 * 292 + 4.
Ora:

N   =   10 A + B   =   (9 + 1) * A + B   =   9 A + A + B   ≡   A + B,  modulo 9
Quindi possiamo calcolare la congruenza di N come somma di A e dell’ultima cifra B.

Il procedimento si può applicare ricorsivamente, consumando tutte le cifre di N, una per volta. Alla fine si concluderà che N è congruente alla somma delle sue cifre. E questo è esattamente il procedimento utilizzato nella prova del nove, che si può quindi descrivere anche così:

• si calcola il resto a 9 dei due fattori;
• quindi si moltiplicano i due valori appena trovati, e se ne calcola il resto a 9;
• infine si verifica che quest’ultimo resto sia uguale al resto a 9 del prodotto.

In caso di errore di calcolo, il risultato della moltiplicazione sarà diverso da quello giusto ed è probabile che la verifica delle congruenze lo rilevi.
Rimane da spiegare perché sia stato scelto proprio il modulo 9. Le ragioni sono due:

1. il resto della divisione per 9 può assumere ben 9 valori (0, 1, 2, …, 8), con una buona probabilità quindi che eventuali errori possano essere rilevati;
2. il calcolo del resto a 9 (e quindi la verifica di divisibilità per 9) è molto semplice.

La divisibilità per 11

Anche 11 è vicino a 10, ma dall’altra parte. Vediamo questo cosa comporta al calcolo della congruenza di N, modulo 11.
Come fatto per il 9, partiamo dall’isolare l’ultima cifra di N:

N   =   10 A + B   =   (11 – 1) * A + B   =   11 A – A + B   ≡   – A + B,  modulo 11

Quindi questa volta A andrà preso con il segno negativo.
Procedendo ricorsivamente, le cifre andranno quindi alternativamente aggiunte e sottratte, partendo dalla cifra meno significativa.
Se rispolverate il criterio di divisibiltà per 11 (scuola media), ricorderete che bisogna sommare separatamente le cifre di posizione pari e quelle di posizione dispari e verificare che le due somme siano uguali. Giusto un altro modo per esprimere l’algoritmo descritto appena più su.

E per altri numeri?

Se si applica ad altri numeri lo stesso approccio visto per 9 e 11, ci si trova di fronte a calcoli più complicati.

Per 7, ad esempio, si dovrebbe ragionare così:

N   =   10 A + B   =   (7 + 3) * A + B   =   7 A + 3 A + B   ≡   3 A + B,  modulo 7

Ma per 23 saremmo completamente fuori strada:

N   =   10 A + B   =   (23 – 13) * A + B   =   23 A – 13 A + B   ≡   – 13 A + B,  modulo 23

del tutto non conveniente.

Serve un approccio diverso

Cominciamo con l’osservare che, se N è diviso esattamente da 23, lo sarà anche 7 N:

se N = 10 A + B ≡ 0, mod 23
7 N   ≡   0
70 A + 7 B ≡ 0
69 A + A + 7 B ≡ 0
ma 69 = 23 * 3, quindi:
A + 7 B ≡ 0, mod 23

Quindi: se N = 10 A + B è divisibile per 23, lo sarà anche A + 7 B.

La sequenza logica può essere scritta anche in ordine inverso:

se A + 7 B ≡ 0, mod 23, allora 10 A + B ≡ 0, mod 23.

Ne segue quindi l’algoritmo di verifica della divisibilità per 23:

Si tolga al numero N l’ultima cifra, e a ciò che rimane si sommi 7 volte la cifra tolta. Se il risultato è divisibile per 23, allora lo sarà anche N.

Quindi: partendo da N, si eliminerà di volta in volta l’ultima cifra, fino a rimanere con un numero piccolo di cui sia semplice determinare la divisibilità per 23.
Esempio:

N = 795.041
79.504 + 7 * 1 = 79.511
7.951 + 7 * 1 = 7.958
795 + 7 * 8 = 851
85 + 7 = 92
9 + 7 * 2 = 23, divisibile per 23

*Perché siamo partiti da 7 N?

Semplicemente perché 70 supera di 1 un multiplo di 23, e questo porta a 70 A ≡ A, mod 23.
Analogamente, per determinare il criterio di divisibilità per, poniamo, 37, basterà partire dal fatto che 3 * 37 = 111, e quindi supera 110 di 1:

se N = 10 A + B ≡ 0, mod 37
11 N  ≡ 0
110 A + 11 B ≡ 0
111 A – A + 11 B ≡ 0
ma 111 = 37 * 3, quindi:
– A + 11 B ≡ 0, mod 37

Ne segue il criterio di divisibiltà per 37:

Si tolga al numero N l’ultima cifra, e da ciò che rimane si sottragga 11 volte la cifra tolta. Se il risultato è divisibile per 37, allora lo sarà anche N

Esempio:

N = 45.658
4.565 – 11 * 8 = 4.477
447 – 11 * 7 = 370, divisibile per 37
infatti: N = 45.658 = 37 * 1.234

C’è una sostanziale differenza tra l’approccio utilizzato per il 9 e l’11 e quello visto per 23 e 37.
Nel primo si calcola il resto a 9 o a 11 del numero di partenza e se ne conclude la divisibilità quando il resto è 0.
Nel secondo invece si può solo concludere se N è divisibile o meno per il modulo.

---

La ricerca di algoritmi di verifica di divisibilità non si esaurisce qui. Si può, ad esempio, isolare non l’ultima cifra, ma le ultime due o addirittura le ultime tre. Per alcuni numeri primi si arriva ad algoritmi di verifica di divisibilità molto semplici.
Una ricca raccolta di criteri di divisibilità si trova su wikipedia in inglese, ma anche su diversi siti web, come ad esempio questo.
Osservando, ad esempio che 999 è multiplo di 37, si trova un criterio più semplice di quello riportato su: basta dividere il numero dato in gruppi di tre cifre, e sommare i vari gruppi. Per numeri molto grandi l’algoritmo è decisamente più veloce.
Come ci si arriva? Provate, gli attrezzi necessari sono quelli descritti!