Syllabus di teoria dei numeri

Ercole Suppa e Rosanna Tupitti

2 aprile 2012

Sommario

In questa lezione vengono ricordate le definizioni e i principali teoremi di teoria dei numeriche sono spesso utilizzati nella risoluzione di problemi olimpici.

1 Divisibilita, MCD e MCM.

• Algoritmo della divisione euclidea. Dati a, b ∈ Z con b 6= 0 esistono due unici numeriq, r ∈ Z tali che:

a = bq + r, 0 ≤ r < |b|

I numeri a, b, q, r sono chiamati rispettivamente dividendo,divisore, quoziente, resto.

• Divisibilita. Nel caso in cui r = 0, ossia se a = bq, diciamo che b divide a e scriviamo b | a .

• Numeri primi. Un numero primo e un intero maggiore di 1 che ha come divisori positivisoltanto 1 e se stesso. Si dimostra che: esistono infiniti numeri primi (teorema di Euclide).

• Teorema fondamentale dell’aritmetica. Ogni intero n > 1 si puo scrivere nella forma:

n = pα11 · pα2

2 · · · pαkk

dove p1, p2, . . . , pk sono primi distinti e α1, α2, . . . , αk sono interi maggiori o uguali a uno. Talescrittura e detta fattorizzazione di n in fattori primi ed e unica a meno dell’ordine dei fattori.

• Massimo comun divisore. Si dice massimo comun divisore di n numeri interi positivia1, a2, · · · , an il piu grande intero positivo che divide tutti gli ai. Il massimo comun divisoredi a1, a2, · · · , an si indica con MCD (a1, a2, . . . , an). Il massimo comun divisore di due interia e b si indica con la notazione abbreviata (a, b). Due interi a e b si dicono primi fra loro ocoprimi se (a, b) = 1.

• Fattorizzazione del MCD. La fattorizzazione del MCD contiene tutti e soli i fattori primiche compaiono in tutte le singole fattorizzazioni, ciascuno elevato al minimo esponente.

• Minimo comune multiplo. Si dice minimo comune multiplo di n numeri interi positivia1, a2, · · · , an il piu piccolo intero positivo che e divisibile per tutti gli ai. Il minimo comunemultiplo di a1, a2, · · · , an si indica con MCM (a1, a2, . . . , an). Il minimo comune multiplo didue interi a e b si indica con la notazione abbreviata [a, b].

1

• Fattorizzazione del MCM. La fattorizzazione del MCM contiene tutti e soli i fattori pri-mi che compaiono in almeno una delle singole fattorizzazioni, ciascuno elevato al massimoesponente.

• Relazione tra MCD e MCM. Per ogni a, b ∈ Z si ha (a, b)[a, b] = ab.

• Algoritmo euclideo per il calcolo del MCD. Dati due interi a, b si dimostra facilmenteche se a = bq + r con 0 ≤ r < |b| allora MCD(a, b) = MCD(b, r). Pertanto il MCD di a e bpuo essere determinato con il seguente algoritmo ricorsivo:

(1) Se uno dei due numeri e uguale a 0, l’altro numero e il MCD di (a, b).

(2) Altrimenti eseguire la divisione euclidea e scrivere a = bq + r, con 0 ≤ r < |b|(3) Rimpiazzare la coppia (a, b) con la coppia (b, r).

(4) Tornare al punto (1)

Ad ogni passo il secondo elemento della coppia diventa piu piccolo, per cui il procedimentoterminera dopo un numero finito di passi, fornendo il MCD di a e b. Come esempio applichiamol’algoritmo euclideo per calcolare MCD(348, 124):

a b q r348 124 2 100124 100 1 24100 24 4 424 4 6 0

Pertanto (348, 124) = (124, 100) = (100, 24) = (24, 4) = (4, 0) e quindi MCD(348, 124) = 4.

• Teorema di Bezout1. Se a, b ∈ Z e d = (a, b), esistono m,n ∈ Z tali che:

d = ma+ nb

• Teorema di Bezout generalizzato. Se a1, a2, · · · , an ∈ Z e d = MCD (a1, a2, . . . , an),esistono m1,m2, . . . ,mk ∈ Z tali che:

d = m1a1 +m2a2 + · · ·+mkak

• Lemma di Euclide2. Se p e primo e p | bc allora p | b oppure p | c.

• Numero dei divisori. Il numero dei divisori del numero naturale n = pα11 · pα2

2 · · · pαkk e dato

dalla formula:d (n) = (α1 + 1) · (α2 + 1) · · · (αk + 1)

1Etienne Bezout matematico francese (1730-1783)2Euclid of Alexandria, fu un matematico Greco, spesso considerato come il Padre della Geometria. La sua

opera gli Elementi di Euclide e stato uno dei testi che ha maggiormente influenzato la storia della matematica.

2

2 Frobenius coin problem.

Il problema delle monete, noto come Frobenius coin problem3 e il problema matematico in cuisi chiede qual e la piu grande somma che non puo essere ottenuta usando solo monete aventi deter-minati tagli. Per esempio la piu grande somma che non puo essere ottenuta usando solo monete di3 e 5 unita e 7 unita. La soluzione di questo problema per un dato insieme T di tagli di monete echiamato numero di Frobenius di T .

Esiste una formula esplicita per il numero di Frobenius quando si hanno solo uno oppure due taglidi monete. Se il numero di tagli di monete e superiore a due non si conosce nessuna formula esplicita.

In termini matematici il problema puo essere formulato nel modo seguente:

Dati n interi positivi a1, a2, . . . , an tali che MCD (a1, a2, . . . , an) = 1 trovare il piu grande numerointero che non puo essere espresso come combinazione lineare a coefficienti interi non negativi dia1, a2, . . . , an, ossia nella forma

k1a1 + k2a2 + · · ·+ knan (*)

dove k1, k2, . . . , kn sono interi non negativi.

Sussistono i seguenti risultati:

• se n = 1 allora a1 = 1 per cui tutti i numeri naturali possono essere espressi nella forma (*),dunque il numero di Frobenius non esiste se n = 1;

• se n = 2 il numero di Frobenius e dato dalla formula

a1a2 − a1 − a2

Questa formula fu scoperta da Sylvester4 nel 1884. Sylvester dimostro inoltre che, in questocaso, il numero degli interi non rappresentabili nella forma k1a1 + k2a2 e dato da:

