Divertiamoci con la Matematica

Umberto Cerruti - Università di Torino

- Diofanto, Euclide e le noci di cocco -

Introduzione

Diofanto
di Alessandria
200 - 284

Hypatia
di Alessandria
370 - 415

Diofanto fu un grande e prolifico matematico dell'antichità. Tra l'altro scrisse un trattato sui numeri poligonali, argomento assai caro a Pitagora. Diofanto è rimasto nella storia soprattutto per i suoi 13 libri dell'Arithmetica. Non ci sono noti gli originali, ma soltanto trascrizioni successive dei primi 6 libri. Si ritiene probabile che questi testi siano pervenuti sino a noi grazie all'interesse suscitato dai commentari di Hypatia, anche questi purtroppo perduti.

Le equazioni diofantine sono equazioni polinomiali in un numero qualsiasi di indeterminate: ciò che le rende particolari è che di esse si cercano soltanto le soluzioni intere.

Le equazioni diofantine di grado maggiore di uno sono spesso difficilissime da risolvere. Non solo: è sovente impossibile persino sapere se hanno soluzioni.

Per esempio stabilire se l'equazione Ax² + By = C ha soluzioni intere (assegati gli interi A, B e C) e uno dei problemi più ardui!

Durante il Secondo Congresso Internazionale del 1900, a Parigi, Hilbert propose ai suoi colleghi matematici 23 problemi. Nel decimo si chiedeva:

Esiste un algoritmo che, data una generica equazione diofantina F, sia in grado di decidere - in tempo finito - se F possiede o meno soluzioni intere?

Nel 1970 Yuri Matiyasevich dimostrò che un tale algoritmo non può esistere, il 10° Problema di Hilbert è indecidibile, proprio come il famoso problema dell'arresto.

Nel seguito ci occuperemo delle più semplici, ma non banali, equazioni diofantine, quelle di grado 1 in due indeterminate, e impareremo a risoverle!

L'algoritmo di Euclide e la sua estensione

Euclide
di Alessandria
325 aC - 265 aC

Malgrado la sua venerabile età, l'algoritmo di Euclide (AE) per il calcolo del massimo comun divisore di una coppia di interi rimane uno degli strumenti assolutamente necessari nell'ambito della teoria dei numeri.

Ricordo che, quando ero bambino, a scuola ci insegnarono a calcolare il massimo comun divisore di due interi partendo dalla loro fattorizzazione.

Questo metodo è ineccepibile su un piano teorico, ma in pratica è inapplicabile, perché a tutt'oggi nessuno è in grado di fattorizzare interi grandi.

Utilizzando AE si può, in maniera efficiente anche con numeri di migliaia di cifre, trovare il più grande intero d che divide due numeri dati a, b senza conoscere i divisori di a e di b.

In quanto segue supponiamo che a, b siano interi tali che a > b > 0.

Denotiamo con MCD(a, b) il massimo comun divisore di a e b. L'osservazione fondamentale di Euclide è stata questa:

(1) MCD(a, b) = MCD(b, a - b)

Questo risulta dal fatto che l'insieme dei divisori comuni di {a, b} è identico all'insieme dei divisori comuni di {b, a - b}.

Se a - b è maggiore di b si può continuare a sottrarre b.

Ad un certo punto si otterrà il resto r della divisione di a per b, r = a - qb, dove q è il quoziente.

Scriveremo a mod b per denotare il resto r.

Esempio 1
10 mod 3 = 1
10 mod 4 = 2
10 mod 5 = 0

Le considerazioni fatte portano ad una espressione più efficiente della (1):

(2) MCD(a, b) = MCD(b, a mod b)

Si noti che, se b > 0, il passaggio dalla coppia (a, b) alla coppia (b, a mod b) è sempre conveniente perché

b < a
a mob b ≤ b - 1 < b

In un numero finito di passi la successione dei resti arriverà a 0, e si avrà:

(3) MCD(a, b) = MCD(d, 0) = d

dove d è l'ultimo resto non nullo.

Vediamo in dettaglio l'algoritmo AE:

Per convenzione inizializziamo la sucessione dei resti con:
r_-1 = a
r₀ = b
Seguono:
r₁ = a mod b = r_-1 mod r₀
r₂ = b mod r₁ = r₀ mod r₁
r₃ = r₂ mod r₁
...
r_k = r_k-1 mod r_k-2
...
0 = r_n = r_n-1 mod r_n-2
Giunti a resto 0 AE termina, e si ha:
d = r_n-1 è MCD(a, b).

