Criteri di divisibilità: una seconda puntata

I criteri di divisibilità sono una mia passione dai tempi del liceo, ma ci dev’essere anche qualcosa nell’inconscio che me li lega all’apertura dell’anno scolastico. Risale al settembre di tre anni fa, infatti, un mio articolo qui, su IV, sui criteri di divisibilità, e proprio in questi giorni mi sono ritrovato a curiosare sull’argomento.
Rimando a quell’articolo del 2017 per le informazioni di partenza, in particolare per quelle relative all’aritmetica modulare. Anche per le divisibilità più comuni (2, 4, 3, 9, 11) rimando all’articolo precedente.
Per chi avesse rimosso il termine di divisibilità, in breve, un numero N è divisibile per il numero d, se il resto della divisione N / d è pari a zero.
Di seguito riporto alcuni criteri di divisibilità che, diversamente da quelli riportati nell’articolo precedente, oltre a calcolare la divisibilità di N per d, mantengono anche inalterato il resto della divisione.

---

Criteri di divisibilità: 7

Immaginiamo di dover determinare se il numero 12.345 è divisibile per 7.
Osserviamo che 12.345 si può anche scrivere come 1.234 * 10 + 5, isolando l’ultima cifra. Manipolando l’espressione. si ha:

1.234 * (7 + 3) + 5 = 1.234 * 7 + 1.234 * 3 + 5

Ora, il primo termine della somma è un multiplo di 7, per cui dà contributo nullo al resto della divisione per 7, e quindi può essere ignorato. In termini più matematici, ricorrendo all’aritmetica modulare, si dice che:

 12.345  =  1.234 * 10 + 5  ≡  1.234 * 3 + 5  (mod 7).

Il simbolo “≡” estende il significato dell’uguaglianza nell’aritmetica modulare, e indica che i due numeri ai suoi lati sono congruenti tra loro, secondo il modulo indicato, nel nostro caso 7: sono cioè uguali, a meno di un multiplo del modulo stesso.
Ricorrere all’aritmetica modulare per il calcolo del resto della divisione dà il vantaggio di tenere bassi i numeri, semplificando i calcoli, senza alterare il risultato finale.

E adesso un po’ di ricorsione

Continuando con l’esempio, si può applicare lo stesso procedimento al numero 1.234, il che porta a:

12.345  ≡  (123 * 3 + 4) * 3 + 5  (mod 7),

E continuare fino ad esaurire le cifre del numero di partenza:

12.345  ≡  (((1 * 3 + 2 ) * 3 + 3) * 3 + 4) * 3 + 5  (mod 7).

L’algoritmo di calcolo è a questo punto semplice da visualizzare:

1. partendo dalla prima cifra a sinistra, si moltiplichi la cifra per 3 e si aggiunga la cifra successiva;
2. se non sono state esaurite le cifre, si moltiplichi il risultato per 3 e si aggiunga la cifra successiva; eventualmente si eliminino i 7 in eccesso;
3. il processo di calcolo si arresta una volta esaurite le cifre; tolti i 7 in eccesso, quello che rimane è il resto cercato.

Nel nostro esempio:

• 1 * 3 + 2 = 5
• 5 * 3 + 3 = 18  ≡  4
• 4 * 3 + 4 = 16  ≡  2
• 2 * 3 + 5  = 11  ≡  4

Il resto della divisione di 12.345 per 7 è quindi 4. Perciò 12.345 non è divisibile per 7.

Criteri di divisibilità per altri numeri

Quanto è estendibile questo approccio?
Un caso molto simile si ha per la divisibilità per 13. Sempre partendo da 12.345, si può infatti osservare che:

12.345  =  1234 * 10 + 5  =  1.234 * (13 – 3) + 5 = 1.234 * 13 – 1.234 * 3 + 5

Come nel caso precedente, il primo termine della somma (1.234 * 13) dà contributo nullo al resto della divisione per 13, quindi può essere ignorato. La differenza fondamentale qui è il segno meno che compare davanti al secondo termine.

Ricorsione!

Applicando lo stesso procedimento al numero 1.234, fino a esaurire le cifre, si ha:

12.345  ≡  (-(-(-1 * 3 + 2 ) * 3 + 3) * 3 + 4) * 3 + 5  (mod 13).

L’algoritmo di calcolo in questo caso diventa:

1. partendo dalla prima cifra a sinistra, si moltiplichi la cifra per -3 e si aggiunga la cifra successiva;
2. se non sono state esaurite le cifre, si moltiplichi il risultato per -3 e si aggiunga la cifra successiva; eventualmente si eliminino i 13 in eccesso;
3. il processo di calcolo si arresta una volta esaurite le cifre; tolti i 13 in eccesso, quello che rimane è il resto cercato.

Nel nostro esempio:

• -1 * 3 + 2 = -1
• -(-1) * 3 + 3 = 6
• -6 * 3 + 4 = -14  ≡  -1
• -(-1) * 3 + 5  = 8

Il resto della divisione di 12.345 per 13 è perciò 8. Quindi 12.345 non è divisibile nemmeno per 13.

Ma il modulo può essere negativo?

Nell’esempio appena mostrato, per due volte ci siamo trovati -1 come valore di congruenza.
In realtà, intendendo il modulo come il resto di una divisione, dovremmo avere sempre un numero positivo. In particolare, esaminando il caso della divisibilità per 13, dovremmo aspettarci come possibili resti della divisione i numeri da 0 a 12.

Ma, ricordando come funziona l’aritmetica modulare, sappiamo che possiamo aggiungere o togliere quante volte si vuole il valore del modulo (13, in questo caso), senza alterare la congruenza. Quindi -1 è congruente a -1 + 13 = 12. Solo conviene continuare il calcolo con -1, per diminuire la complessità del calcolo stesso.

Sono possibili altri criteri di divisibilità basati sullo stesso principio?

Il trucco su cui si basano i due criteri di divisibilità mostrati si basa sulla vicinanza del numero (primo) in esame (7 o 13) a 10, la base del nostro sistema di numerazione.
In realtà si può seguire questo procedimento anche nel caso in cui un multiplo del numero in esame sia vicino a una potenza di 10.

Ad esempio, si osservi che 17 * 6 = 102, e vediamo come costruire un criterio di divisibilità per 17.  Sempre partendo dal nostro 12.345, lo si divida in gruppi di due cifre, partendo da destra:  1 23 45.

12.345 = 123 * 100 + 45 = 123 * (102 -2) + 45 = 123 * 17 * 6 – 123 * 2 + 45.

Anche in questo caso il primo termine della somma, essendo multiplo di 17, dà contributo nullo al calcolo del resto, quindi si ha:

12.345  ≡  -123 * 2 + 45 (mod 17).

Applicando la stessa trasformazione a 123, si ha:

12.345  ≡  -(-1 * 2 + 23) * 2 + 45 (mod 17).

Quindi l’algoritmo procede così:

1. separate le cifre del numero di partenza in coppie, a partire dalla destra;
2. si moltiplica il primo gruppo da sinistra per -2 e si somma il gruppo successivo, eventualmente eliminando gli eccessi di 17;
3. si continua così, moltiplicando il risultato per -2 e sommando il gruppo successivo, fino all’esaurimento dei gruppi;
4. eliminati gli eventuali eccessi di 17, si ottiene il resto finale.

Nel nostro caso:

• 1 23 45
• –1 * 2 + 23 = 21   ≡  4
• -4 * 2 + 45 = 37  ≡  20  ≡  3

Il resto della divisione di 12.345 per 17 è pari a 3, quindi 12.345 non è divisibile per 17.

---

È possibile trovare ancora qualche criterio di divisibilità con questo approccio?

Sì, ma a costo di calcoli via via più complessi, che vanno quindi a minare il presupposto di questa ricerca, quello di rendere semplice la verifica di divisibilità, al livello di essere eseguibile a mente, anche a fronte di numeri con molte cifre.
Chi volesse provare comunque a scoprire uno di questi algoritmi, potrebbe partire dal fatto che 999 è divisibile per 37. Un criterio di divisibilità per 37, basato sul raggruppamento del numero di partenza in gruppi di 3 cifre, non è quindi complicatissimo da ricavare.

---

Foto di apertura di Rudy and Peter Skitterians da Pixabay.