(a1 − 1) (a2 − 1)

2

Per esempio se a1 = 3 e a2 = 5 allora ogni numero positivo N puo essere espresso nella forma

N = 3k1 + 5k2

tranne i numeri 1,2,4 e 7.

• il problema di Frobenius con n = 3 e irrisolto.

Per un approccio algoritmico si puo consultare [8].

3Ferdinand Frobenius, matematico tedesco (1849-1917).4James Joseph Sylvester, matematico inglese (1814-1897)

3

3 Aritmetica modulare.

• Relazione di conguenza. Sia m > 1 un numero intero fissato. Due numeri a, b ∈ Z sidicono congrui modulo m e si scrive:

a ≡ b (mod m)

se m | a− b. Si dimostra facilmente che a ≡ b (mod m) se e solo se a e b divisi per m dannolo stesso resto.

• Classe di congruenza. Si dice classe di congruenza (modulo m) di un intero a l’insieme ditutti gli interi congrui ad a modulo m:

[a]m = [a] = {b ∈ Z | b ≡ a (mod m)}

Ogni classe di congruenza contiene un unico x tale che 0 ≤ x < m (x e detto rappresentantecanonico).

• Sistema completo di resti. Un insieme di m numeri interi x1, x2, . . . , xm e detto un sistemacompleto di resti modulo m se per ogni a ∈ Z esiste uno ed un solo xi tale che a ≡ xi (mod m).

• Proprieta delle congruenze. La relazione di congruenza gode delle proprieta riflessiva,simmetrica, transitiva ed e compatibile con le operazioni di somma e prodotto, ossia se

a ≡ b (mod m), c ≡ d (mod m)

allora:

(1) a+ c ≡ b+ d (mod m)

(2) a− c ≡ b− d (mod m)

(3) ac ≡ bd (mod m)

(4) ak ≡ bk (mod m), ∀k ∈ N

Dalle precedenti proprieta discende che

(5) Se f(x) e un polinomio a coefficienti interi allora

a ≡ b (mod m) ⇒ f(a) ≡ f(b) (mod m)

Non vale pero, in generale, la legge di cancellazione ossia

ka ≡ kb (mod m) 6⇒ a ≡ b (mod m)

La legge di cancellazione vale solo se (k,m) = 1 ossia:

(6) Se (k,m) = 1 e ka ≡ kb (mod m) ⇒ a ≡ b (mod m).

• Inverso modulo m. Si dice che b e l’inverso di a modulo m se ab ≡ 1 (mod m). In tal casosi dice che a e invertibile modulo m.

• Criterio di invertibilita. Un intero a e invertibile modulo m se e solo se (a,m) = 1.

4

• Calcolo dell’inverso modulo m. Se (a,m) = 1 per il teorema di Bezout esistono h, k ∈ Ztali che:

ha+ km = 1 ⇔ ah ≡ 1 (mod m)

ossia h e l’inverso di a modulo m.

• Teorema di Wilson5. Se p e un numero primo si ha:

(p− 1)! ≡ −1 (mod p)

• Piccolo teorema di Fermat6. Se a ∈ Z e p e un primo tale che p - a si ha:

ap−1 ≡ 1 (mod p)

• Corollario del piccolo teorema di Fermat. Se a ∈ Z e p e un primo si ha:

ap ≡ a (mod p)

• Sistema di congruenze. Se m1, . . . ,mk, a1, . . . , ak ∈ Z, si dice sistema di congruenze unsistema della forma:

x ≡ a1 (mod m1)x ≡ a2 (mod m2)...x ≡ ak (mod mk)

(*)

Risolvere tale sistema significa trovare tutti gli interi x che verificano contemporaneamente lek congruenze del sistema.

• Teorema cinese dei resti. Se m1,m2, . . . ,mk ∈ Z a due a due relativamente primi, alloraqualunque siano gli interi a1, a2, . . . , ak ∈ Z il sistema (*) ammette una soluzione, unicamodulo m1m2 · · ·mk.

• Costruzione della soluzione del sistema (*). Per ogni i ∈ {1, 2, . . . , k} poniamo

bi =∏j 6=i

mj

e indichiamo con ci l’inverso di bi modulo mi. Allora una soluzione del sistema (*) e data da

x0 =k∑i=1

aibici

Tutte le altre soluzioni sono della forma:

x = x0 + t ·m1m2 · · ·mk , t ∈ Z5John Wilson (1741-1793) matematico inglese. Diede l’enunciato del teorema che porta il suo nome senza

dimostrarlo. La prima dimostrazione fu data da Lagrange nel 1771.6Pierre de Fermat (1601-1665), un giurista del parlamento di Tolosa e cultore di matematica che diede grandi

contributi in diversi settori, soprattutto in teoria dei numeri.

5

• Funzione di Eulero7. Si dice funzione ϕ di Eulero la funzione che ad ogni intero n > 1associa il numero degli interi 0 < a < n che sono relativamente primi con n, ossia

ϕ (n) = |{a ∈ |0 < a < n, (a, n) = 1}|

• Proprieta della funzione di Eulero.

(1) ϕ e una funzione moltiplicativa ossia se (a, b) = 1 ⇒ ϕ(ab) = ϕ(a) · ϕ(b)

(2) se p e un numero primo ϕ(p) = p− 1

(3) se p e un numero primo ed α ∈ N: ϕ (pα) = pα − pα−1

(4) se n = pα11 · pα2

2 · · · pαkk allora

ϕ (n) = n

(1− 1

p1

)· · ·(

1− 1

pk

)= n

∏p|n

(1− 1

p

)

• Teorema di Fermat-Eulero. Se a ∈ Z ed (a,m) = 1 allora aϕ(m) ≡ 1 (mod m).

4 Equazioni diofantee.

• Equazione diofantea. Un’equazione a coefficienti interi di cui si devono trovare le soluzioniintere e chiamata equazione diofantea (in onore di Diofanto8).

• Equazione diofantea in due variabili di primo grado. Un’equazione diofantea di primogrado in due variabili e un’equazione della forma

ax+ by = c

dove a, b, c ∈ Z. Risolvere tale equazione significa trovare tutte le coppie (x, y) di numeriinteri che la soddisfano.