Nella tavola sottostante vediamo come esempio il calcolo di MCD(90, 17). Nella prima colonna c'è il numero del passo k, da -1 a n, nella seconda c'è il resto r_k e nella terza il quoziente q_k.

Per k ≥ 1 viene sempre mantenuta la relazione

(4) r_k = r_k-2 - q_k-1r_k-1

All'n-esimo passo si ha r_n = 0. Si noti che q_-1 e q_n non sono definiti.

PASSO k	RESTO r_k	QUOZIENTE q_k
-1	90	***
0	17	5
1	5	3
2	2	2
3	1	2
4	0	***

Tavola 1

In questo esempio n = 4, r₃ = 1 = MCD(90, 17).

Per la (4) ogni resto è combinazione lineare, con coefficienti interi, dei due resti precedenti.
Quindi, risalendo all'indietro a partire da d = r_n-1, si otterrà d = MCD(a, b) come combinazione lineare, con coefficienti interi, dei numeri a, b. Pertanto esistono sempre due interi u, v tali che vale

(5) d = ua + vb

La (5) viene detta identità di Bezout.

Esiste una semplice estensione dell'algoritmo di Euclide, estensione che chiamiamo AEE, che permette di calcolare i coefficienti u, v parallelamente al calcolo di MCD(a, b).

E' sufficiente aggiungere due colonne alla Tavola 1, nelle quali si pongono u_k e v_k ad ogni passo k, mantenedo sempre vera la condizione

(6) r_k = u_ka + v_kb

Allora quando k = n-1 si ottiene la (5).

Come creare e mantenere le relazioni (6) per k che varia da -1 a n-1?

La fase di inzializzazione è ovvia, basta porre

u_-1 = 1, v_-1 = 0
u₀ = 0, v₀ = 1

In questo modo si ha

a = r_-1 = u_-1a + v_-1b
b = r₀ = u₀a + v₀b

A questo punto le (4) stesse ci dicono come calcolare le coppie (u_k, v_k), per k ≥ 1

(7) (u_k, v_k) = (u_k-2, v_k-2) - q_k-1(u_k-1, v_k-1)

Nella sottostante Tavola 2 vediamo AEE all'opera, per esprimere 1 nella forma u × 90 + v × 17

PASSO k	RESTO r_k	QUOZIENTE q_k	u_k	v_k
-1	90	***	1	0
0	17	5	0	1
1	5	3	1	-5
2	2	2	-3	16
3	1	2	7	-37
4	0	***	-17	90

Tavola 2

Per capire bene come si utilizzano le (7) vediamo un esempio

Esempio 2
Calcoliamo (u₃, v₃) nella Tavola 2, utilizzando le (7).
(u₃, v₃) = (u₁, v₁) - q₂ (u₂, v₂) =
(1, -5) - 2 × (-3, 16) = (1, -5) + (6, -32) = (7, -37)

Nella Tavola 2 il risultato è contenuto nella penultima riga: 7 × 90 - 37 × 17 = 1.

Siamo ora in grado di risolvere, come promesso, le equazioni diofantine di tipo più semplice, quelle della forma

(°) ax + by = c

Disponiamo infatti, attraverso AEE, di un potente algoritmo per trovare le soluzioni della (°).

