Dalla prova del nove
ad un criterio generale di divisibilità.

Da una ricerca di Vittorio De Petris e Giuseppina Amedoro, Corso CIIM-CIDM per Animatori Formazione Permanente, Perugia 14-21 ottobre 1984

1 - Quoziente e resto, figlio e figliastro della divisione.

Non tutti si rendono conto, facendo una divisione, che essa dà luogo a due risultati: quoziente e resto. Il primo è il più noto e in genere è il solo che viene preso in considerazione. Il secondo è di solito trascurato, quasi sempre considerato con fastidio, come un corpo estraneo, di cui si farebbe volentieri a meno. La maggior parte degli autori di testi scolastici cerca sempre di mettere nei problemi numeri divisibili tra loro in modo tale che eventuali divisioni abbiano sempre per resto zero. Gli studenti sono così abituati ad ottenere quozienti interi che ritengono (spesso a ragione) di aver sbagliato qualcosa se capita loro di ottenere quozienti con cifre decimali, specialmente se periodiche. Le calcolatrici, che hanno soppiantato definitivamente il noioso calcolo a mano, ma hanno anche completamente trasfigurato il "povero" resto, ridotto ad una sequenza di cifre decimali, per lo più periodiche, che la calcolatrice tronca bruscamente dopo l'ottava cifra del visore (1). Il resto sopravvive in alcune applicazioni di calcolo per computer. Ad esempio, nei vecchi linguaggi di programmazione, la funzione a mod b serviva proprio a dare il resto della divisione tra gli interi a e b. Nel foglio di calcolo più diffuso, Excel, esiste in libreria una funzione =RESTO(a;b) che fornisce ugualmente il suddetto resto. Pochi sanno a cosa serve calcolare il resto di una divisione. In questo articolo, che si potrebbe giudicare perfettamente aderente alla moda americana del politically correct, ci proponiamo di "riabilitare" il resto, facendo vedere alcune sue proprietà e un bel po' di interessanti applicazioni.
______________________
(1) Per ottenere il resto, con la calcolatrice, dopo aver calcolato il quoziente, basta togliere la parte intera e poi moltiplicare per il divisore. Ad esempio, per calcolare il resto della divisione tra 137 e 15 , dividiamo 137 : 15 ottenendo 9.1333333.... Togliendo la parte intera 9 e moltiplicando per 15 otteniamo 1,9999995, che viene arrotondato (per recuperare l'errore prodotto dal troncamento della calcolatrice). Si ottiene così 2 che è il resto della divisione tra 137 e 15.

2 - Uno sguardo nel passato.

Uno dei primi usi dei resti è molto antico: si tratta della cosiddetta prova del nove, usata per verificare la correttezza dei calcoli. Pochi erano consapevoli che stavano usando i resti della divisione per nove e che la procedura per eseguire la prova era basata sulle proprietà dei resti, come vedremo più avanti. Quasi tutti sapevano che non sempre la prova del nove riesce a scovare gli errori. Certamente, se la prova dà esito negativo, occorre rifare i calcoli e vedere dove è stato commesso l'errore. Ma se la prova dà esito positivo, non possiamo essere certi di aver calcolato correttamente. Alcuni errori possono infatti sfuggire alla prova del nove. Se, anziché fare la prova del 9 si facesse la prova del 7, sarebbero scovati molti più errori. Dice infatti Luca Pacioli (Summa de arithmetica, geometria, proportioni et proportionalitate, 1494) :

"...La prova del .7. de più ci chiaresci che non quella del .9. sequita per questo la prova del .7. esser men rea di quella del .9. e per conseguente quella del .9. essere più rea." e continua, però, affermando "questa del .7. non si pò pigliare se non partendo [dividendo]: e non si piglia infilzando le figure [sommando le cifre] del numero sì como facemo per .9."

Come abbiamo detto, pur essendo usata frequentemente, non veniva data alcuna giustificazione alla prova del nove, almeno fino al 1202. In tale anno veniva pubblicato il Liber Abbaci di Leonardo Pisano detto il Fibonacci, dove per la prima volta si trovava una precisa giustificazione della prova (già nota ai matematici arabi ed indiani), partendo da un esempio: la moltiplicazione di 37 x 37 = 1369. Egli nota:

"...quando si divide un numero in parti e poi si moltiplica ciascuna delle parti per un dato numero, quelle moltiplicazioni, raccolte insieme, sono uguali alla moltiplicazione di tutto il numero [che si è] diviso per il numero per il quale tutte le parti dello stesso erano state moltiplicate. Quindi, le moltiplicazioni 36 x 37 e 1 x 37, assieme congiunte, uguagliano quella di 37 x 37. Però dalla moltiplicazione di 36 x 37 proviene un numero che è originato da una certa quantità di 9, essendo 36 costituito da 9. Per cui il numero che sorge da 36 x 37, se diviso per 9, non resterà nulla per indivisibile. Ancora, la moltiplicazione di 1 per 37 è uguale alla moltiplicazione di 1 x 36 e di 1 x 1. Ma dalla moltiplicazione di 1 x 36 proviene un numero perfettamente divisibile per 9, mentre la moltiplicazione di 1 x 1 risulta indivisibile per 9. Quindi da 37 x 37 : 9 resta 1, come dalla somma di tutte le cifre che si trovano nel prodotto 1369".

Questa lunga citazione dimostra che, pur se limitato alla divisibilità per 9, lo stesso ragionamento avrebbe potuto condurre agli altri criteri di divisibilità. Una regola generale della divisibilità era quindi alla portata della matematica medioevale. Al tempo del Pacioli, oltre al criterio di divisibilità per 9 erano noti solo quelli del 2, 3, 5, 6, 8 e 10, tutti meno validi del 9 per il controllo delle operazioni.

Occorrerà arrivare a Pascal (1623-1662) ed al suo De numeris multicibus ex sola characterum numericorum additione agnoscendis (1650) per ottenere un criterio di divisibilità applicabile a qualsiasi numero.

3 - Le classi-resto modulo k.
Prima di entrare nel merito della prova del nove (o di un'altra prova qualsivoglia) e dei criteri di divisibilità, è bene fare alcune considerazioni generali sui resti delle divisioni e sulle loro proprietà.

I resti dei numeri naturali divisi per un numero prefissato k, si comportano come le ore dell'orologio, o i giorni della settimana o i mesi dell'anno. Arrivati all'ultimo, si ricomincia da capo. E' come quando si fa la conta tra un gruppo di bambini. Chi sta facendo la conta, arrivato all'ultimo bimbo da contare, "salta" i multipli del numero ottenuto e poi continua a contare i numeri rimanenti. Il fatto che i resti si ripetano sempre con la stessa sequenza, fa sì che essi costituiscano una struttura "modulare". Da qui il nome di "modulo" dato all'operazione che associa ad una coppia di numeri, il resto della loro divisione. Dati due numeri interi n e k (k ¹ 0), definiamo l'operazione

n mod k = r

che associa alla coppia (n,k) il numero intero r dato dal resto della divisione tra n e k.

Di solito nelle divisioni n è maggiore di k, ma può anche verificarsi che n sia minore; in questo caso il resto sarà n stesso. Dall'aritmetica elementare si sa che il resto della divisione tra due naturali n e k è sempre minore di k:

n mod k < k

Dividendo tra loro due numeri qualsiasi n e k il resto sarà necessariamente uno dei termini della successione

{0, 1, 2, 3, ..., (k-1)}

Una volta fissato k, possiamo stabilire una corrispondenza tra i vari numeri naturali e i rispettivi resti modulo k.
Tale relazione costituisce una corrispondenza univoca o applicazione, poiché per ogni n Î N esiste uno (ed un solo) resto al quale può essere associato nella divisione per k.
Viceversa, ci sono infiniti numeri naturali che, divisi per k, danno lo stesso resto. Due numeri che, divisi per uno stesso numero k, danno lo stesso resto, si dicono congruenti modulo k.
In simboli:

a º b mod k (si legge a congruente b modulo k)

E' facile verificare che la relazione di congruenza gode delle proprietà

  • riflessiva, poiché ogni numero è congruente con se stesso;
  • simmetrica, poiché se n1 º n2, allora anche n2 º n1
  • transitiva, poiché se n1 º n2 e n2 º n3, allora n1 º n3
Si tratta quindi di una relazione di equivalenza.

Un insieme in cui sia presente una relazione di equivalenza, può essere suddiviso in classi di equivalenza, cioè in tanti sottoinsiemi ciascuno dei quali è costituito da elementi tra loro equivalenti. Si ottiene così una partizione dell'insieme.
A questo punto, possiamo sostituire gli infiniti termini di ogni sottoinsieme con un unico termine (per comodità, il più piccolo di ciascuna classe). Compiamo cioè un'operazione nota in teoria degli insiemi come "passaggio a quoziente". Un insieme viene suddiviso in sottoinsiemi costituiti da un solo elemento in rappresentanza di tutti gli elementi della stessa classe, ad esso equivalenti. E' come quando, in un manuale di scienze naturali, l'insieme dei vertebrati è raffigurato mediante un disegno in cui compaiono un cavallo, un'oca, una biscia, una rana e un salmone in rappresentanza delle cinque classi dei mammiferi, uccelli, rettili, anfibi e pesci.
Nei due disegni a lato vediamo un esempio di partizione dell'insieme dei naturali secondo le classi di equivalenza modulo 6 ed il successivo passaggio a quoziente.

In una relazione di equivalenza, vale il principio di sostituzione, per il quale una data proprietà non cambia se, al posto di un elemento, si sostituisce un qualsiasi altro elemento della stessa classe.
Vediamone un esempio:
Un Tizio ci rivolge la seguente domanda: "Oggi è venerdì. Che giorno sarà tra 100 giorni?"
Potremmo metterci ad elencare i giorni della settimana dopo il venerdì fino a contarne 100, ma è senz'altro più facile calcolare 100 mod 7 = 2. Sostituendo 2 a 100, riformuliamo la domanda: "Che giorno sarà tra 2 giorni?" La risposta è immediata: "Domenica!"

4 - Aritmetica delle classi-resto mod k.
Un falegname sta tagliando una tavola a lunga 2,55 metri in pezzi da 60 cm. Ne ottiene 4 e gli resta un pezzo r' di 15 cm. Da un'altra tavola b lunga 2,00 metri, tagliata sempre in pezzi da 60 cm ottiene 3 parti e gli resta un pezzo r" lungo 20 cm. Se avesse avuto un unica tavola (a+b) lunga 4,55 metri, avrebbe ottenuto 7 parti e gli sarebbe avanzato un pezzo (r'+r") lungo 35 cm.
Si ha cioè:

a = mk + r'
b = nk + r"

(a+b) = (mk + r') + (nk + r") = (m+n)k + (r'+r").

Nell'ultima espressione il termine (m+n)k è multiplo di k, quindi, diviso per k, dà per resto 0. Può quindi essere eliminato. Rimane perciò il resto (r'+ r"). Si ha pertanto:

(a+b) mod k = r'+r"

Va detto che se i due pezzi avanzati da ciascuna tavola avessero avuto una lunghezza (r'+r") ³ k avremmo potuto ottenere un altro pezzo di lunghezza k e un nuovo resto r''' uguale al resto mod k della somma tra r' e r". Possiamo così affermare:

Il resto mod k della somma di due numeri a e b è uguale alla somma dei resti mod k dei due numeri a e b, a meno di multipli di k.

Una proprietà analoga si verifica per il prodotto.

a = (mk + r')
b = ( nk + r")
a x b = (mk+r')(nk+r") = mnk2 + mkr" + nkr' + r'r"

Nell'ultimo polinomio i primi tre termini sono multipli di k. Essi, divisi per k, danno per resto 0 e quindi si possono eliminare. Rimane solo il termine (r'r"). Si ha pertanto:

(a x b) mod k = r'r"

Anche per il prodotto r' r" vale la stessa considerazione fatta in precedenza per la somma r'+r" nel caso in cui risulti r'r" ³ k. Il prodotto r'r" sarebbe sostituto dal resto di r'r" mod k. Possiamo quindi affermare che

Il resto mod k del prodotto di due numeri a e b è uguale al prodotto dei resti mod k dei numeri a e b, a meno di multipli di k.

5 - Dalle proprietà delle classi resto alla prova del nove

La prova del nove si basa proprio sulle due proprietà or ora viste. Dopo aver fatto un'operazione, si ripete di nuovo il calcolo, sostituendo i due fattori con i rispettivi resti modulo 9 e calcolando il prodotto dei due resti, sempre nel modulo 9. Le varie operazioni sono facili, poiché i resti modulo 9 si ottengono sommando le cifre dei termini (e sommando eventualmente anche quelle del risultato ottenuto, fino ad ottenere un numero di una sola cifra). Il valore ottenuto dev'essere uguale al resto modulo 9 del prodotto ottenuto.

Prendiamo ad esempio, il prodotto 3621 x 58 . Sostituendo i due fattori con il loro resto modulo 9 si ottengono i resti 3 e 4 , che moltiplicati danno 12, il cui resto modulo 9 è 3. Il resto modulo 9 del prodotto 210018 da anch'esso 3. La prova si dice riuscita poiché i due termini nei quadranti inferiori dello schema sono identici.
 
P.S. : per rivedere l'animazione clicca sul tasto "Aggiorna" del Browser.

Se volessimo usare un altro numero al posto del nove, ad esempio il 7, come proposto da Pacioli, dovremmo trovare una regola per calcolare il resto modulo 7 dei termini, ma a quell'epoca i matematici non erano ancora arrivati a tale livello di conoscenze. Il primo ad conseguire tale risultato fu, come detto in precedenza, Pascal nel 1650.

6 - Il metodo di Pascal per il calcolo dei resti mod 7.

Il metodo proposto da Pascal utilizza le proprietà delle classi resto. Si voglia verificare, ad esempio, se il numero 75342 sia o no divisibile per 7.
Il numero può essere scritto in forma polinomiale, trasformandolo cioè in un polinomio formato dalla somma delle cifre moltiplicate per le rispettive potenze di 10, in relazione al loro valore posizionale:

7 x 104 + 5 x 103 + 3 x 102 + 4 x 101 + 2 x 100
(1)

Pascal trascrive il polinomio in una tabella a due righe, mettendo le cifre del numero nella prima riga e le rispettive potenze del dieci nella seconda riga:

75342
104103102101100

Sostituisce quindi i termini della seconda riga con i rispettivi resti modulo 7:

75342
46231

Ora occorre moltiplicare ciascuno dei termini della prima riga per il corrispondente sotto di esso nella seconda riga. Quindi si sommano i prodotti così ottenuti:

7 x 4 + 5 x 6 + 3 x 2 + 4 x 3 + 2 x 1 = 28 + 30 + 6 + 12 + 2 = 78 (2)

Poiché 78, diviso per 7, dà per resto 1, anche il numero 75342, diviso per 7, darà per resto 1.
In pratica Pascal calcola il resto modulo 7 del polinomio (1), nel quale le potenze di 10 vengono sostituite dai rispettivi resti modulo 7, ottenendo così la (2). Ciò è reso possibile dalla relazione di equivalenza tra i numeri di una stessa classe resto e dal conseguente principio di sostituzione visto al § 2.

Il ragionamento di Pascal, oltre che nella divisibilità per 7, è applicabile a qualunque altro criterio di divisibilità. Esso resta valido anche se si opera con sistemi di numerazione non decimali, come dichiara lo stesso Pascal "...et non solum in progressione denaria, sed in quacumque progressione instituantur numeratio".

7 - Le sequenze-resti . Criterio generale di divisibilità.

Nel descrivere il metodo di Pascal, abbiamo incontrato una sequenza di numeri (... 4 6 2 3 1), data dai resti modulo 7 delle successive potenze di 10. Tale sequenza può essere utilizzata per qualunque numero di cui si voglia calcolare il resto modulo 7. Infatti, se si vuole calcolare il resto mod 7 di un altro numero, si dovranno sostituire le cifre nella prima riga, mentre resteranno fissi i termini della seconda. Questi dovranno essere quindi calcolati una volta per tutte, trascrivendoli da qualche parte, per poterli utilizzare ogni volta che occorre.
Vediamo allora di trovare un modo per calcolarli senza fare troppa fatica:

  • Il primo termmine (a partire da destra) è sempre 1
  • Tutti gli altri termini si ottengono moltiplicando per 10 il valore del termine precedente e calcolando poi il resto modulo 7 del prodotto ottenuto
  • Il procedimento si ferma se si ottiene per resto 0, nel qual caso si ha una sequenza finita, oppure se si ottiene di nuovo un resto già ottenuto in precedenza, nel qual caso si ha una sequenza periodica e i termini si ripetono a partire dalla ricorrenza.

1 mod 7 = 1
(1x10) mod 7 = 10 mod 7 = 3
(3x10) mod 7 = 30 mod 7 = 2
(2x10) mod 7 = 20 mod 7 = 6
(6x10) mod 7 = 60 mod 7 = 4
(4x10) mod 7 = 40 mod 7 = 5
(5x10) mod 7 = 50 mod 7 = 1

Nell'ultima riga abbiamo ottenuto di nuovo il resto 1, come per il primo termine. E' chiaro perciò che, continuando a calcolare, si otterranno periodicamente i resti precedenti. Si può pertanto concludere che il criterio di divisibilità per 7 darà luogo ad una sequenza-resti periodica, i cui termini (che vanno letti da destra verso sinistra) sono:

... 5 4 6 2 3 1

Per vedere se un numero n qualsiasi è divisibile o no per 7, si procede pertanto nel seguente modo:

  1. Si scrivono su una riga le cifre del numero n.
  2. Si scrivono sotto ciascuna di esse altrettanti termini della sequenza-resti mod. 7 (a partire da destra), usando, se occorre le ulteriori cifre periodiche della sequenza.
  3. Si moltiplicano i termini della prima riga per i corrispondenti nella seconda.
  4. Si sommano i prodotti così ottenuti.
  5. Si calcola il resto mod 7 del valore ottenuto.
  6. Se il resto mod 7 è zero, allora il numero n è divisibile per 7

La regola vista per il 7, vale per qualunque altro numero, di cui si vuole determinare il criterio di divisibilità. E' sufficiente infatti sostituire il numero 7 con la lettera k nel secondo, quinto e sesto punto. La regola resta perfettamente valida. Essa costituisce quindi un criterio generale di divisibilità valido per determinare se un qualsiasi numero n sia o no divisibile per numero prefissato k.
Per ogni criterio di divisibilità occorrerà calcolare la sequenza-resti relativa al numero usato come base del criterio stesso. Vale lo stesso procedimento descritto all'inizio di questo paragrafo, sostituendo la lettera k al posto del valore 7.

Facciamo alcuni esempi. Essi serviranno, oltre che a rafforzare la conoscenza della regola, anche per comprendere meglio i criteri di divisibilità, spesso messi nei testi scolastici senza alcuna giustificazione, considerati come altrettante regole indipendenti, senza farli derivare tutti da un unico criterio generale. Gli alunni vengono così indotti ad imparare le regole in modo mnemonico e ad applicarle in modo automatico, senza stimolare in loro capacità di osservazione e di analisi.

8 - Divisibilità per 2 e per 5.

Applicando al 2 e al 5 i primi due passi della regola, si ottiene la sequenza:

... 0 0 0 0 0 0 1

Moltiplicando le cifre di un qualsiasi numero per i rispettivi termini della predetta sequenza, resterà solo l'ultima cifra. Tutte le altre cifre infatti vengono moltiplicate per 0 e quindi si annullano. Ecco spiegato, in modo razionale, il motivo per cui, nei criteri di divisibilità per 2 e per 5 si considera solo l'ultima cifra.

 7 - Divisibilità per 3 e per 9.

Il resto di 10 mod 3 o mod 9 è 1. Moltiplicando 1 per 10, si ha ancora 10 e si ottiene di nuovo il resto 1. La sequenza-resti è dunque periodica e formata dalla cifra 1 ripetuta indefinitamente:

... 1 1 1 1 1 1 1

Le varie cifre del numero di cui si vuole calcolare il resto, moltiplicate per 1, resteranno invariate. La somma finale si ottiene dunque sommando semplicemente le cifre del numero stesso, ovvero "infilzando le figure", per dirla con il linguaggio di Luca Pacioli. Tale semplicità ha fatto preferire la prova del nove ad altre prove, che pure avrebbero potuto fornire un minor numero di errori non rivelati. E' proprio ciò che Leonardo Pisano aveva dimostrato, senza però estendere il ragionamento agli altri casi, come avrebbe fatto Blaise Pascal circa quattro secoli e mezzo dopo.
Per inciso, va detto che il numero di codice fiscale viene controllato usando il criterio di divisibilità per 26, dopo aver sostituito le varie lettere con i rispettivi valori, secondo apposite tabelle di trasformazione.

9 - Divisibilità per 7.

Abbiamo già visto la sequenza dei resti modulo 7 da impiegare per definire il criterio di divisibilità per 7. Vogliamo qui apportare una piccola modifica, che ne rende più facile la memorizzazione. Basta semplicemente considerare i resti della sequenza all'interno degli interi relativi nell'insieme-quoziente Z|7. In tale insieme, i termini 5, 4 e 6, possono essere sostituiti dagli equivalenti numeri negativi -2, -3, -1 (basta togliere 7 da ciascuno di essi). La sequenza resti mod 7 diventa perciò:

... -2 -3 -1 + 2 +3 +1.

Essa è così più facile da memorizzare; leggendola da destra verso sinistra si ha: "1, 3, 2, -1, -3, -2"
E' chiaro che, al quarto punto delle regola, va calcolata la somma algebrica. Proviamo a ripetere il calcolo fatto in precedenza, usando la nuova sequenza-resti:

75342
-3-1231
-21-56122

Sommando i termini dell'ultima riga si ottiene -6, che equivale a 1 (basta aggiungere 7)

E' sempre possibile aggiungere 7 o un suo multiplo, tutte le volte che si ottiene un valore negativo. Il numero 7 e i suoi multipli sono elementi della classe resto [0]. Essi sono elementi neutri nell'addizione e quindi si possono aggiungere o togliere a piacere.

10 - Divisibilità per 11.

Calcoliamo la sequenza-resti modulo 11:

Il primo termine è 1
Il secondo termine è il resto mod 11 di 10. Ma 10 è minore di 11, quindi il resto è 10 stesso.
Il terzo termine si ottiene moltiplicando il resto precedente per 10. Si ha 100 mod 11 = 1
Avendo ottenuto di nuovo 1, la sequenza-resti diventa periodica:

... 10, 1, 10, 1, 10, 1, 10, 1

Come per il 7, possiamo sostituire il numero 10 della sequenza, con il suo equivalente negativo -1, ottenuto togliendo 11. La sequenza-resti modulo 11 diventa:

... -1, +1, -1, +1, -1, +1

Proviamo ad usare tale sequenza, per calcolare il resto modulo 11 del numero 786452:

786452
-11-11-11
-78-64-52

Nella terza riga si ottengono le cifre stesse del numero dato, con segni alternati + e -
Dalla somma algebrica di tali cifre si ottiene un numero che consente di calcolare il resto modulo 11 del numero dato:

-7 + 8 - 6 + 4 - 5 + 2 = 14 - 18 = - 4 ovvero, aggiungendo 11, il resto 7.

Ecco spiegato il criterio di divisibilità per 11 che troviamo nei testi scolastici, senza che venga fornita alcuna spiegazione: "Si sommano le cifre di posto dispari, poi si sommano quelle di posto pari, infine si trova la differenza tra le due somme...".

11 - Caratteristiche delle sequenze-resti.

Costruiamo una tabella contenente tutte le sequenze resti, a partire da quelle mod. 2, per finire a quelle mod. 125.

Uno sguardo alla tabella a lato consente di osservare la presenza di diversi tipi di sequenze:

  • finite, tutte le volte che il modulo è un divisore di 10 o i suoi fattori primi sono costituiti esclusivamente da potenze di tali divisori (2, 4, 5, 8, 10, ... 25, 125, ecc.). La lunghezza della sequenza è data dal massimo esponente delle potenze di 2 o di 5, che costituiscono i fattori primi del modulo;
  • periodiche, quando tra i fattori primi del modulo compaiono fattori diversi dal 2 e dal 5. Se il modulo è primo rispetto a 5 e rispetto a 2, la sequenza sarà semplicemente periodica (3, 7, 9, 11). Se il modulo ha fra i suoi fattori anche il 2, il 5 o loro potenze, la sequenza avrà una parte non periodica ed una periodica (es. il mod. 6 e il mod. 12).

12 - Altri criteri di divisibilità.

Vediamo qualche altro criterio, in aggiunta a quelli già visti nel paragrafo precedente, desumendolo dalle sequenze resti contenute nella precedente tabella.

Per il 4, si calcola il resto del numero che si ottiene sommando all'ultima cifra il doppio della penultima.

Per il 6, si sommano tutte le cifre tranne l'ultima, si moltiplica il risultato per 4, si aggiunge l'ultima cifra e si calcola il resto mod. 6 del numero ottenuto.

Per l'8 si somma l'ultima cifra con il doppio della penultima e con il quadruplo della terzultima. Si calcola infine il resto mod. 8 del numero ottenuto.

Per il 12 si sommano tutte le cifre tranne le ultime due, si moltiplica per 4 e poi si aggiunge il numero formato dalle ultime due cifre.

Per il 25 e per il 125, si calcolano i resti dei numeri costituiti rispettivamente dalle ultime due e dalle ultime tre cifre del numero dato.

Proviamo a trovare un criterio di divisibilità per 13. Usando la regola vista al §7, cerchiamo la sequenza resti mod 13 delle successive potenze di 10. Si ottiene ... 4, 3, 12, 9, 10, 1. Sostituendo i numeri prossimi al 13 con i rispettivi valori negativi (togliendo 13) abbiamo una sequenza più facile da memorizzare: ...4, 3, -1, -4, -3, 1. Leggendo da destra verso sinistra: uno, -tre, -quattro, -uno, tre, quattro, ...
Facciamo una prova:
Trovare il resto mod 13 del numero 176534. Scriviamo le cifre su una riga, i termini della sequenza sulla seconda e i prodotti sulla terza:

1
7
6
5
3
4
4
3
-1
-4
-3
1
4
21
-6
-20
-9
4

La somma algebrica dei termini della terza riga è uguale a -6. Avendo ottenuto un valore negativo, aggiungiamo 13 ed otteniamo 7, che è il resto cercato.

13 - Qualche piccolo trucco.

Per tutti i criteri, valgono i seguenti accorgimenti:

  • Prima e durante il procedimento di calcolo è sempre possibile eliminare le cifre il cui valore è uguale o multiplo di k
  • Prima e durante il procedimento di calcolo è sempre possibile eliminare due o più cifre la cui somma è uguale o multipla di k
  • Durante il procedimento di calcolo è sempre possibile ridurre a meno di k i valori ottenuti, sia nei calcoli intermedi, sia nei risultati finali.
  • E' sempre possibile applicare ricorsivamente il criterio agli stessi valori finali ottenuti. Dopo un po' si otterrà un valore sufficientemente piccolo, sul quale sarà più agevole calcolare il resto mod. k.

14 - Le classi resto dal punto di vista dell'algebra moderna.

L'aritmetica delle classi resto si presta ad alcune considerazioni algebriche. Prendiamo insieme formato dalla varie classi resto il cui modulo k sia un numero primo, ad esempio l'insieme delle classi resto modulo 5, costituito dalla cinque classi [0], [1], [2], [3],[4]. Le classi possono essere addizionate o moltiplicate fra loro. Il risultato sarà ancora un elemento dell'insieme quoziente N|5 . Proviamo a costruire le due tabelle, additiva e moltiplicativa:

+01234  ×01234
001234000000
112340101234
223401202413
334012303142
440123404321

Nella tabella additiva vediamo che l'operazione è una legge di composizione interna (il risultato è sempre un elemento dell'insieme considerato). L'operazione di addizione è associativa. Esiste un elemento neutro, la classe [0], che addizionata ad un qualsiasi elemento dà per risultato l'elemento stesso. Tra i risultati di ogni riga compare sempre l'elemento neutro [0]; ciò vuol dire che ogni elemento ha il suo elemento inverso cioè un elemento che associato ad esso dà per risultato l'elemento neutro. Il verificarsi di tutte queste proprietà conferisce all'insieme quoziente N|5 la struttura algebrica di gruppo rispetto all'addizione. Si tratta di un gruppo abeliano (in onore del matematico Abel) poiché l'addizione è commutativa. Il nostro insieme ha dunque due operazioni binarie, l'addizione (che è anche associativa) e la moltiplicazione. Quest'ultima è distributiva rispetto alla prima, poiché x × (y + z) = x × y + x × z. La presenza di tutte queste proprietà conferisce all'insieme la struttura algebrica di anello. Dato che il nostro anello possiede un elemento neutro per la moltiplicazione e ogni suo elemento eccettuato lo zero ha un elemento inverso, gli si può attribuire una ulteriore qualifica, quella di corpo. In un corpo ogni equazione di primo grado ha almeno una soluzione. Ad esempio, per risolvere l'equazione 3x = 2 basta scorrere la riga del 3, fino ad incontrare il 2 ed andare a vedere in corrispondenza il valore in testa alla colonna, che rappresenta la soluzione cercata. Nel nostro caso si ha x = 4. Osservando che ogni riga della tabella moltiplicativa contiene tutti gli elementi, siamo sicuri di ottenere sempre la soluzione per qualsiasi equazione.

Diversa è la situazione se passiamo a considerare un insieme formato dalla classi resto modulo k, nel caso in cui k sia un numero non primo. Consideriamo ad esempio l'insieme quoziente N|6, formato dalle sei classi resto modulo 6: [0], [1], [2], [3], [4], [5] e costruiamo le due tabelle dell'addizione e della moltiplicazione:

+012345 ×012345
00123450000000
11234501012345
22345012024024
33450123030303
44501234042042
55012345054321

Non vi sono particolari novità nell'addizione, rispetto alla quale l'insieme N|6 presenta ancora una struttura di gruppo. Se andiamo invece a considerare la moltiplicazione, osserviamo la presenza di zeri anche laddove i fattori sono diversi da 0. Ciò porta a situazioni alquanto paradossali. Ad esempio, dato che [2] × [3] = [0], si ha che, all'inverso, [0] : [2] = [3]. Si hanno cioè divisori dello zero. Cade così la legge di annullamento di un prodotto, per la quale un prodotto è nullo se lo è almeno uno dei due termini. Osservando che in alcune righe compare più volte uno stesso risultato, si ha per conseguenza che una semplice equazione di primo grado, come ad esempio 4x = 2, può avere ben due soluzioni: 2 e 5. Viceversa, la mancanza di alcuni termini lungo una riga della tabella, fa si' che alcune equazioni siano impossibili, anche se i loro coefficienti non sono nulli. Ad esempio l'equazione 3x = 5 non ha alcuna soluzione, poiché nella riga del 3 non compare alcun 5.

Quando il numero k che costituisce il modulo della classe resto è un numero primo l'insieme quoziente N|k costituisce un anello di integrità, anzi addirittura un campo (che deve avere le proprietà di un corpo e deve essere dotato di proprietà commutativa). Dato che l'insieme N|k è formato da un numero finito di elementi, il campo in questione è un campo finito, che in onore di Galois è stato chiamato campo di Galois, in sigla GF (Galois Field).

ESERCIZI

1. Trova il resto mod 13 dei numeri 166935 e 362115.
Prepariamo le due tabelle, scrivendo sulla prima riga le cifre dei due numeri e sulla seconda la sequenza-resti mod 13, vista al § 12:
 
... 4 , 3, -1, -4, 3, 1.

Moltiplichiamo ora i termini della prima riga per i corrispondenti della seconda ottenendo i prodotti indicati nella terza riga delle rispettive tabelle. Sommando i prodotti ottenuti otteniamo i resti:
 
166935 mod 13 = -24, che viene corretto aggiungendo due volte 13 e diventa quindi 2.
362115 mod 13 = 26, che è un multiplo di 13 e quindi vale 0.

2. Risolvi l'equazione 4x = 3 nell'insieme della classi resto modulo 6.

Scorrendo la riga del 4 nella tabella moltiplicativa delle classi resto modulo 6, non si riesce a trovare l'elemento [3], dunque la nostra equazione è impossibile.

3.Andrea, Bruno, Carlo, Domenico e Enrico stanno facendo la conta e la somma delle dita è 22. A chi tocca, se la conta comincia da Domenico?

Dato che i ragazzi sono cinque, calcoliamo il resto 22 mod 5 = 2. Il secondo ragazzo dopo Domenico è Andrea.

4.Sulla lavagna un alunno ha eseguito una moltiplicazione. Fa' la prova del nove e verifica se ci sono errori.

324 mod 9 = 0
47 mod 9 = 2
0 x 2 = 0
anche 15318 mod 9 = 0
0
2
0
0

La prova del nove dà esito positivo, ma la moltiplicazione è ugualmente errata. Infatti 324 x 47 = 15228. Come già detto, non sempre la prova del nove riesce a scovare errori.

5. Applica la "prova del sette" alla moltiplicazione precedente e vedi se ci sono errori.
Occorrre trovare il resto mod 7 dei due fattori 324 e 47. Il primo ha per resto 2, il secondo ha per resto 5. I due resti vengono posti sulle prime due caselle dello schema. Moltiplicando 2 x 5 si ottiene 10, che diviso per 7 da resto 3. Ora occorre calcolare il resto mod 7 di 15318, che è uguale a 5. Dunque la prova del 7 ci dice che la precedente moltiplicazione è errata, confermado in tal modo di è esser men rea di quella del 9, come ebbe a dire Luca Pacioli.

6. Durante un esercizio sull'aritmetica delle classi resto, un alunno ha calcolato 5 + 4 = 2. In quale modulo è stata fatta l'addizione?

Dato che 5 + 4, nell'aritmetica decimale fa 9, il risultato 2 si può ottenere solo togliendo 7. L'insieme in cui 7 è un elemento neutro per l'addizione è N|7, Dunque l'alunno sta usando le classi resto modulo 7.
 
7. Il gioco dei fiammiferi. Il gioco consiste nel disporre su un tavolo un numero a piacere di fiammiferi. Dopo aver sorteggiato chi deve fare la prima mossa, si dà inizio al gioco, che consiste nel prelevare a turno dal tavolo un numero di fiammiferi compreso tra uno e tre.
Vince chi riesce a costringere l'avversario a prendere l'ultimo fiammifero. Esiste una strategia vincente per chi fa la prima mossa?
Si calcola il resto modulo 4 del numero di fiammiferi. Nel nostro caso, con 30 fiammiferi, il resto è 2. E' come se ora sul tavolo ci fossero solo i 2 fiammiferi del resto. Alla prima mossa, basta togliere un solo fiammifero, in modo da lasciarne uno al nostro avversario. Fatta la prima mossa, si userà la seguente strategia : qualunque numero di fiammiferi prenderà il nostro avversario, noi ne prenderemo quanti ne occorrono per arrivare a 4 (sommando entrambe le prese). Se egli ne prende 1 noi ne prenderemo 3; se egli ne prende 2 noi ne prenderemo 2; se egli ne prende 3 noi ne prenderemo 1. Essendo 4 un elemento neutro (nelle classi resto modulo 4), la situazione non cambierà: sul tavolo ci sarà virtualmente sempre un solo fiammifero, l'ultimo, che lasceremo al nostro avversario.
Nel caso che i fiammiferi fossero stati 29, il loro resto mod 4 sarebbe stato 1. In tal caso, qualunque mossa avessi fatto, sarei stato destinato comunque a perdere. Avrei potuto tuttavia sperare che il mio avversario, ignorando la regola, commettesse l'errore di lasciare sul tavolo un numero di fiammiferi con il resto mod 4 diverso da 1. La stessa situazione si avrebbe se la prima mossa spettasse al mio avversario e la situazione iniziale gli fosse favorevole.

8. Quanto fa 8 : 4 nell'insieme quoziente delle classi resto modulo 12?

Occorre costruire la riga del 4 nella tabella moltiplicativa delle classi resto mod 12:
 


L'8 compare ben 4 volte, in corrispondenza delle colonne 2, 5, 8, e 11, che rappresentano altrettante risposte valide alla domanda posta.

9. Dimostra che nell'insieme quozione N|k la sottrazione è una legge di composizione interna.
E' sufficiente osservare che le varie righe di una tabella additiva contengono sempre tutti i termini dell'insieme. Per trovare il risultato di una sottrazione si usa la tabella additiva al contrario. Ad esempio, per trovare la differenza 2-5 nella tabella dei resti mod 7, si scorre la riga del 5 e si va a cercare il 2. In testa alla colonna in cui compare il 2 si ha il numero 4. Dunque 2 - 5 = 4. Come rilevato, la presenta di tutti i termini su ciascuna riga ci assicura che il risultato si trova in ogni caso.

Test di Verifica con 20 domande

BIBLIOGRAFIA

Ettore Picutti Sul numero e la sua storia (Feltrinelli)
Lucio Lombardo Radice Istituzioni di Algebra astratta (Feltrinelli)
Alexander Abian La teoria degli insiemi (Feltrinelli)
Irving Adler La nuova matematica (Editrice La Scuola)