• Equazione omogenea. L’equazione diofantea ax+ by = c si dice omogenea se c = 0.

• Soluzioni dell’equazione omogenea e non omogenea. Se (x1, y1), (x2, y2) sono due so-luzioni dell’equazione non omogenea allora (x1 − x2, y1 − y2) e soluzione dell’equazione omo-genea associata ax + by = 0. Pertanto, per trovare tutte le soluzioni dell’equazione nonomogenea, basta trovare una soluzione qualunque dell’equazione non omogenea, piu tutte lesoluzioni dell’omogenea associata.

• Condizione necessaria e sufficiente per l’esistenza di soluzioni. Un’equazione dio-fantea omogenea ammette sempre infinite soluzioni. Un’equazione diofantea non omogeneaammette almeno una soluzione se e solo se (a, b) | c. In tal caso le soluzioni sono infinite.Pertanto un’equazione diofantea di primo grado ammette o zero o infinite soluzioni.

7Leonhard Euler, matematico svizzero (1707-1783)8Diofanto di Alessandria, matematico dell’antica Grecia vissuto nel periodo tra il III e il IV secolo dopo

Cristo, considerato come il Padre dell’algebra.

6

• Come trovare una soluzione dell’equazione non omogenea. Sia d = (a, b) e siano m, ncome nel teorema di Bezout, cioe tali che ma+nb = d. Se e verificata la condizione necessariae sufficiente, cioe se esiste un intero k tale che c = kd allora x0 = km, y0 = kn e una dellesoluzioni dell’equazione non omogenea.

• Come trovare tutte le soluzioni dell’equazione omogenea. Sia d = (a, b) e sianoα, β ∈ Z tali che a = αd, b = βd. Allora le soluzioni dell’equazione omogenea sono tutte esole quelle del tipo x = βt, y = −αt con t ∈ Z.

5 Frazioni continue.

• Frazione continua finita. Si definisce frazione continua finita un’espressione della forma

[a0; a1, a2, . . . , an] := a0 +1

a1 +1

a2 +1

. . .+

1

an

dove a1, a2, . . . , an sono numeri reali positivi ed a0 e un numero reale non negativo. I numeria1, . . . , an sono detti denominatori parziali. La frazione continua e detta semplice se i numeriai sono interi.

• Sviluppo di un numero razionale in frazione continua. Utilizzando l’algoritmo euclideodelle divisioni successive si dimostra facilmente che ogni numero razionale puo essere scrittocome una frazione continua semplice finita. Illustriamo, ad esempio, come la frazione 17

61puo

essere sviluppata in frazione continua:

17

61= 0 +

1

3 +10

17

= 0 +1

3 +1

1 +7

10

= 0 +1

3 +1

1 +1

1 +3

7

= 0 +1

3 +1

1 +1

1 +1

2 +1

3= [0; 3, 1, 1, 2, 3]

• La rappresentazione di un numero razionale come frazione continua semplice finita non e unicain quanto possiamo sempre modificare l’ultimo termine. Infatti se an > 1 allora

an = (an − 1) +1

1⇒ [a0; a1, a2, . . . , an] = [a0; a1, a2, . . . , an − 1, 1]

mentre se an = 1 allora

an−1 +1

an= an−1 + 1 ⇒ [a0; a1, a2, . . . , an] = [a0; a1, a2, . . . , an−2, an−1 + 1]

7

Ad esempio abbiamo che

17

61= [0; 3, 1, 1, 2, 3] = [0; 3, 1, 1, 2, 2, 1]

• Convergenti di una frazione continua. La frazione continua ottenuta da [a0; a1, a2, . . . , an]considerando i denominatori parziali fino ad ak e detta convergente k-esima ed e indicata con

Ck = [a0; a1, a2, . . . , ak] =pkqk

Ad esempio le convergenti della frazione17

61= [0; 3, 1, 1, 2, 3] sono:

C0 = 0

C1 = [0; 3] = 0 +1

3=

1

3

C2 = [0; 3, 1] = 0 +1

3 +1

1

=1

4

C3 = [0; 3, 1, 1] = 0 +1

3 +1

1 +1

1

=2

7

C4 = [0; 3, 1, 1, 2] = 0 +1

3 +1

1 +1

1 +1

2

=5

18

C5 = [0; 3, 1, 1, 2, 3] = 0 +1

3 +1

1 +1

1 +1

2 +1

3

=17

61

• Formula ricorsiva per il calcolo delle convergenti di una frazione continua. Sidimostra facilmente per induzione che le convergenti Ck = pk/qk della una frazione continua[a0; a1, a2, . . . , an] possono essere calcolate con le seguenti formule ricorsive:

p0 = a0 q0 = 1

p1 = a1a0 + 1 q1 = a1

pk = akpk−1 + pk−2 qk = akqk−1 + qk−2, ∀k ≥ 2

8

• Proprieta fondamentale delle convergenti di una frazione continua. Se Ck = pk/qke la k-esima convergente della frazione continua [a0; a1, a2, . . . , an] allora:

pkqk−1 − qkpk−1 = (−1)k−1, ∀k ∈ {1, 2, . . . , n}

Da questa proprieta discende che MCD(pk, qk) = 1 per ogni k ∈ {1, 2, . . . , n}.

• Risoluzione di un’equazione diofantea lineare. Le frazioni continue possono essereimpiegate per trovare le soluzioni dell’equazione diofantea

ax+ by = 1

dove a, b sono due interi tali coprimi. Espandiamoa

bin frazione continua

a

b= [a0; a1, . . . , an].

Le ultime due convergenti di questa frazione sono Cn−1 = pn−1/qn−1 e Cn = pn/qn = a/b.Poiche MCD(pn, qn) = 1 = MCD(a, b) abbiamo che pn = a, qn = b. Pertanto dalla proprietafondamentale delle convergenti abbiamo

pnqn−1 − qnpn−1 = (−1)n−1 ⇒ aqn−1 − bpn−1 = (−1)n−1

Allora una soluzione particolare di ax+ by = 1 e:

(i) x0 = qn−1, y0 = −pn−1 se n e dispari

(ii) x0 = −qn−1, y0 = pn−1 se n e pari

La soluzione generale di ax+ by = 1 e:

x = x0 + bt, y = y0 − at t ∈ Z