ALGORITMO
Vogliamo risolvere la (°), dove a, b, c sono interi positivi qualsiasi.
Calcoliamo con AEE gli interi d, u, v dove d = MCD(a, b) e vale la
(°°)    ua + vb = d.
Se la (°) ha soluzioni intere, ogni numero che divide sia a che b divide c. Pertanto
se d non divide c non ci sono soluzioni.
Supponiamo allora che d divida c, c = hd.
Moltiplicando la (°°) per h troviamo (hu)a + (hv)b = hd = c.
Pertanto la coppia (x₀, y₀) è una soluzione di (°), dove si è posto x₀ = hu, y₀ = hv.
Sia (x, y) una qualsiasi soluzione di (°). Allora si ha
ax + by = c = ax₀ + by₀, ovvero
(°°°)    a(x - x₀) = b(y₀ - y).
Dividiamo a, b per il loro MCD d. Troviamo a₁ = a/d, b₁ = b/d. Ovviamente a₁ e b₁ sono coprimi tra di loro.
Dividendo la (°°°) per d otteniamo:
(°°°°)    a₁(x - x₀) = b₁(y₀ - y).
La (°°°°) ci dice che a₁ divide il prodotto a destra. Poiché a₁ è coprimo con b₁, a₁ deve dividere (y₀ - y). Per lo stesso motivo b₁ deve dividere (x - x₀).
Esistono allora k, k' tali che y = y₀ - ka₁, x = x₀ + k'b₁.
Ricordiamo ora che la coppia (x, y) è soluzione della (°):
(*)    c = ax + by = a(x₀ + k'b₁) + b(y₀ - ka₁) = c + ak'b₁ - bka₁
perché ax₀ + by₀ = c.
Poiché a₁ = a/d, b₁ = b/d, la (*) diventa:
c = c + k'ab/d - kab/d, il ché implica k = k'.
Concludendo, se ha soluzioni, la (°) ha infinite soluzioni. Le soluzioni sono date dalle coppie (x, y) :

x = x₀ + kb/d,    y = y₀ - ka/d dove k è un intero qualsiasi.
Si noti bene che la coppia iniziale (x₀, y₀) non ha nulla di speciale. Qualsiasi soluzione (x, y) può essere messa al posto di (x₀, y₀).

Per capire bene un algoritmo c'è un solo modo: applicarlo più volte.

Esempio 3
(1) 10625x + 39457y = 44
Calcoliamo MCD(10625, 39457) = 17. Poiché 17 non divide 44, l'equazione (1) non ha soluzioni.
(2)10625x + 39457y = 34
Usiamo AEE ottenendo    MCD(10625, 39457) = 17 = -765 × 10625 + 206 × 39457.
Utilizzando le notazioni dell Algoritmo si ha: h = 2, a₁ = 625, b₁ = 2321, x₀ = -1530, y₀ = 412.
Le soluzioni sono tutte e sole le coppie (x_k, y_k) con    x_k = -1530 + 2321k    y_k = 412 - 625k.
Per esempio una soluzione è (x₁, y₁) = (791, -213)
(3) 1024x - 15625y = 11529
Risolviamo prima la
(#)    1024x + 15625y = 11529.
Usiamo AEE ottenendo    MCD(1024, 15625) = 1 = -4776 × 1024 + 313 × 15625.
Poiché d = 1 divide 11529 la (#) ha infinite soluzioni. In questo caso a₁ = a = 1024 e b₁ = b = 15625.
h = 11529,    x₀ = hu = 11529 × (-4776)    y₀ = hv = 11529 × 313.
Pertanto una soluzione della (#) è (x₀, y₀) = (-55062504, 3608577).
Sappiamo allora che le soluzioni della (#) sono le coppie (x_k, y_k), con x_k = -55062504 + 15625k    y_k = 3608577 - 1024k.
Chiaramente (x, y) è una soluzione della (3) se e solo se (x, -y) è una soluzione della (#). Quindi
le soluzioni della (3) sono le coppie (X_k, Y_k), con X_k = -55062504 + 15625k    Y_k = -3608577 + 1024k.
Supponiamo ora di dover trovare il minimo X positivo per cui (X, Y) è una soluzione della (3).
Poiché la parte intera di 55062504/15625 è 3524, il minimo k per avere X positivo è 3525. Infine si ha:

(X₃₅₂₅, Y₃₅₂₅) = (15621, 1023)

Esercitazione 1.1

Faccio compravendita di giacche di un sol tipo. 
Acquisto una giacca a 27 euro e la rivendo a 40 euro.
All'inizio della giornata ho in cassa 30 euro. Alla fine ne ho 130.
Qual è il minimo numero di giacche che ho venduto?

Marinai e noci di cocco

Tempo fa cinque marinai naufragarono su un'isola. Passarono tutto il giorno a raccogliere noci di cocco, e andarono a dormire. Nella notte uno di loro si alzò e, non fidandosi troppo degli altri, pensò di prendere subito quanto gli spettava. Una scimma curiosa si era avvicinata, e il marinaio le gettò una noce. Le noci rimaste vennero divise in cinque mucchi uguali, senza che avanzasse nulla. Il marinaio prese la sua parte, un quinto giusto, rifece un gran mucchio e tornò a dormire. Gli altri quattro marinai fecero esattamente la stessa cosa, uno dopo l'altro, senza accorgersi di nulla. E ogni volta arrivò la scimmia, cui venne data una noce, proprio come nel primo caso.

Arrivato il mattino i cinque si alzarono e, con incredibile faccia tosta, divisero il mucchio rimasto in cinque parti uguali, ovviamente dopo avere lanciato una noce all'immancabile scimmia.

Domanda: quante erano le noci di cocco?

Una prima risposta

Diciamo x il numero delle noci. Poiché levata una noce il mucchio si divideva esattamente in cinque parti si deve avere

x = 5a₁ + 1

Il primo marinaio prende a₁ noci e rimangono 4a₁ noci. Se denotiamo con a₂, a₃, a₄, a₅, y, rispettivamente, il numero di noci prese dal secondo, terzo, quarto, quinto marinaio e da ogni marinaio il mattino seguente si ha:

x = 5a₁ + 1
4a₁ = 5a₂ + 1
4a₂ = 5a₃ + 1
4a₃ = 5a₄ + 1
4a₄ = 5a₅ + 1
4a₅ = 5y + 1

Sostituendo dal basso verso l'alto si ottiene:

a₅ = (5y + 1)/4
a₄ = (5a₅ + 1)/4 =(5((5y + 1)/4) + 1)/4 = (25y + 9)/16
a₃ = (5a₄ + 1)/4 = (5((25y + 9)/16) + 1)/4 = (125y + 61)/64
a₂ = (5a₃ + 1)/4 = (5((125y + 61)/64) + 1)/4 = (625y + 369)/256
a₁ = (5a₂ + 1)/4 = (5((625y + 369)/256) + 1)/4 = (3125y + 2101)/1024
Infine:
x = 5a₁ + 1 = 5(3125y + 2101)/1024 + 1 = (15625y + 11529)/1024
da cui si ricava l'equazione diofantea
1024x - 15625y = 11529

Abbiamo già visto in Esempio 3 (3) come si risolve questa equazione. La soluzione minima è x = 15621. Si ricordi che x è il numero iniziale delle noci.
In corrispondenza di questa si ha che il numero y delle noci ottenute alla fine da ogni marinaio è 1023.

Generalizziamo

Se vediamo astrattamente l'indovinello dei marinai osserviamo subito che si tratta della iterazione di un processo sempre uguale.
Poiché non complica assolutamente le cose, supponiamo che ogni volta vengano date alle scimmie k noci di cocco (nel nostro indovinello si ha k = 1). Indichiamo con n il numero dei marinai (nel nostro indovinello si ha n = 5). Denotiamo con x(t) il numero delle noci al passo t (nel nostro indovinello ci interessa t = 6). Si noti che x(0) = x è il numero iniziale di noci.

Se, al passo t, ci sono x(t) noci di cocco, k vengono date alla scimmia, le rimanenti x(t) - k sono divise in n parti e una di queste viene accantonata. Si passa pertanto da x(t) noci a x(t+1) noci, dove

(8) x(t+1) = x(t) - k -

x(t)-k

(n - 1)(x(t) - k)

Ci chiediamo ora: quante sono le noci rimaste al passo t?

La risposta è nella formula (9).

(9) rim(x, k, n, t) = k(1 - n) +

æ
è

(n - 1)

ö
ø

(k(n - 1) + x)

La funzione rim riceve, come argomenti, il numero iniziale x delle noci, il numero k delle noci che si danno alla scimmia, il numero n dei marinai e infine il numero del passo t. Restituisce il numero x(t) delle noci rimaste. Effettivamente, se si pone t = 0 e t = 1 si trovano rispettivamente il valore iniziale x e il valore x(1) dato dalla (8).

E' facile ora dimostrare la (9) per induzione.

La Base della Induzione consiste nella osservazione che x(1) = rim(x(0), k, n, 1). Vogliamo provare che per ogni t ³ 1 si ha

(10) x(t) = rim(x(0), k, n, t)

Supponiamo allora vera la (10) per un t dato (questa è la Ipotesi Induttiva), e proviamo che vale per t+1. Dalle (8), (9) e (10) si ottiene che

(11) x(t+1) =

(n - 1)(x(t) - k)

(n - 1)

æ
è

k(1 - n) +

æ
è

(n - 1)

ö
ø

(k(n - 1) + x) - k

ö
ø

Per dimostrare che in effetti rim(x, k, n, t+1) = x(t+1) rimane solo da verificare la seguente uguaglianza:

(12)

(n - 1)

æ
è

k(1 - n) +

æ
è

(n - 1)

ö
ø

(k(n - 1) + x) - k

ö
ø

= k(1 - n) +

æ
è

(n - 1)

ö
ø

t+1

(k(n - 1) + x)

Esercitazione 1.2

Verificare la (12).

Dalla (9) si ricava immediatamente che rim(x, k, n, t) è intero se e solo se n^t | (k(n - 1) + x) , dove con a | b si intende affermare che a è un divisore di b.

Pertanto la soluzione più piccola sarà

(13) x = n^t - k(n - 1)

Nel caso dell'indovinello dei marinai la (13) dà x = 5⁶ - 4 = 15621 in accordo con quanto trovato sopra.

In corrispondenza dei dati dell'indovinello x = 15621, k = 1, n = 5, t = 6 si ha rim(15621, 1, 5, 6) = 4092.

Naturalmente questo non coincide con il valore di y trovato nell' Esempio 3 (3).
Infatti la rimanenza è sempre composta da n - 1 parti. Nel nostro caso da 4 parti. Quindi la quota individuale sarà y = 4092/4 = 1023.

E' molto interessante osservare che la funzione rim per t negativi fa semplicemente tornare indietro il processo di t passi. Per esempio

rim(4092, 1, 5, -2) = rim(15621, 1, 5, 4) = 6396.

Questo ci porta a definire una nuova funzione che chiamiamo mir

(14) mir(z, k, n, t) = rim(z, k, n, -t) = k(1 - n) +

æ
è

(n - 1)

ö
ø

(k(n - 1) + z)

Si ha sempre

(15) mir(rim(x, k, n, t), k, n, s) = rim(x, k, n, t-s)

Fissati k, n, t, se mir e rim si vedono come funzioni della sola x esse sono funzioni inverse, cioè per ogni x

(16) mir(rim(x, k, n, t), k, n, t) = rim(mir(x, k, n, t), k, n, t) = x

Supponiamo che il nostro processo, partendo da x, dia numeri interi per t passi, e poniamo z = rim(x, k, n, t).

Da quanto detto segue che x = mir(z, k, n, t). Pertanto, dalla (14), il numero

æ
è

(n - 1)

ö
ø

(k(n - 1) + z)

deve essere intero. Questo è possibile se e solo se (n-1)^t | (k(n - 1) + z).

Pertanto la soluzione più piccola sarà

(17) z = (n - 1)^t - k(n - 1)

Se riscriviamo la (9) tenendo presente che z = rim(x, k, n, t), otteniamo

z = k(1 - n) +

æ
è

(n - 1)

ö
ø

(k(n - 1) + x)

Questa espressione, mediante ovvie trasformazioni, diventa

(18) (n - 1)^tx - n^tz = k(n-1)(n^t - (n - 1)^t)

Questa è l'equazione diofantea che connette tutti i dati del processo.

Poichè (n-1) ed n sono coprimi, sappiamo che la (18) ha sempre soluzioni. Non solo, ma le abbiamo già trovate! Le soluzioni minime sono date dalle (13) e (17). Infatti sostituendo le (13) e (17) nella (18), si ottiene la identità

(19) (n - 1)^tx - n^tz = (n - 1)^t(n^t - k(n - 1)) - n^t((n - 1)^t - k(n - 1)) = k(n-1)(n^t - (n - 1)^t)

Questo completa lo studio del problema generalizzato.

Esercitazione 1.3

1.3.1 Risolvere il problema della pesca utilizzando i metodi che abbiamo visto. 
      (Come ricorderete il problema della pesca è stato posto dal Professor Beppe Di Domenico)

1.3.2 Determinare un x e un k tali che quando si svegliano (t = 6) i nostri 5 marinai 
      non trovano nessuna noce.

1.3.3 Qual è il significato di rim(x, k, n, t) per k negativo?

1.3.4 Ammettiamo valori negativi di k. 
      Esistono x, k, n tali che rim(x, k, n, t) rimane costante per ogni t?

1.3.5 Determinare x, k positivi tali che rim(x, k, 4, 7) = 3.

Nota

Il problema della "Scimmia e le noci di cocco" ha una interessante storia, e possiede soluzioni e varianti sorprendenti.

Si veda il Capitolo 9 (pagg. 82 - 87) di:

Martin Gardner
Enigmi e giochi matematici 2
Sansoni, 1973

Divertiamoci con la Matematica

- Diofanto, Euclide e le noci di cocco -

Introduzione

L'algoritmo di Euclide e la sua estensione

Marinai e noci di cocco

Una prima risposta

Generalizziamo

Inviate le vostre risposte e soluzioni a umberto.cerruti@unito.it