• Frazione continua infinita. Se a0, a1, a2, . . . e una successione (infinita) di interi positivi(escluso al piu a0 che puo anche essere uguale a 0) allora l’espressione:

[a0; a1, a2, a3, . . . ] := a0 +1

a1 +1

a2 +1

a3 +1

. . .

e chiamata frazione continua semplice infinita. Per attribuire un significato numerico a taleespressione poniamo:

[a0; a1, a2, a3, . . . ] := limk→∞

[a0; a1, a2, . . . , ak]

Se una frazione continua infinita, come ad esempio [3; 1, 2, 1, 6, 1, 2, 1, 6, . . . ] contiene un bloccodi denominatori parziali b1, b2, . . . , bn che si ripetono, la frazione e detta periodica. Una frazionecontinua periodica [a0; a1, . . . , am, b1, . . . , bn, b1, . . . , bn, . . . ] viene indicata con la notazione:

[a0; a1, . . . , am, b1, . . . , bn]

dove la barra indica che i termini b1, . . . , bn si ripetono infinite volte. Se b1, . . . , bn e il piupiccolo blocco di interi che si ripetono, diciamo che b1, . . . , bn e il periodo della frazione continuaed n e detta la lunghezza del periodo. Si possono dimostrare le seguenti proprieta:

9

(i) Il valore di una frazione continua infinita e un numero irrazionale.

(ii) Due frazioni continue infinite [a0, a1, a2, . . . ] e [b0, b1, b2, . . . ] rappresentano lo stesso nu-mero se e solo se ai = bi per ogni i ≥ 0.

(iii) La frazione continua sviluppo di un irrazionale quadratico x =√K e periodica da un

certo punto in poi (teorema dimostrato da Lagrange9 nel 1770).

(iv) Se d e un intero positivo che non e un quadrato perfetto, allora lo sviluppo in frazionecontinua di

√d e della forma

√d = [a0; a1, a2, a3, . . . , a3, a2, a1, 2a0]

(v) Siano Ck = pk/qk le convergenti della frazione continua sviluppo di√d e sia n il suo

periodo. Allorap2kn−1 − dq2kn−1 = (−1)kn, k ∈ {1, 2, 3, . . . }

• Sviluppo di un numero reale in frazione continua. Se x e un numero reale positivo,poniamo

x0 := x, a0 := [x0]

da cui segue che 0 ≤ x0 − a0 < 1. Se x0 − a0 > 0 poniamo

x1 :=1

x0 − a0, a1 := [x1]

ed in generale per n ≥ 1, se xn − an > 0, poniamo

xn+1 :=1

xn − an, an+1 := [xn+1]

La sequenza (xn) termina dopo un numero finito di passi se x e un numero razionale, in casocontrario e una sequenza infinita. Se x e un numero irrazionale otteniamo due successioni:(an) di numeri interi positivi ed (xn) di numeri irrazionali maggiori di 1 e si puo dimostrareche

x = [a0; a1, a2, . . . ]

• Determinare lo sviluppo in frazione continua di√

11:

x0 =√

11 a0 = 3

x1 =1

x0 − [x0]=

1√11− 3

=

√11 + 3

2≈ 3, 15 a1 = 3

x2 =1

x1 − [x1]=

1√11+32− 3

=√

11 + 3 ≈ 6, 31 a2 = 6

x3 =1

x2 − [x2]=

1√11 + 3− 6

=1√

11− 3≈ 3, 15 a2 = 3

Pertanto√

11 = [3; 3, 6].

9Joseph Louis Lagrange (1736-1813) fu, dopo Eulero, il piu grande matematico del XVIII secolo.

10

• Sviluppo in frazione continua di√N per N ∈ {1, . . . , 99}, N non quadrato.

√2 = [1; 2]

√3 = [1; 1, 2]

√5 = [2; 4]

√6 = [2; 2, 4]

√7 = [2; 1, 1, 1, 4]

√8 = [2; 1, 4]

√10 = [3; 6]

√11 = [3; 3, 6]

√12 = [3; 2, 6]

√13 = [3; 1, 1, 1, 1, 6]

√14 = [3; 1, 2, 1, 6]

√15 = [3; 1, 6]

√17 = [4; 8]

√18 = [4; 4, 8]

√19 = [4; 2, 1, 3, 1, 2, 8]

√20 = [4; 2, 8]

√21 = [4; 1, 1, 2, 1, 1, 8]

√22 = [4; 1, 2, 4, 2, 1, 8]

√23 = [4; 1, 3, 1, 8]

√24 = [4; 1, 8]

√26 = [5; 10]

√27 = [5; 5, 10]

√28 = [5; 3, 2, 3, 10]

√29 = [5; 2, 1, 1, 2, 10]

√30 = [5; 2, 10]

√31 = [5; 1, 1, 3, 5, 3, 1, 1, 10]

√32 = [5; 1, 1, 1, 10]

√33 = [5; 1, 2, 1, 10]

√34 = [5; 1, 4, 1, 10]

√35 = [5; 1, 10]

√37 = [6; 12]

√38 = [6; 6, 12]

√39 = [6; 4, 12]

√40 = [6; 3, 12]

√41 = [6; 2, 2, 12]

√42 = [6; 2, 12]

√43 = [6; 1, 1, 3, 1, 5, 1, 3, 1, 1, 12]

√44 = [6; 1, 1, 1, 2, 1, 1, 1, 12]

√45 = [6; 1, 2, 2, 2, 1, 12]

√46 = [6; 1, 3, 1, 1, 2, 6, 2, 1, 1, 3, 1, 12]

√47 = [6; 1, 5, 1, 12]

√48 = [6; 1, 12]

√50 = [7; 14]

√51 = [7; 7, 14]

√52 = [7; 4, 1, 2, 1, 4, 14]

√53 = [7; 3, 1, 1, 3, 14]

√54 = [7; 2, 1, 6, 1, 2, 14]

√55 = [7; 2, 2, 2, 14]

√56 = [7; 2, 14]

√57 = [7; 1, 1, 4, 1, 1, 14]

√58 = [7; 1, 1, 1, 1, 1, 1, 14]

√59 = [7; 1, 2, 7, 2, 1, 14]

√60 = [7; 1, 2, 1, 14]

√61 = [7; 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14]

√62 = [7; 1, 6, 1, 14]

√63 = [7; 1, 14]

√65 = [8; 16]

√66 = [8; 8, 16]

√67 = [8; 5, 2, 1, 1, 7, 1, 1, 2, 5, 16]

√68 = [8; 4, 16]

√69 = [8; 3, 3, 1, 4, 1, 3, 3, 16]

√70 = [8; 2, 1, 2, 1, 2, 16]

11

√71 = [8; 2, 2, 1, 7, 1, 2, 2, 16]

√72 = [8; 2, 16]

√73 = [8; 1, 1, 5, 5, 1, 1, 16]

√74 = [8; 1, 1, 1, 1, 16]

√75 = [8; 1, 1, 1, 16]

√76 = [8; 1, 2, 1, 1, 5, 4, 5, 1, 1, 2, 1, 16]

√77 = [8; 1, 3, 2, 3, 1, 16]

√78 = [8; 1, 4, 1, 16]

√79 = [8; 1, 7, 1, 16]

√80 = [8; 1, 16]

√82 = [9; 18]

√83 = [9; 9, 18]

√84 = [9; 6, 18]

√85 = [9; 4, 1, 1, 4, 18]

√86 = [9; 3, 1, 1, 1, 8, 1, 1, 1, 3, 18]

√87 = [9; 3, 18]

√88 = [9; 2, 1, 1, 1, 2, 18]

√89 = [9; 2, 3, 3, 2, 18]

√90 = [9; 2, 18]

√91 = [9; 1, 1, 5, 1, 5, 1, 1, 18]

√92 = [9; 1, 1, 2, 4, 2, 1, 1, 18]

√93 = [9; 1, 1, 1, 4, 6, 4, 1, 1, 1, 18]

√94 = [9; 1, 2, 3, 1, 1, 5, 1, 8, 1, 5, 1, 1, 3, 2, 1, 18]

√95 = [9; 1, 2, 1, 18]

√96 = [9; 1, 3, 1, 18]

√97 = [9; 1, 5, 1, 1, 1, 1, 1, 1, 5, 1, 18]

√98 = [9; 1, 8, 1, 18]

√99 = [9; 1, 18]

6 Equazioni diofantee di secondo grado.

6.1 Equazione pitagorica

• L’equazione diofantea x2 +y2 = z2 e chiamata equazione pitagorica in quanto se consideriamoun triangolo rettangolo i cui cateti e la cui ipotenusa hanno lunghezze x, y, z espresse danumeri interi allora, per il teorema di Pitagora, (x, y, z) e una soluzione.

• Una soluzione (x, y, z) dell’equazione x2 + y2 = z2 e detta primitiva se MCD(x, y, z) = 1.

• Ricerca delle soluzioni (positive) primitive. Le soluzioni (positive) primitive dell’equa-zione x2 + y2 = z2 con y pari sono

x = r2 − s2, y = 2rs, z = r2 + s2

dove r, s sono interi arbitrari di parita opposta tali che r > s > 0 ed (r, s) = 1.

• Ricerca delle soluzioni positive. Le soluzioni positive dell’equazione x2 + y2 = z2 con ypari sono

x = k(r2 − s2

), y = 2krs, z = k

(r2 + s2

)dove r, s sono interi arbitrari, di parita opposta, tali che r > s > 0 e k e un intero qualsiasi.

12

6.2 Equazione di Pell

• Se d e un intero l’equazione diofantea

x2 − dy2 = 1

e detta equazione di Pell. Se d e un quadrato perfetto, diciamo d = a2, l’equazione puo esserescritta nella forma (x − ay)(x + ay) = 1 e, pertanto, ammette un numero finito di soluzioni.Anche se d < 0 l’equazione ha un numero finito di soluzioni. Il caso piu interessante si haquando d e un numero intero positivo che non e un quadrato perfetto.

• Una soluzione (x, y) e detta positiva se entrambi x ed y sono numeri interi positivi. Unasoluzione (x1, y1) e detta soluzione fondamentale (o soluzione minima) se e la piu piccolasoluzione positiva, cioe se per ogni altra soluzione positiva (x′, y′) risulta che x1 < x′ edy1 < y′. Nella trattazione che segue ci limitiamo alla determinazione delle soluzioni positivein quanto, a parte le soluzioni banali (±1, 0), tutte le altre sono della forma (±x,±y), dovex > 0 ed y > 0.

• Ricerca delle soluzioni positive. Sebbene John Pell10 abbia contribuito molto poco allostudio di questa equazione, essa porta il suo nome a causa di un errore di Eulero. I matematiciche per primi si occuparono di questa equazione furono Brahmagupta (VII secolo), Bhaskara(XII secolo) e Fermat (XVII secolo) che ne fece uno studio sistematico. Il metodo di risoluzionedell’equazione di Pell, basato sulla teoria delle frazioni continue, e dovuto a Lagrange (XVIIIsecolo). Esponiamo il procedimento risolutivo, omettendo le dimostrazioni11:

(i) Troviamo lo sviluppo in frazione continua di√d

√d = [a0; a1, a2, a3, . . . , a3, a2, a1, 2a0]

e determiniamo le sue convergenti Ck = pk/qk con k ∈ {0, 1, . . . , n− 1} se n e pari ek ∈ {0, 1, . . . , 2n− 1} se n e dispari.

(ii) Se n e pari allora la soluzione fondamentale e data da x1 = pn−1, y1 = qn−1, mentre se ne dispari la soluzione fondamentale e data da x1 = p2n−1, y1 = q2n−1.

(iii) ogni soluzione positiva di x2 − dy2 = 1 e data da (xn, yn), dove xn, yn sono interideterminati dall’uguaglianza

xn + yn√d =

(x1 + y1

√d)n, ∀n ≥ 2

Equivalentemente, dopo aver trovato la soluzione fondamentale (x1, y1), possiamo calco-lare tutte le altre soluzioni mediante le formule ricorsive

xn+1 = x1xn + dy1yn

yn+1 = x1yn + y1xn

10John Pell (1611-1685) grande insegnante e grande studioso ammesso al Trinity College di Cambridge all’etadi 13 anni. Fu professore di matematica ad Amsterdam e a Breda e fu eletto membro della Royal Society nel 1663.

11Al lettore interessato sull’argomento si consiglia [?]

13

• Soluzione fondamentale di x2 − dy2 = 1 per d ∈ {1, . . . , 103}.

d x1 y1 d x1 y1 d x1 y12 3 2 38 37 6 71 3480 4133 2 1 39 25 4 72 17 25 9 4 40 19 3 73 2281249 2670006 5 2 41 2049 320 74 3699 4307 8 3 42 13 2 75 26 38 3 1 43 3482 531 76 57799 663010 19 6 44 199 30 77 351 4011 10 3 45 161 24 78 53 612 7 2 46 24335 3588 79 80 913 649 180 47 48 7 80 9 114 15 4 48 7 1 82 163 1815 4 1 50 99 14 83 82 917 33 8 51 50 7 84 55 618 17 4 52 649 90 85 285769 3099619 170 39 53 66249 9100 86 10405 112220 9 2 54 485 66 87 28 321 55 12 55 89 12 88 197 2122 197 42 56 15 2 89 500001 5300023 24 5 57 151 20 90 19 224 5 1 58 19603 2574 91 1574 16526 51 10 59 530 69 92 1151 12027 26 5 60 31 4 93 12151 126028 127 24 61 1766319049 226153980 94 2143295 22106429 9801 1820 62 63 8 95 39 430 11 2 63 8 1 96 49 531 1520 273 65 129 16 97 62809633 637735232 17 3 66 65 8 98 99 1033 23 4 67 48842 5967 99 10 134 35 6 68 33 4 101 201 2035 6 1 69 7775 936 102 101 1037 73 12 70 251 30 103 227528 22419

• Soluzione fondamentale di x2 − dy2 = −1 per d ∈ {1, . . . , 103}.

d x1 y1 d x1 y1 d x1 y12 1 1 37 6 1 73 1068 1255 2 1 41 32 5 74 43 510 3 1 50 7 1 82 9 113 18 5 53 182 25 85 378 4117 4 1 58 99 13 89 500 5326 5 1 61 29718 3805 97 5604 56929 70 13 65 8 1 101 10 1

14

• Esempio 1. Trovare le soluzioni intere positive dell’equazione x2 − 7y2 = 1.

(i) Osserviamo che√

7 = [2; 1, 1, 1, 4] e che il periodo della frazione continua e 4. Le prime5 convergenti di

√13 sono:

2

1,3

1,5

2,8

3,37

14

(ii) Poiche il periodo e pari la soluzione fondamentale e x1 = p3 = 8, y1 = q3 = 3.

(iii) Altre soluzioni sono determinate dall’uguaglianza

xn + yn√

7 =(

8 + 3√

7)n, ∀n ≥ 2

Ad esempio (x2, y2) = (127, 48), (x3, y3) = (2024, 765), etc.

• Esempio 2. Trovare le soluzioni intere positive dell’equazione x2 − 13y2 = 1.

(i) Osserviamo che√

13 = [3; 1, 1, 1, 1, 6] e che il periodo della frazione continua e 5. Leprime 10 convergenti di

√13 sono:

3

1,4

1,7

2,11

3,18

5,119

33,137

38,256

71,393

109,649

180

(ii) Poiche il periodo e dispari la soluzione fondamentale e x1 = p9 = 649, y1 = q9 = 180.

(iii) Altre soluzioni sono determinate dall’uguaglianza

xn + yn√

13 =(

649 + 180√

13)n, ∀n ≥ 2

Ad esempio (x2, y2) = (842401, 233640).

• Ricerca della soluzione fondamentale per tentativi. Talvolta la soluzione fondamentaledell’equazione di Pell x2 − dy2 = 1 puo essere trovata manualmente sostituendo di volta involta i valori y = 1, 2, 3, . . . nell’espressione 1 + dy2, finche si ottiene un quadrato.

• Equazione di Pell negativa. L’equazione di Pell negativa e data da

x2 − dy2 = −1

Anche questa equazione e stata studiata estensivamente. Essa puo essere risolta con la stessatecnica delle frazioni continue ed ammette soluzioni quando il periodo della frazione continuache rappresenta

√d ha lunghezza dispari. Tuttavia a tutt’oggi non si conosce un criterio per

stabilire se il periodo di√d ha lunghezza dispari e quindi non siamo in grado di stabilire per

quali valori di d l’equazione x2 − dy2 = −1 risulta risolubile. Ad esempio x2 − 3y2 = −1 nonha soluzioni intere (basta osservare che un quadrato e congruo a 0 oppure ad 1 modulo 3).

15

7 Problemi

1. Dimostare che l’equazione x2 − y2 = 2 non ha soluzioni intere.

2. Dimostrare che 6 divide n(n− 1)(2n− 1) per ogni n ∈ N.

3. Dimostrare che 17 divide 2n · 32n − 1 per ogni n ∈ N.

4. Dimostrare che 17n − 12n − 24n + 19n e divisibile per 35 per ogni n ∈ N.

5. Dimostrare che 599 + 1199 + 1799 e divisibile per 33.

6. Dimostrare che 36n − 26n e divisibile per 35 per ogni n ∈ N0.

7. Dimostrare che n5 − 5n3 + 4n e divisibile per 120 per ogni n ∈ N.

8. Dimostrare che n2 + 3n+ 5 non e divisibile per 121 per ogni n ∈ N.

9. Sia A la somma delle cifre del numero 44444444. Sia B la somma delle cifre di A. Qual e lasomma delle cifre di B ? (IMO 1975).

10. Lungo un corridoio sono disposte 2000 porte contrassegnate con i numeri {1, 2, . . . , 2000}.All’inizio tutte le porte sono chiuse. Una persona cammina lungo il corridoio ed apre tutte leporte con numero pari a partire dalla numero 2, cosı che tutte le porte {2, 4, . . . , 1998, 2000}sono aperte. Un’altra persona cammina lungo il corridoio e cambia lo stato (cioe chiude unaporta se essa e aperta e la apre se e chiusa) delle porte contrassegnate con un multiplo di 3.Quindi un’altra persona cambia lo stato delle porte contrassegnate con un multiplo di 4, ecc.Questo processo continua finche lo stato delle porte non puo essere piu alterato. Dire quantesono le porte chiuse alla fine del processo.

11. Quale resto si ottiene dividendo 61987 per 37 ?

12. Sia N = 22 · 31 + 11 · 17 + 13 · 19. Determinare

(a) la parita di N ;

(b) l’ultima cifra di N ;

(c) il resto quando N viene diviso per 7.

13. Trova l’ultima cifra del numero 19891989.

14. Trova l’ultima cifra del numero 777777.

15. Trova l’ultima cifra del numero 777 .

16. Qual e l’ultima cifra del numero ((((((((((7)7)7)7)7)7)7)7)7)7)7 in cui 7 figura 10 volte comeesponente.

17. Qual e l’ultima cifra del numero 77777

77

.

18. Trova le ultime due cifre di 31234.

19. Trova le ultime tre cifre di 79999.

16

20. Dimostrare che esiste un multiplo di 21 avente 241 come ultime tre cifre.

21. Dimostrare che il numero 222 · · · 22︸ ︷︷ ︸1980 cifre

e divisibile per 1982.

22. Dimostrare che se 2n+ 1 e 3n+ 1 sono quadrati perfetti allora n e divisibile per 40.

23. Dimostrare che la somma di due quadrati dispari non puo essere un quadrato

24. Dimostrare che la successione di numeri 11, 111, 1111, 11111, . . . (scritti in base 10) noncontiene quadrati perfetti.

25. Dimostrare che il numero 111 · · · 111︸ ︷︷ ︸81 cifre

e divisibile per 81.

26. Dimostrare che nella successione 1, 31, 331, 3331, . . . esistono infiniti numeri composti.

27. Dimostrare che 270 + 370 e divisibile per 13.

28. Dimostrare che 3105 + 4105 e divisibile per 7.

29. Dimostrare che 22225555 + 55552222 e divisibile per 7.

30. Dimostrare che 4n + 15n− 1 e divisibile per 9.

31. Dimostrare che 3851989 + 181980 non e un quadrato perfetto.

32. Dimostrare che non esistono numeri interi a, b tali che a2 − 3b2 = 8.

33. Dimostrare che non esistono numeri interi a, b tali che 15a2 − 7b2 = 9.

34. Dimostrare che l’equazione x2 + y2 + z2 = 2xyz non ha soluzioni intere eccetto (0, 0, 0).

35. Dimostrare che la somma dei quadrati di cinque numeri naturali consecutivi non puo essereun quadrato perfetto.

36. Dimostrare che il numero 100 · · · 00500 · · · 001 (100 zeri nei due gruppi) non e un cubo perfetto.

37. Se a+ 1 e divisibile per 3 dimostra che 4 + 7a e divisibile per 3.

38. Trova l’ultima cifra del numero 12 + 22 + · · ·+ 992.

39. Sette numeri naturali sono tali che la somma di ogni sei di essi e divisibile per 5. Dimostrache ognuno di questi numeri e divisibile per 5.

40. Dimostrare che esiste un numero naturale n tale che i numeri n+ 1, n+ 2, · · · , n+ 1999 sonotutti composti.

41. Dimostrare che 399 + 61100 e divisibile per 31.

42. Quale resto si ottiene dividendo il numero 1010 + 10100 + 101000 + · · ·+ 1010000000000 per 7.

43. Dimostra che, se p e un numero primo maggiore di 3, allora p2 − 1 e divisibile per 24.

44. Trova la somma di tutti gli interi x divisibili per 7 tali che 1 ≤ x ≤ 1000.

17

45. La successione di numeri naturali (an) soddisfa le condizioni

(a) a1 = a2 = 1

(b) an+2 = an+1 · an per ogni n ∈ N

Dimostrare che nessun termine della successione e divisibile per 4.

46. Dimostra che nessuno dei numeri an = 100100 · · · 1001 e primo, dove n = 2, 3, 4, . . . indica ilnumero delle occorrenze delle cifra 1 in an.

47. Trovare il piu piccolo intero positivo che diviso per 13 da resto 5 e diviso per 23 da resto 12.

48. Paolo ha una collezione di monete. Se egli dispone le monete in pile da 6 gli restano 3 monete.Se le monete sono disposte in pile da 8 restano 7 monete e se sono disposte in pile da 5 restano4 monete. Se il numero n di monete e minore di 100, trovare n.(Flanders Mathematical Olympiad 1997-98)

49. Sia d un intero positivo diverso da 2,5,13. Prova che esistono due numeri interi distintia, b ∈ {2, 5, 13, d} tali che ab− 1 non e un quadrato perfetto (IMO 1986).

50. Dimostra che un intero positivo n e somma di almeno due interi positivi consecutivi se e solose non e una potenza di due. (Canadian Mathematical Olympiad 1976)

51. Trova tutte le soluzioni intere dell’equazione diofantea 5x+ 3y = 7.

52. Marinai, noci di cocco e scimmie. Cinque marinai sono finiti dopo un naufragio suun’isola. Per procurarsi cibo, essi raccolgono tutte le noci di cocco che riescono a trovare.Durante la notte uno dei marinai si sveglia e decide di prendersi la sua parte di noci. Eglile divide in cinque mucchi uguali e scopre che ne avanza una, ed allora questa la getta allescimmie. Poi nasconde la sua parte e torna a dormire. Dopo un po’ si sveglia un secondomarinaio con la medesima idea. Egli divide quel che e restato delle noci in cinque mucchiuguali, scopre che ne avanza ancora una e la getta alle scimmie. Poi nasconde la sua parte.A loro volta gli altri tre marinai fanno lo stesso, e ciascuno getta una noce alle scimmie. Lamattina dopo i marinai, con l’aria piu innocente del mondo, dividono le noci rimaste in cinquemucchi uguali e questa volta non ne avanza nessuna. Trovare il minimo numero possibile dinoci del mucchio originario. (Hint: Il problema e ricondotto a quello di trovare le soluzioniintere positive dell’ equazione diofantea: 1024x− 15625y = 8404)

53. Trova tutte le soluzioni intere delle seguenti equazioni diofantee:

(a) 3x+ 2y = 1

(b) 91x+ 221y = 15

(c) 401x+ 503y = 20

54. Decomporre il numero 71 nella somma di due addendi positivi, dei quali il primo sia multiplodi 5 e l’altro multiplo di 8.

55. Rappresentare il numero 131 come somma di due addendi non negativi di cui il primo, divisoper 7, dia resto 3 e l’altro, diviso per 11, dia resto 5.

18

56. Decomporre la frazione 128/117 nella somma di due frazioni positive aventi per denominatori9 e 13.

57. Un fattore compra delle mucche a 80000 lire l’una, e dei maiali a 50000 lire l’uno. Paga intutto 810000 lire. Quante mucche e quanti maiali ha comprato ?

58. Dimostra che se l’equazioneax+ by + cz = e

ammette soluzioni intere allora MCD(a, b, c) | e. Viceversa, supposto che MCD(a, b, c) | e,prova che esistono w, z ∈ Z tali che

(a, b)w + cz = e

e poi prova che esistono x, y ∈ Z tali che

ax+ by = (a, b)w

La stessa tecnica puo essere utilizzata per risolvere equazioni diofantee lineari con n incognite.

59. Trova le soluzioni intere dell’equazione

323x+ 391y + 437z = 10473

60. Roberto ha 56 monete in pezzi da 1, 5, 10 centesimi. Dire quante sono le monete di ciascuntaglio sapendo che la somma complessiva e di 97 centesimi.

61. Esprimere ciascuno dei seguenti numeri razionali sotto forma di frazione continua semplicefinita:

(a)185

56(b)

185

56(c)

69

31(d)

118

303

62. Trovare i numeri razionali rappresentati dalle seguenti frazioni continue:

(a) [4; 1, 3, 5, 7] (b) [2; 1, 3, 1, 1, 5] (c) [0; 1, 2, 3, 4, 3, 2, 1] (d) [−1; 1, 4, 16]

63. Determinare le convergenti dalle seguenti frazioni continue:

(a) [1; 4, 3, 3, 4, 1] (b) [2; 1, 1, 1, 1, 5] (c) [0; 3, 5, 1, 10, 3]

64. Mediante le frazioni continue trovare la soluzione generale di ciascuna delle seguenti equazionidiofantee

(a) 11x+ 31y = 1 (b) 2x+ 9y = 1 (c) 158x− 57y = 1 (d) 17x− 12y = 1

65. Calcolare il valore di ognuna delle seguenti frazioni continue infinite:

(a) [3, 4] (b) [2; 1, 3, 1] (c) [1; 3, 2, 1] (d) [0; 1, 2, 3]

66. Esprimere ciascuno dei seguenti numeri irrazionali sotto forma di frazione continua sempliceinfinita:

(a)√

11 (b)1 +√

13

2(c)

5 +√

31

4(d)

7−√

5

4

19

67. Sostituendo successivamente i valori y = 1, 2, 3, . . . nell’espressione dy2 + 1 determinare lasoluzione fondamentale dell’equazione x2 − dy2 = 1 quando d vale

(a) 7 (b) 1 (c) 18 (d) 30 (e) 39

68. Trovare la soluzione fondamentale delle seguenti equazioni

(a) x2 − 29y2 = 1 (b) x2 − 26y2 = 1 (c) x2 − 41y2 = 1 (d) x2 − 74y2 = 1

69. Dimostrare che n2 + (n+ 1)2 e un quadrato perfetto per infiniti valori di n.

70. Dimostrare che se (x1, y1) e la soluzione fondamentale di x2 − dy2 = −1 allora la coppia

(x2, y2) definita dall’uguaglianza x2 + y2√d =

(x1 + y1

√d)2

e la soluzione fondamentale di

x2 − dy2 = 1.

71. Trovare il piu piccolo numero naturale n di tre cifre tale che la somma 1 + 2 + · · · + n e unquadrato perfetto.

72. Un numero naturale a si dice triangolare se esiste n ∈ N tale che a =n(n+ 1)

2. Il numero

36 e sia triangolare che quadrato dato che 36 = 62 =8 · 9

2. Trovare il piu piccolo numero

triangolare-quadrato maggiore di 36.

73. Trovare il piu piccolo numero naturale di due cifre della forma n(n+ 1)/3 che e un quadratoperfetto.

74. Risolvere l’equazione diofanteax2 + y2 = 4xy + 1

75. Trovare tutti i valori di n per cui il numero di diagonali di un poligono convesso di n lati e unquadrato perfetto. (Mathematical Reflection n. 5 (2009), Problem J135)

76. Trovare gli interi n per cui esiste un intero m tale che

1 + 2 + 3 + · · ·+m = (m+ 1) + (m+ 2) + · · ·+ n

77. Determinare gli interi positivi m,n tali che

m+ (m+ 1) + · · ·+ (n− 1) + n = mn

(International Mathematical Talent Search 2/31)

78. Dimostrare che esistono infiniti interi n tali che n, n+ 1, n+ 2 sono ognuno la somma di duequadrati perfetti. (Esempio 0 = 02 + 02, 1 = 02 + 12, 2 = 12 + 12).(W.L. Putnam Mathematical Competition 2000).

79. Trovare tutti i triangoli tali che le lunghezze dei lati sono interi consecutivi e la cui area eespressa da un numero intero.

80. Dimostrare che esistono infiniti interi n, multipli di 40 tali che 2n+ 1 e 3n+ 1 sono quadratiperfetti. (American Math Monthly E2606)

81. Dimostrare che esistono infiniti interi positivi n tali che n2 + 1 divide n!

82. Dimostrare che esistono infiniti interi positivi n tali che[√

2n]

+ 1 e un quadrato perfetto.

20

Riferimenti bibliografici

[1] Massimo Gobbino, Schede Olimpiche, U.M.I, Bologna (2010)

[2] C.D. Olds, Frazioni Continue, Zanichelli, Bologna (1968)

[3] David M. Burton, Elementary Number Theory, Allyn and Bacon, Boston (1980)

[4] Edward J. Barbeau, Pell’s Equation, Springer (2000)

[5] Titu Andreescu, Dorin Andrica, Ion Cucurezeanu,An introduction to Diophantine equations, Birkhauser, New York (2010)

[6] Kin Y. Li, Pell’s Equation (I), Mathematical Excalibur, vol.6, n.3 (2001)

[7] Kin Y. Li, Pell’s Equation (II), Mathematical Excalibur, vol.7, n.1 (2002)

[8] R.W. Owens, An algorithm to solve the Frobenius problem,Mathematics Magazine 76(4), (2003), pag. 264-275

21