1

CAPITOLO 1 I NUMERI NATURALI Il sistema decimale Originati dall’esigenza di contare, i numeri naturali rappresentano un modello adeguato per la rappresentazione astratta d’insiemi di oggetti, e possono essere rappresentati in molti modi. Quello largamente più diffuso è il cosiddetto sistema decimale posizionale, o in base dieci, rappresentato dalle cifre da 0 a 9. Questo significa che, ad esempio, il numero 731 è diverso dal 137, pur essendo costituiti dalle stesse cifre, perché 731= 700+30+1= 7 ⋅102 +3 ⋅101 +1⋅100 , mentre 137=100+30+7=1⋅102 +3 ⋅101 +7 ⋅100 . Osservando il modo con cui i due numeri sono stati rappresentati nel sistema decimale, è possibile dare una regola generale per la rappresentazione di qualsiasi numero naturale:

z = an ⋅10n + an−1 ⋅10

n−1 + ⋅ ⋅ ⋅+ a1 ⋅10+ a0 , dove i coefficienti, ovvero i termini ai ∈ 0,1,..., 9{ } , appartengono all’insieme delle cifre da 0 a 9. Notiamo che

731 : 10 = 73 e resto 1⇒ a0 =1, 73 : 10 = 7 e resto 3⇒ a1 = 3, 7 : 10 = 0 e resto 7⇒ a2 = 7 ,

e quindi, i coefficienti sono i resti delle successive divisioni del numero dato per 10. Questo spiega il senso della rappresentazione usuale di un numero naturale di n+1 cifre:

z = anan−1...a1a0 . Come è facile intuire, è possibile rappresentare i numeri naturali in una base qualsiasi, una volta accettato che le cifre nella rappresentazione numerica sono i resti delle successive divisioni per la base. Per esempio, in base 3 si ha:

2

731 : 3 = 243 e resto 2, 243 : 3 = 81 e resto 0, 81 : 3 = 27 e resto 0, 27 : 3 = 9 e resto 0, 9 : 3 = 3 e resto 0, 3 : 3 = 1 e resto 0, 1 : 3 = 0 e resto 1,

quindi 731=1⋅36 +0 ⋅35 +0 ⋅34 +0 ⋅33 +0 ⋅32 +0 ⋅31 +2 ⋅30 =1000002

Per inciso, l’ultima rappresentazione suggerisce anche come passare dalla base 3 alla base 10. Il vantaggio più grande apportato dalla notazione posizionale rispetto a quella additiva (tipo quella dei numeri romani, dove MCMXCVI = 1000 (M) + 900 (CM) + 90 (XC) + 5 (V) + 1 (I)), si riscontra nei calcoli con le operazioni aritmetiche fondamentali. Nel sistema posizionale le regole di calcolo possono essere raccolte nelle famose tavole che, una volta memorizzate, permettono di svolgere calcoli con relativa semplicità. 1.2 Numeri primi Tra i numeri naturali assumono una grande importanza i cosiddetti numeri primi, ovvero quei numeri maggiori di 1, che non ammettono divisori diversi da se stesso e da 1. I numeri che non sono primi si dicono composti. In generale, un numero a è multiplo di b se esiste un numero naturale c tale che a = bc : in questo caso si dice che b divide a e si indica con la notazione b|a . Dalla definizione di multiplo di un numero naturale seguono i seguenti fatti: - d | a, d | b ⇒ d | a+ b 2|6, 2|4⇒ 2|(6+4) =10 , - d | a ⇒ d | ac, ∀c ∈ N 3|9⇒ 3|9 ⋅2 =18 , - d|a, a|b, ⇒ d|b 3|6, 6|18⇒ 3|18 . Caratterizziamo ulteriormente i numeri primi attraverso alcuni importanti risultati.

3

Teorema della fattorizzazione unica: ogni numero naturale maggiore di 1 si può esprimere in un solo modo come prodotto di potenze di numeri primi. Si tratta di un teorema fondamentale dell’aritmetica, di cui dimostreremo tra breve soltanto l’unicità. La ricerca dei numeri primi all’interno dell’insieme dei numeri naturali suscita da sempre un grande interesse. Esaminiamo un metodo molto antico, ideato dal grande scienziato Eratostene. Il metodo, denominato crivello di Eratostene, consente, fissato un numero naturale N, di determinare tutti i numeri primi non superiori a N. In che modo? Semplicemente cancellando i multipli dei numeri il cui quadrato non supera N. Vediamo come funziona con un semplice esempio: determiniamo i numeri primi minori di N = 36 . Cancelliamo i multipli dei numeri da 2 a 6 (in quanto il quadrato di 7 supera 40): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 Il metodo ideato da Eratostene si basa sul fatto che un numero composto minore o uguale a 36, è divisibile per un numero minore o uguale a 6. Dimostriamo questo fatto considerando il numero n = ab ≤ 36 : se quanto detto non fosse vero, risulterebbe a > 6∧b > 6 e quindi n = ab > 36 , in contraddizione con la scelta di n = ab ≤ 36 . Adesso occupiamoci di stabilire quanti sono i numeri primi. La risposta a questa domanda fu data, sempre nell’antichità, dal matematico Euclide, ed è contenuta nel teorema che porta il suo nome, di cui, oltre all’enunciato, daremo anche una dimostrazione. Cominciamo con il seguente risultato di natura tecnica. Lemma. Se a,n ∈ N ,a ≠1 e a n , allora a non divide n+1.

Dimostrazione. Per assurdo, se a dividesse n+1 avremmo, poiché per ipotesi a divide n, n = r ⋅ a e n+1= s ⋅ a per determinati r, s ∈ N , tali che

n = r ⋅ an = s ⋅ a −1

#$%

⇒ r ⋅ a = s ⋅ a −1⇒ s − r( )a =1. Abbiamo quindi trovato una

4

scomposizione di 1 come prodotto di interi diversi da 1, e ciò è chiaramente impossibile. Di conseguenza a non può dividere n+1. Teorema (Euclide). I numeri primi sono infiniti. Dimostrazione (Euclide IX, 20)1. Supponiamo per assurdo che l’insieme dei numeri primi contenga una quantità finita di elementi, e sia p il maggiore di questi (consideriamo nota la proprietà di ordinamento dell’insieme dei numeri naturali). Moltiplichiamo tutti i numeri primi, e aggiungiamo 1 al risultato. Il numero n = 2 ⋅3 ⋅5 ⋅ ...⋅ p+1 così ottenuto dovrebbe essere non primo, essendo il più grande numero primo p, e chiaramente n > p . Quindi n è divisibile per almeno uno dei numeri primi pi : ∃q ∈ Z|n = q ⋅ pi . Allora n−1=1⋅2 ⋅ ..⋅ pi ⋅ ...⋅ p è divisibile per pi , mentre non lo è la sua

formulazione equivalente n−1= q ⋅ pi −1, dal momento che 1pi∉ Z .

L’insieme dei numeri primi non può quindi contenere un numero finito di elementi, come volevasi dimostrare. Il numero costruito nella dimostrazione suggerisce un metodo per costruire una successione di numeri primi. Purtroppo, ancora non sono state trovate formule per la generazione di numeri primi. Restano tuttora irrisolti due problemi sui numeri primi:

- (congettura di Goldbach, 1742): Ogni numero pari diverso da due può essere espresso come somma di due numeri primi,

- esistono infinite coppie di numeri primi gemelli, ovvero della forma p, p+2 .

Massimo comun divisore ed algoritmo euclideo Com’è noto, dati due numeri a,b ≠ 0∈ Z , l’insieme degli interi, si definisce massimo comun divisore il maggiore dei loro divisori comuni. Si considera nota la regola per il calcolo del MCD attraverso la scomposizione in fattori primi (giustificata, adesso, dal teorema della fattorizzazione unica): ad esempio, se a =18 = 2 ⋅32 , b = 24 = 23 ⋅3 , allora MCD(18,24) = 2 ⋅3= 6 .

1 Si tratta della proposizione 20 del libro IX degli Elementi di Euclide.

5

Esiste un metodo “antico” per il calcolo del MCD: il cosiddetto algoritmo2 euclideo, basato su un procedimento iterativo. Prima però, consideriamo il seguente risultato di carattere generale. Teorema. Se a e b sono due interi con b > 0 , esiste un intero q tale che a = qb+ r , dove r è un intero tale che 0 ≤ r < b . Dimostrazione. Senza eseguire la divisione ordinaria, possiamo comunque affermare che a è multiplo di b, oppure che a è compreso tra due multipli consecutivi di b. Nel primo caso a = qb e la tesi segue con r = 0 ; nel

secondo bq < a < q+1( )b = bq+ b , da cui segue 0 < a − bq := ra − bq < b

"#$

%$⇒ 0 < r < b .

La seguente considerazione può essere posta a fondamento dell’algoritmo euclideo: Proposizione 1. Da una relazione del tipo a = qb+ r segue che ogni divisore della coppia a,b( ) , lo è anche di b,r( ) .

Dimostrazione. Sia v un divisore di a,b( ) : a = hv b = kv . Poiché

r = a − qb = hv− qkv = h− qk( )v⇒ v divide r, e quindi è un divisore di b,r( ) .

Proposizione 2. Se d|r e d|b , a = bq+ r , allora d|a .

Dimostrazione. d|r⇒∃ #r : r = d #r , d|b⇒∃ #b : b = d #b . Di conseguenza a = qb+ r = qd !b + d !r = d (q !b + !r )⇒ d|a . Supponiamo di voler determinare il MCD (24,15) .

24 =1⋅15+915 =1⋅9+69 =1⋅6+36 = 2 ⋅3+0

Quando l’ultimo resto è zero, il resto precedente è il MCD; nell’esempio sopra, il MCD (24,15) è 3. In generale, il procedimento iterativo può essere schematizzato così:

2 Per algoritmo s’intende un metodo sistematico di calcolo.

6

MCD(a,b) :a = q1b+ r1b = q2r1 + r2r1 = q3r2 + r3...rn−1 = qn+1rn +0⇒ MCD(a,b) = rn ,

dal momento che rn = rn ⋅1+0 . Dobbiamo giustificare l’algoritmo euclideo.

Teorema (Euclide). rn = d := MCD(a,b) .

r0 := a; r1 := b r0 = q0r1 + r2r1 = q1r2 + r3...rn−2 = qn−2rn−1 + rnrn−1 = qn−1rnrn+1 = 0

Dimostrazione.d = MCD(a,b)⇒ d a − qb⇒ d r0,d r1⇒ d r2 = r0 − q0r1 . A catena,

d r3 , fino a d rn ⇒ rn ≥ d . Resta da dimostrare che rn ≤ d . Rileggiamo a

ritroso l’algoritmo euclideo: rn rn−1⇒ rn−2 = qn−1rn + rn = 1+ qn−1( ) rn ⇒ rn rn−2 .

Proseguendo fino al livello iniziale segue che rn r1 = be rn r0 = a , e quindi che

rnè un divisore comune di a,b( ) e che rn ≤ d . La seguente proposizione segue direttamente dall’applicazione dell’algoritmo euclideo.

7

Proposizione 3. (Teorema di Bézout) Se d = MCD(a,b) , allora esistono due numeri interi k e l tali che d = ka+ lb . La dimostrazione di questa proprietà poggia sul seguente procedimento.

24 =1⋅15+9⇒ 9 = 24−1⋅15

15 =1⋅9+6⇒ 6 =15−1⋅ (24−1⋅15)

9 =1⋅6+3⇒ 3= 24−1⋅15−1⋅ 15−1⋅ (24−1⋅15)$% &'⇒ 3= 2 ⋅24−3 ⋅15⇒ k = 2 l = −3

6 = 2 ⋅3+0

Esempio. 3= MCD(6,9)⇒∃k = −1,l =1tali che 3= −6+9 . Dimostrazione. Consideriamo l’insieme dei numeri che si formano combinando linearmente gli interi a e b, ovvero moltiplicando questi per un numero intero e prendendone la somma; formalmente M = x = au+ bv u,v ∈ Z{ }. In

generale, quando definiamo un insieme, occorre innanzitutto far vedere che questo non è vuoto, cioè che contiene almeno un elemento. Nel nostro caso è piuttosto semplice, in quanto gli interi a = a ⋅1+ b ⋅0 e b = a ⋅0+ b ⋅1 appartengono all’insieme. Inoltre, per come sono definiti gli elementi di M, se x ∈ M ⇒−x ∈ M ; sicuramente M contiene qualche intero positivo. Indichiamo con m il minimo3degli interi positivi contenuti in M (quindi esistono due numeri interi k e l tali che m = ka+ lb ). Faremo vedere che d = MCD(a,b) = m = ak + bl . Dimostriamo innanzitutto che m x per ogni x ∈ M . Se, per assurdo, ciò non fosse vero, esisterebbe un x ∈ M tale che x = qm+ r , con 0 < r < m . Quindi r = x − qm = au+ bv− q ak + bl( )⇒ r = a u− qk( )+ b v− ql( ) : avremmo dimostrato che r ∈ M , ma ciò è impossibile perché 0 < r < m contro la minimalità di m. Di conseguenza m divide sia a che b, quindi è un loro divisore comune e, come tale, m ≤ d . Per dimostrare l’uguaglianza occorre quindi far vedere che m ≥ d . Per questo scopo osserviamo che d = MCD(a,b) implica a = !a d e b = !b d per certi !a , !b ∈ Z ; di conseguenza ∀x = au+ bv ∈ M si ha x = !a du+ !b dv = !a u+ !b v( )d , e quindi d = MCD(a,b) divide ogni elemento di M, quindi m ≥ d . Abbiamo così dimostrato la tesi.

3L’esistenza del minimo di un sottoinsieme dei numeri naturali ha un carattere assiomatico.

8

La seguente proposizione è un corollario della precedente. Proposizione 4. Se 1= MCD(a,b) , allora esistono due numeri interi k e l tali che 1= ka+ lb .

Esempio. 1= MCD(5,9)⇒∃k = 2,l = −1tali che 1= 2 ⋅5+ −1( ) ⋅9 . Quest’ultima proprietà è fondamentale per la dimostrazione del teorema della fattorizzazione unica. Per questo scopo dimostriamo il seguente fatto. Lemma: se p è primo e p|ab , allora p|a o p|b . Dimostrazione. Facciamo vedere, per esempio, che se p non divide a, necessariamente deve dividere b. Infatti, se p /| a⇒ MCD(a, p) =1⇒∃k,l ∈ Z tali che ka+ lp =1, in virtù della proprietà 4. Moltiplicando per b l’ultima espressione e ricordando che p|ab⇒ ab = sp , otteniamo kab+ lbp = b⇒ ksp+ lbp = b⇒ (ks + lb) p = b⇒ p|b , come volevasi dimostrare. Il lemma può essere generalizzato al prodotto di un numero qualsiasi di interi, e porta alla conclusione che se p divide tale prodotto, allora dovrà dividere almeno uno dei fattori. Esercizi

1. Dimostrare che se p|abc , allora o p|a , o p|b , o p|c . 2. Calcolare d = MCD(a,b)e la coppia di interi k e l tali che d = ka+ lb

per le seguenti coppie di numeri naturali: a) 32,144( ) ; b) 56,212( ) ; c) 42,753( ) . Soluzioni a)d =16;k =1;l = −4 , b)d = 4;k = −5;l =19 , c )d = 3;k = −1;l =18 .

3. Dimostrare che, se a beb a , allora a = ±b .

4. Dimostrare che, sed abe MCD a,d( ) =1, allora d b .

5. Se d = MCD a,b( ) , allora ad, bd

sono primi tra loro.

6. Siano a,b∈ N . Indicati con m = mcm a,b( ) e con d = MCD a,b( ) , si dimostri che ab = md .

7. Se p a e q a , e se MCD p,q( ) =1, allora pq a .

9

8. (Test di primalità) p è primo se e solo se MCD a, p( ) =1per ogni scelta di a = 2,..., p−1.

Soluzioni

1. Se p /| a∧ p /|b , allora deve necessariamente dividere c. Se così non fosse, d = MCD p,c( ) =1e quindi per il teorema di Bézout ∃k,l ∈ Z tali che pk + cl =1. Moltiplicando ambo i membri per ab otteniamo ab = abpk + abcl = (abk + ql ) p , essendo abc divisibile per p, per ipotesi. Di conseguenza p divide ab, quindi deve dividere almeno uno dei due fattori, mentre abbiamo supposto che p /| a∧ p /|b . Di conseguenza questa supposizione non è vera, quindi p divide almeno uno dei fattori a, b, c come volevasi dimostrare.

2. Vedi sopra. 3. a b⇒ b = "b a , b a⇒ a = "a b , quindi

a = !a !b a⇒ a 1− !a !b( ) = 0⇒ !a !b =1⇒ !a = !b =1⇒ a = b!a = !b = −1⇒ a = −b

.

4. d|ab⇒∃q ∈ Z tale che ab = qd ; MCD a,d( ) =1⇒ ak + dl =1, per k,l ∈ Z . Moltiplicando per b l’ultima espressione risulta abk + dbl = b⇒ qdk + dbl = b⇒ qk + bl( )d = b e quindi d|b .

5. d = MCD a,b( )⇒∃k,h ∈ Z tali che a = kd e b = hd . Se, per assurdo,

ad, bd

non fossero primi tra loro, vorrebbe dire che

MCD ad, bd

!

"#

$

%&= 'd >1. Di conseguenza, potremmo scrivere

ad= !k !d , b

d= !h !d ⇒ a = (d !d ) !k e b = (d !d ) !h . Avremmo così trovato un

divisore comune (d !d ) della coppia di interi a, b più grande (essendo

!d >1) del massimo comun divisore. Di conseguenza ad, bd

sono primi

tra loro.

10

6. d = MCD a,b( )⇒∃ #a , #b ∈ Z a = #a d ∧b = #b d . Di conseguenza,

ab = !a d( ) !b d( ) = !a !b d( )d . Notiamo che !a !b d = !a !b d( ) = !a b , ma anche

!a !b d = !b !a d( ) = a !b ; di conseguenza !a !b d è il più piccolo multiplo comune di a,b .

7. Per l’esercizio precedente, seMCD p,q( ) =1⇒ pq = m . Poiché m è il minimo comune multiplo, e a è multiplo comune di p e di q, allora m = pq a .

8. ⇒( )Se p è primo, allora MCD a, p( ) =1 poiché non esiste alcun

a = 2,..., p−1 che divide p. ⇐( )Per assurdo, se p non fosse primo, allora esisterebbe a ∈1,2..., p−1tale che p = ka , con k numero intero. Di conseguenza, MCD a , p( ) = MCD a ,ka( ) = a >1, contro l’ipotesi

MCD a, p( ) =1per ogni scelta di a = 2,..., p−1. Pertanto pè un numero primo.

L’unicità della fattorizzazione di un numero naturale Adesso possiamo dimostrare l’unicità della fattorizzazione di un numero naturale maggiore di 1. Dimostrazione (teorema della fattorizzazione unica). Per assurdo supponiamo che un numero naturale maggiore di uno possa essere fattorizzato in due modi diversi, cioè che esistano due diversi insiemi di numeri primi, p1,..., pr( ) e q1,...,qs( ) , tali che N = p1p2...pr = q1q2...qs . Partiamo da

p1 : poiché divide N , e N = q1q2...qs , per il lemma precedente esiste k ∈1,..., s tale che p1 divide qk ; poiché quest’ultimo è primo, necessariamente p1 = qk . Togliamo questi due fattori dalla lista N = p1p2...pr = q1q2...qs , e ripetiamo il ragionamento per p2 , per p3 , fino all’ultimo pr . In questo modo, avendoli eliminati dalla lista p1p2...pr = q1q2...qs , il membro di sinistra è uguale a uno. E quello di destra? Dovrà per forza essere anch’esso uguale a uno, essendo q1,...,qs( ) primi, quindi maggiori di

11

uno. Abbiamo quindi dimostrato che, a meno dell’ordine, la scomposizione di un numero composto è unica. Le equazioni diofantee di primo grado Le considerazioni fatte sul massimo comun divisore e sulle proprietà basate sull’algoritmo euclideo sono fondamentali nella ricerca delle soluzioni intere di equazioni algebriche di primo grado, a coefficienti razionali. Le equazioni diofantee devono il loro nome al matematico alessandrino Diofanto, vissuto tra il III e il IV secolo d.C. e noto come il padre dell’algebra. Fu autore dell’opera Arithmetica. A lui si devono lo studio delle equazioni indeterminate e lo sviluppo del simbolismo matematico.

Problema. Si calcoli, mediante l’utilizzo dell’algoritmo euclideo, il MCD(45,24), evidenziando i vari passaggi, e determinando due numeri interi k e l tali che MCD(45, 24) = 45k + 24l . Soluzione.

- 45=1⋅24+ 2124 =1⋅21+321= 7 ⋅3+ 0⇒MCD(45, 24) = 3

12

I numeri interi k e l tali che MCD(45,24) = 45k +24l si determinano con il noto procedimento: 45=1⋅24+ 2124 =1⋅21+3⇒ 3= 24−1⋅21= 24−1⋅ 45−1⋅24( ) = 45(−1)+ 24(2)

k = −1; l = 2

La soluzione di problemi di questo tipo può essere ricondotta a quella delle cosiddette equazioni diofantee, dove si cercano numeri interi x e y che soddisfano ax + by = c . Per convincersi di quanto appena detto è sufficiente riscrivere l’enunciato del teorema di Bézout con x,y al posto k,l e riflettere sulla somiglianza:

ak + bl = dax + by = d .

Si può dimostrare che un’equazione di primo grado in due incognite a coefficienti razionali del tipo ax + by = c ammette soluzioni intere se, e soltanto se, il termine noto c è multiplo del MCD(a,b) . Proposizione. L’equazione diofantea ax + by = c ammette soluzioni intere se e soltanto se d = MCD(a,b)|c . Dimostrazione (⇒ ). Sia d = MCD(a,b) , allora d|a e d|b , di conseguenza a = !a d e b = !b d . Se x := m e y := n sono soluzioni intere, allora !a dn+ !b dn = c⇒ c|d .

(⇐ ). Viceversa, se d|c⇒ c = dq . Per il teorema di Bézout ∃k,l ∈ Z tali che ak + bl = d . Se moltiplichiamo per q ambo i membri dell’ultima equazione

otteniamo (ak + bl )q = dq = c⇒ a(kq)+ b(lq) = c⇒x := kqy := lq

"#$

%$una coppia di

soluzioni intere, come volevasi dimostrare. Ad esempio, l’equazione 3x + 6y = 22 non ammette soluzioni intere perché MCD(3, 6) = 3 /| 22 . Ancora, l’equazione 3x −4 y = 2 ammette soluzioni intere, mentre l’equazione 4x +6 y = 3 no, com’è possibile vedere anche dalla loro rappresentazione grafica: a differenza della seconda, la prima retta passa per punti a coordinate intere.

13

-20 -16 -12 -8 -4 0 4 8 12 16 20

-12

-8

-4

4

8

12

La proposizione appena vista permette di stabilire se un’equazione diofantea ammette soluzioni intere, inoltre ci suggerisce un metodo per determinarne la forma generale. Infatti, se !x , !y( ) e x*, y *( ) rappresentano due coppie di soluzioni

dell’equazione ax + by = c , allora la coppia x0 = !x − x*, y0 = !y − y *( )è soluzione della cosiddetta equazione omogenea ax + by = 0 (verificare!). Ricapitolando, una soluzione dell’equazione di partenza può essere sempre vista come la somma di una soluzione particolare x*, y *( ) , e di quelle dell’equazione omogenea, cioè tutte le coppie della forma x0 = bn; y0 = −an( ) , con n ∈ Z (verificare).

Problema. Si determinino le soluzioni intere dell’equazione 17x −15 y = 5. Soluzione. Innanzitutto s’individuano le soluzioni dell’equazione omogenea

associata: 17x −15 y = 0⇒x0 =15n

y0 =17n

#$%

&%n ∈ Z e si osserva che

MCD(17,15) =1 divide il termine noto, per cui esistono infinite soluzioni intere dell’equazione diofantea; cerchiamo una soluzione particolare sfruttando la proprietà dell’algoritmo euclideo, 17=1⋅15+215 = 7 ⋅2+1⇒1=15−7 ⋅2 =15−7 17−1⋅15( ) =17(−7)+15(8) . La coppia

14

x = −7, y = −8 è soluzione dell’equazione 17x −15 y =1; di conseguenza una soluzione particolare dell’equazione 17x −15 y = 5 si otterrà moltiplicando

per 5 le soluzioni trovate: !x = −35!y = −40

#$%

&%. Le soluzioni, espresse nella forma

x = !x + x0y = !y + y0

"#$

%$, sono x = −35+15n

y = −40+17n

"#$

%$.

Esercizi 1. Si dica per quali valori di k ∈ Z l’equazione kx +12 y = 3ammette

soluzioni intere. 2. Problema. Un rivenditore deve stabilire quanti pezzi (indivisibili) x di

un certo prodotto deve acquistare al prezzo di 5€/ pz , sapendo che in magazzino possono essere stoccati un massimo di 100 pezzi, che le spese fisse ammontano a 100€ , e che rivendendone y al prezzo di 9€/ pz , deve chiudere il bilancio acquisti-vendite in pareggio.

3. Problema. Un rivenditore deve stabilire quanti pezzi (indivisibili) x di un certo prodotto deve acquistare al prezzo di 4€/ pz , sapendo che in magazzino possono essere stoccati un massimo di 50 pezzi, che le spese fisse ammontano a 50€ , e che rivendendone y al prezzo di 7€/ pz , deve chiudere il bilancio acquisti-vendite in pareggio.

Soluzioni 1. Indichiamo con dk = MCD k,12( ) : l’equazione ammette soluzioni

intere se e solo se dk|3 . Innanzitutto, poiché 12 è pari, se k è dispari

MCD k,12( ) =1, e l’equazione ammette soluzioni intere. Se k fosse un multiplo di 12 o di 6 (ovvero un multiplo di un divisore di 12 maggiore di 3) l’equazione non ammette soluzioni intere perché MCD k,12( ) = 6n > 3. In definitiva, l’equazione ammette soluzioni

intere se e soltanto se k ≠ 6 2n+1( ),12n{ } .

2. In sintesi, l’equazione risolvente con i vincoli imposti dal problema è la seguente:

15

9 y−5x −100 = 00 ≤ x ≤1000 ≤ y ≤ x

#

$%%

&%%

⇒x = 9n−200y = 5n−100

⇒ 0 ≤ 9n−200 ≤1005n−100 ≤ 9n−200

#$%

&%

#$%

&%. Di

conseguenza, i valori che può assumere l’intero n (e di conseguenza x e y

sono:

n ≥ 2009

n ≤ 3009

n ≥ 25

#

$

%%%

&

%%%

⇒ 25 ≤ n ≤ 33⇒ x = 25,34,43,52,61,70,79,88,97y = 25,30,35,40,45,50,55,60,65

.

3. L’equazione risolvente e i vincoli sono compendiati nel seguente

sistema misto:

16

7 y−4x −50 = 00 ≤ x ≤ 500 ≤ y ≤ x

⎧

⎨⎪⎪

⎩⎪⎪

⇒

x = 5+7n y =10+4n

0 ≤ x ≤ 500 ≤ y ≤ x

⎧

⎨

⎪⎪

⎩

⎪⎪

⇒

5+7n ≥ 05+7n ≤ 5010+4n ≥ 0

10+4n ≤ 5+7n

⎧

⎨⎪⎪

⎩⎪⎪

, da cui segue

n ≥ − 57⇒ n ≥ 0

n ≤ 457⇒ n ≤ 6

n ≥ −104⇒ n ≥ −2

n ≥ 53⇒ n ≥ 2

⎧

⎨

⎪⎪⎪⎪⎪

⎩

⎪⎪⎪⎪⎪

⇒ n = 2,3,4,5,6⇒

x =19x = 26x = 33x = 40x = 47

.

Classi di resto Consideriamo, all’interno dell’insieme dei numeri interi, la relazione che associa due numeri a, b se questi danno lo stesso resto nella divisione per uno stesso numero n. Una relazione di questo tipo si dice congruenza, ed i numeri a, b si dicono congrui modulo n. Con la notazione di Gauss si scrive:

17

a ≡ bmod(n) ,

e si legge “a è congruo a b modulo n”, se n|(a − b) . La congruenza modulo n è una relazione di equivalenza sull’insieme dei numeri interi. Verifichiamo le proprietà. 1. Proprietà riflessiva: n|0 = a − a⇒ a ≡ amod(n) ; 2. Proprietà simmetrica: n|(a − b)⇒ n|−(a − b) = (b− a)⇒ b ≡ amod(n) ; 3. Proprietà transitiva: n|(a − b) , n|(b− c )⇒ n|(a − b+ b− c )⇒ a ≡ cmod(n) . Le relazioni di equivalenza operano una partizione nell’insieme in cui sono definite, suddividendolo in sottoinsiemi, detti classi di equivalenza, tali che:

I. L’unione di tutti i sottoinsiemi forma l’insieme di partenza; II. L’intersezione di due qualsiasi sottoinsiemi distinti è l’insieme vuoto; III. Nessun sottoinsieme è vuoto.

L’insieme degli interi, con la relazione di congruenza, viene suddiviso in classi di equivalenza dette classi di resto. L’insieme formato dalle classi di equivalenza è detto insieme quoziente. Lo schema seguente illustra la disposizione di tutti gli interi all’interno delle classi di resto modulo 3.

Z3

−9 −8 −7−6 −5 −4−3 −2 −10"# $% 1"# $% 2"# $%3 4 56 7 89 10 11

In particolare, si denota con Zn ≡ 0"# $%, 1"# $%,..., n−1"# $%{ } l’insieme quoziente

degli interi in base alla relazione di congruenza modulo n. Le classi di resto

18

j!" #$, con j = 0,1,2...,n−1 contengono ognuno gli interi che, nella divisione per n, danno come resto j. Il comportamento delle classi di resto rispetto all’operazione di addizione può essere riassunto nelle cosiddette tavole di composizione. Vediamo come si costruiscono. Per cominciare, occorre chiarire il significato dell’addizione 1!" #$+ 2!" #$ in un

determinato insieme quoziente, ad esempio Z3 = 0!" #$, 1!" #$, 2!" #${ } .

Quest’operazione è rappresentativa dell’addizione di tutti gli interi appartenenti alle due classi, quindi è necessario stabilire una legge di formazione di tutti i numeri appartenenti a una determinata classe di resto. Ricordiamo che a ∈ 1"# $%se, nella divisione per 3, dà come resto 1:

a ≡1mod(3)⇒ 3 a −1( )⇒∃k ∈ Z a = 3k +1; analogamente

b ≡ 2mod(3)⇒ 3 b−2( )⇒∃h ∈ Z b = 3h+2 . In base a queste leggi di

formazione possiamo scrivere 1!" #$+ 2!" #$= 3k +1( )+ 3h+2( ) = 3 h+ k +1( ) = 0!" #$ . Riepiloghiamo in tabella:

Z3,+( ) 0[ ] 1[ ] 2[ ]

0[ ] 0!" #$ 1!" #$ 2!" #$

1!" #$ 1!" #$ 2!" #$ 0!" #$

2!" #$ 2!" #$ 0!" #$ 1!" #$ Esercizio. Scrivere la tavola di composizione per la moltiplicazione in Z3 .

Z3,•( ) 0[ ] 1[ ] 2[ ]

0[ ] 0!" #$ 0!" #$ 0!" #$

1!" #$ 0!" #$ 1!" #$ 2!" #$

2!" #$ 0!" #$ 2!" #$ 1!" #$

19

Z4 ,+( ) 0[ ] 1[ ] 2[ ] 3[ ]

0[ ] 0[ ] 1[ ] 2[ ] 3[ ] 1[ ] 1[ ] 2[ ] 3[ ] 0[ ] 2[ ] 2[ ] 3[ ] 0[ ] 1[ ] 3[ ] 3[ ] 0[ ] 1[ ] 2[ ]

L’aritmetica delle classi di resto è detta modulare. Ad esempio il quadrante dell’orologio, dove la lettura dell’ora è modulo 12 (le 5 del mattino e le 17 del pomeriggio sono “congrue” modulo 12 perché a quell’ora le lancette sono nella stessa configurazione 0!" #$= 12−24{ }, 1!" #$= 1−13{ }, 2!" #$= 2−14{ },...); oppure la disposizione dei

vertici di un triangolo equilatero secondo le rotazioni di 120° attorno al proprio centro:

Consideriamo le seguenti proprietà “aggiuntive” della congruenza: se a ≡ "a mod(n) e b ≡ "b mod(n) , allora

4. (a± b) ≡ ( "a ± "b )mod(n); 5. ab ≡ "a "b mod(n) . Esercizio. Porre a = !a + rn e b = !b + sne verificare le proprietà 4 e 5 della congruenza. Riportiamo per convenienza il quadro complessivo delle cinque proprietà della congruenza modulo n. 1. Proprietà riflessiva: n|0 = a − a⇒ a ≡ amod(n) ; 2. Proprietà simmetrica: n|(a − b)⇒ n|−(a − b) = (b− a)⇒ b ≡ amod(n); 3. Proprietà transitiva: n|(a − b) , n|(b− c )⇒ n|(a − b+ b− c )⇒ a ≡ cmod(n) . 4. Se a ≡ "a mod(n) e b ≡ "b mod(n) , allora (a± b) ≡ ( "a ± "b )mod(n); 5. Se a ≡ "a mod(n) e b ≡ "b mod(n) , allora ab ≡ "a "b mod(n) .

20

Le equazioni con le classi di resto Un’interessante applicazione del metodo per la ricerca delle soluzioni intere di un’equazione diofantea, è rappresentata dal procedimento per la risoluzione delle equazioni con le classi di resto, ovvero equazioni del tipo

ax!" #$= b!" #$mod(n) . Intanto, qual è il significato di questa scrittura? Dire ax[ ] = b[ ] modulo n significa affermare che le due classi di resto coincidono, e se due numeri appartengono alla stessa classe di resto, allora sono congrui modulo n, quindi n divide la loro differenza:

ax − b = ny . Di conseguenza, risolvere l’equazione ax!" #$= b!" #$mod(n) equivale a cercare le soluzioni intere in x (che ci interessa) ed in y (che ci interessa meno), dell’equazione ax − ny = b . Esempio. Risolvere l’equazione 14x!" #$= 21!" #$mod(77) .

• In base a quanto appena accennato cerchiamo le soluzioni intere dell’equazione 14x −77 y = 21. Possiamo dividere ambo i membri per 7, ottenendo l’equazione equivalente 2x −11 y = 3. Verificato che quest’equazione ammette soluzioni intere, il metodo per la loro

ricerca conduce alle soluzioni x =11n−15y = 2n−3

"#$

%$. A noi interessa

x =11n−15 . Ora, poiché 15 =11+4 , la soluzione può essere scritta in una forma più adeguata al contesto in cui è inserita, ovvero quello delle classi di resto: x =11n−4 .

Esercizi

1. Risolvere la seguente equazione: 18x!" #$= 16!" #$mod40 . 2. (Problema 25 vecchio libro di testo). Un marziano, dopo aver visto

scritta l’equazione x2 −16x +41= 0 , invitato a scrivere la differenza delle radici, scrive 10. Sapendo che i numeri tra 0 e 6 coincidono con quelli in base 10, si dica quante dita ha il marziano.

3. Si attribuisca un significato alla frazione 14mod(7) .

21

4. Si attribuisca un significato alla frazione 14mod(6) .

5. Dimostrare che per ogni n > 0 il numero 5n +2 ⋅3(n−1) +1è divisibile per 8.

6. Dire a quale classe di resto modulo 5 appartiene il numero 1+2+22 + ...+219 .

7. (Problema 34 vecchio libro di testo) E’ dato un cesto di uova; si sa

che se si tolgono a due a due resta un uovo, se si tolgono a tre a tre ne restano due, mentre se si tolgono a quattro a quattro ne restano tre. Dire qual è il numero minimo di uova nel cesto.

8. (Problema 74 vecchio libro di testo). Due cercatori d’oro hanno due grandi sacchi di pezzi d’oro. Il primo ha solo pezzi da 15 grammi, il secondo solo pezzi da 21 grammi. Può il primo pagare al secondo un debito di 27 grammi d’oro? Potrebbe il secondo pagare al primo un debito di 29 grammi d’oro?

Soluzioni

1. 40 | 18x −16( )⇒18x −16 = 40y⇒ 9x − 20y = 8 . Le soluzioni dell’equazione

omogenea sono x0 = 20ny0 = 9n

!"#

$#, una soluzione particolare è data da

!x = 9 ⋅8 = 72!y = 4 ⋅8 = 32

#$%

&%per cui x = 20n+ 72 = 20n+32 .

2. Indicato con n il numero di dita del marziano (si suppone che abbia

due mani, ognuna con lo stesso numero di dita), ragionando come faremmo in base dieci scriviamo: 16 =1⋅n1 + 6 ⋅n0; 41= 4 ⋅n1 +1⋅n0; 10 =1⋅n + 0 ⋅n0 . In questo modo i

coefficienti dell’equazione di secondo grado sono a =1=1⋅n0; b = −16 = −(n+ 6); c = 41= (4n+1) , e la differenza delle radici,

espressa dalla condizione x2 − x1 = Δa

⇒10 = n = (n+ 6)2 − 4(4n+1)1

⇒ n = 8 .

3. Si tratta di trovare il “reciproco di 4 modulo 7”, ovvero la classe di resto che, moltiplicata per la classe di 4, dà come risultato la classe di 1: si tratta della classe di resto modulo 2: 1

4mod(7) = 2[ ]7 . Infatti

2[ ]7 ⋅ 4[ ]7 = 8[ ]7 = 1[ ]7 .

22

4. Stavolta non è possibile attribuire un significato alla frazione. Infatti,

se moltiplichiamo 4 per ognuno dei numeri da 1 a 5, non otteniamo mai un numero che, diviso per 6, dà come resto uno.

5. Dall’osservazione delle successive potenze di 5 possiamo concludere che 5n ∈ 5"# $%8 se n è dispari, oppure che 5n ∈ 1"# $%8 se n è pari. Ora,

sempre per n pari, 3(n−1) ∈ 3#$ %&8 e per n dispari 3(n−1) ∈ 1#$ %&8 .

Ricapitolando, 5n +2 ⋅3(n−1) +1∈ 1$% &'+2 3$% &'+ 1$% &'= 0$% &' se n è pari, e

5n +2 ⋅3(n−1) +1∈ 5$% &'+2 1$% &'+ 1$% &'= 0$% &' se n è dispari. In ogni caso giungiamo al risultato cercato.

6. Osserviamo che le classi di resto a cui appartengono le potenze di 2 che costituiscono i singoli addendi si ripetono con questa periodicità: 1∈ 1[ ] 2 ∈ 2[ ] 4∈ 4[ ] 8∈ 3[ ] 16 ∈ 1[ ] 32 ∈ 2[ ] 64∈ 4[ ] 128∈ 3[ ] . La

periodicità è giustificata dalle proprietà aggiuntive. Quindi la somma fino all’addendo 219 avviene contando 1!" #$+ 2!" #$+ 4!" #$+ 3!" #$= 1+2+4+3!" #$= 10!" #$= 0!" #$ esattamente 5 volte. La

somma è quindi divisibile per 5, quindi appartiene alla classe di resto 0.

7. Il numero minimo di uova N appartiene alla classe di resto 1 modulo due, a quella 2 modulo tre, e a quella 3 modulo quattro:

N ∈ 1"# $%2 ⇒ N = 2m+1; N ∈ 2"# $%3 ⇒ N = 3n+2; N ∈ 3"# $%4 ⇒ N = 4k +3

I numeri di uova possibili si ottengono risolvendo le equazioni diofantee (a soluzioni intere!) che si ottengono uguagliando le espressioni sopra:

2m−3n =12m−4k = 2⇒ m−2k =1

#$%

&%. Dalla prima equazione segue, ad esempio,

m = 5 e n = 3 . Sostituendo nella seconda equazione otteniamo k = 2 . Per questi valori risulta N =11.

8. Nella transazione (con resto) indicati con x e con y il numero di pezzi rispettivamente da 15 e da 21 grammi, per rispondere alla domanda occorre risolvere l’equazione diofantea 15x −21 y = 27⇒ 5x −7 y = 9 . Le soluzioni sono x = 3 e y = 2 . Nel secondo caso, poiché MCD(15, 21) = 3

23

non divide 29, l’equazione risolvente 21 y−15x = 29non ha soluzioni intere; il pagamento non può quindi avvenire.

Il problema presentato nell’esercizio numero 7 è un caso particolare del cosiddetto Teorema cinese del resto. Teorema. Siano p1,..., pk numeri interi coprimi, ovvero tali che

MCD pi , p j( ) =1 per ogni i ≠ j compresi nella lista 1,2,...,k . Allora il

sistema

x ≡ b1mod p1( )x ≡ b2 mod p2( )

...x ≡ bkmod pk( )

"

#

$$$

%

$$$

è risolubile simultaneamente per ogni scelta di

b1,b2,...,bk ∈ Z .

Dimostrazione.

x ≡ b1mod p1( )x ≡ b2 mod p2( )

...x ≡ bkmod pk( )

"

#

$$$

%

$$$

⇒

x − p1 y1 = b1x − p2 y2 = b2

...x − pk yk = bk

"

#

$$

%

$$

⇒

x = p1 y1 + b1x = p2 y2 + b2

...x = pk yk + bk

"

#

$$

%

$$

;

segue la catena di uguaglianze pi yi − p j y j = bj − bi ∀i ≠ j ∈1,2,...,k .

Poiché MCD pi , p j( ) =1 e 1 bj − bi( ) , allora l’equazione diofantea nelle

incognite yi e y j ammette soluzioni intere.

24

“Liceo Scien t i f i c o Stata le “Guido Caste lnuovo”

COMPITO DI MATEMATICA Classe III sezione E

15/10/2015

Problema Nel frigorifero di un supermercato è contenuto un certo numero di mele tutte uguali. Sappiamo che, se le prendiamo a 3 a 3 ne restano 2, mentre se ne prendiamo a 5 a 5 ne resta una sola.

a) Qual è il numero minimo di mele contenute nel frigorifero? b) In frigorifero sono contenuti 22 kg di mele acquistati al prezzo di 0,50€ kg . Sono previsti due formati per la vendita: sacchetti da 1kg al prezzo di 2€ kg , e sacchetti da 3kg al prezzo di 1€ kg . Si trovi il numero x di sacchetti da 1kg e quello y di sacchetti da 3kg che devono essere venduti al fine di realizzare un guadagno di 10€ . Rappresenta graficamente la retta associata all’equazione risolutiva del problema, completa dei vincoli opportuni.

c) Qual è la combinazione di sacchetti da 1kg e da 3kg che lascia in frigorifero il minor numero di mele? E quella più vantaggiosa per il venditore? Prova a commentare i risultati ottenuti.

Quesiti

1. Esistono delle analogie tra la sequenza dei vertici di un triangolo equilatero, ottenuta in seguito a successive rotazioni di 120° rispetto al centro, e l’operazione di addizione in Z3 ?

2. Risolvere in Z6 l’equazione 3x!" #$= 14!" #$. 3. Dimostrare che l’equazione diofantea ax + by = c ammette soluzioni

intere se e solo se d = MCD a,b( )divide il termine noto c.

25

CORREZIONE Problema

a) Qual è il numero minimo di mele contenute nel frigorifero? • Il prelievo di mele dal frigorifero è un problema di congruenza di interi; indicato

con N il numero di mele contenute in frigorifero, risulta

N ≡ 2mod 3( )⇒ N −2( ) = 3xN ≡1mod 5( )⇒ N −1( ) = 5 y

$

%&

'&⇒ 3x +2 = 5 y+1. Si tratta quindi di

cercare tra le soluzioni dell’equazione diofantea 5 y−3x =1, quella che restituisce il minimo valore di N. Le soluzioni dell’omogenea sono

x0 = 5n

y0 = 3nn ∈ Z ⇒ x = 5n+3

y = 3n+2⇒

N = 5 y+1=15n+11N = 3x +2 =15n+11

. La condizione

N ≥ 0 restituisce 15n+11≥ 0⇒ n ≥ 0⇒ Nmin =11. b) La funzione di bilancio è 2x +3 y−11=10⇒ 2x +3 y = 21. I vincoli riguardano

la quantità disponibile di mele in frigorifero, x +3 y ≤ 22 , e la positività del

numero di sacchetti per questioni pratiche. In definitiva:

2x +3 y = 21x +3 y ≤ 22x ≥ 0, y ≥ 0

#

$%%

&%%

.

Procediamo con ordine; per quanto riguarda l’equazione 2x +3 y = 21, si ha che

1= MCD 3,2( )|21⇒ x =12, y = −1 è una soluzione particolare da

aggiungere a quella dell’equazione omogenea x0 = −3n, y0 = 2n per ottenere

x = −3n+12y = 2n−1

"#$

%$n ∈ Z . Scriviamo adesso il sistema dei vincoli al fine di

determinare i valori interi di n che restituiscono soluzioni x, y accettabili:

−3n+12+6n−3≤ 22−3n+12 ≥ 02n−1≥ 0

$

%&

'&

⇒3n ≤133n ≤122n ≥1

$

%&

'&

⇒12≤ n ≤ 4⇒ n =1,2,3,4 . Le

26

soluzioni corrispondenti ai valori di n ammissibili sono in definitiva: n =1⇒ 9,1( );n = 2⇒ 6,3( );n = 3⇒ 3,5( );n = 4⇒ 0,7( ) .

c) La combinazione di sacchetti dei due formati che lascia in frigorifero il minor numero di mele è 0,7( ) perché corrisponde alla vendita di 3kg ⋅7= 21kg di mele,

facendone restare 1kg soltanto in frigorifero. Il motivo è da ricercarsi nella convenienza del formato più grande rispetto a quello più piccolo. L’informazione può essere dedotta dall’osservazione del grafico, essendo la soluzione 0,7( )quella

più vicina alla retta che delimita il semipiano x +3 y ≤ 22.

Quesiti 1. Sì, le analogie esistono. Infatti, se associamo alla rotazione di 120° rispetto al

centro del triangolo equilatero la classe di resto [1], a quella di 240° la classe [2], e a quella di 360° la classe [0], possiamo associare alla composizione di rotazioni successive l’operazione di addizione in Z3 ed ottenere una tavola di composizione del tutto analoga.

2. 3x!" #$= 14!" #$⇒ 3x ≡14mod(6)⇒ 6| 3x −14( )⇒ 3x −14 = 6 y . Occorre

quindi cercare soluzioni intere dell’equazione 3x −6 y =14 . Poiché MCD(6,3) = 3 /|14 , l’equazione non ammette soluzioni intere; di conseguenza

l’equazione 3x!" #$= 14!" #$ non ammette soluzioni in Z6 .

3. Dimostrazione (⇒ ). Sia d = MCD(a,b) , allora d|a e d|b , di conseguenza a = !a d e b = !b d . Se x := m e y := n sono soluzioni intere, allora !a dn+ !b dn = c⇒ d|c .

(⇐ ). Viceversa, se d|c⇒ c = dq . Per il teorema di Bézout ∃k,l ∈ Z tali che ak + bl = d . Se moltiplichiamo per q ambo i membri dell’ultima equazione

27

otteniamo (ak + bl )q = dq = c⇒ a(kq)+ b(lq) = c⇒x := kqy := lq

"#$

%$una coppia di

soluzioni intere, come volevasi dimostrare. Approfondimento: il binomio di Newton e la divisibilità Quanto visto finora costituisce uno strumento utile per stabilire criteri generali di divisibilità. Nel caso delle potenze, può essere vantaggioso conoscere il cosiddetto binomio di Newton, un’espressione del tipo (a+ b)n . Lo sviluppo della potenza di questo binomio può essere associato al cosiddetto “triangolo di Tartaglia”, con il quale vengono rappresentati (a meno del segno) i coefficienti dello sviluppo:

1

1 2 1 ⇒ (x + y)2 = x2 +2xy+ y2

1 3 3 1 ⇒ (x + y)3 = x3 +3x2 y+3xy2 + y3

1 4 6 4 1 ⇒ (x + y)4 = x4 +4x3 y+6x2 y2 +4xy3 + y4

...

.

Osserviamo ad esempio l’ultimo sviluppo: se portiamo il termine x4 a sinistra otteniamo (x + y)4 − x4 = 4x3 y+6x2 y2 +4xy3 + y4 = y ⋅ (4x3 +6x2 y+4xy2 + y3 ) := y ⋅m ;

da questo segue che y| x + y( )4− x4 e quindi, in generale, y|(x + y)n − xn .

Esempio. Dimostrare che 5n −1 è divisibile per 4. • Poiché 5= 4+1, possiamo scrivere 5n −1= (4+1)n −1. Per quanto osservato

in precedenza, 4 divide (4+1)n −1n , ovvero 5n −1 , come volevasi dimostrare.

• Oppure: poiché 5∈ 1[ ]mod(4) , per la proprietà “aggiuntiva” 5, tutte le potenze di 5 appartengono alla classe di resto 1[ ] modulo 4, da cui segue che 4 divide 5n −1 .

Un criterio per la divisibilità La proprietà 5 della congruenza modulo n permette di determinare i resti delle divisioni delle successive potenze di 10 per un numero dato. Per esempio, poiché 10 ≡ −1mod(11) , allora 102 ≡ −1( )2 mod(11) , e così via. Di

conseguenza, se z = anan−1...a0 = ak10k

k=0

n

∑ , la sua classe di resto modulo 11 è

28

z[ ] = ak10k

k=0

11

∑"

#$

%

&'= ak10

k"# %&k=0

n

∑ = ak[ ]k=0

n

∑ 10k"# %&= ak (−1)k

k=0

n

∑ . Morale, un numero intero è

divisibile per 11 se la somma delle cifre a segno alterno è zero. Per esempio, z =121⇒ z[ ] =1− 2+1= 0 . Analogamente possiamo stabilire criteri di divisibilità per 3 o per 9. Infatti, 10 ≡1mod(3) , e pure 10 ≡1mod(9) . Questo significa che la verifica della divisibilità viene condotta sulla somma delle cifre: se questa è multipla di 3, o di 9, allora il numero è divisibile per 3 o per 9. Come ultimo caso, studiamo la divisibilità per 7. Risulta: 10 ≡ 3mod(7)⇒102 ≡ 2mod(7)⇒103 ≡ (−1)mod(7)⇒104 ≡ (−3)mod(7)⇒105 ≡ (−2)mod(7)⇒106 ≡1mod(7)

Esercizi 1. Determinare a quale numero compreso tra 0 e 6 è congruo modulo 7 il

numero 11⋅18 ⋅2322 ⋅13⋅19 . 2. Determinare un criterio di divisibilità per 4, e per 5. Il “piccolo” teorema di Fermat4 Un importante criterio di divisibilità è fornito dal seguente risultato.

Teorema (Fermat). Se p è primo e p /| a , allora a p−1 ≡1mod( p) . Facciamo precedere la dimostrazione da un esempio numerico. Siano a = 6, p = 5 . Evidentemente p è un numero primo che non divide a; inoltre risulta a p−1 = 65−1 =1296 ≡1mod(5) . Osserviamo che i numeri 1⋅6,2 ⋅6,3 ⋅6,4 ⋅6 non sono divisibili per 5. Infatti, non essendo 6 divisibile per 5, dovrebbero esserlo gli interi 1,2,3,4 cosa chiaramente impossibile dal momento sono numeri minori del numero primo 5. Inoltre, i numeri 1⋅6,2 ⋅6,3 ⋅6,4 ⋅6 non sono nemmeno congruenti tra loro modulo 5, sempre per quanto appena detto. Ne consegue che i numeri 1⋅6,2 ⋅6,3 ⋅6,4 ⋅6 sono congruenti ai numeri 1,2,3,4 in un determinato ordine (un resto, nella divisione per 5, devono pur averlo!). In particolare

4PierredeFermat(1601-1665)matematicoemagistratofrancese.

29

1⋅6 ≡1mod(5)2 ⋅6 ≡ 2mod(5)3 ⋅6 ≡ 3mod(5)

4 ⋅6 ≡ 4mod 5( )

.

Se moltiplichiamo i numeri 1⋅6,2 ⋅6,3 ⋅6,4 ⋅6 tra loro e riscriviamo opportunamente il risultato otteniamo 1⋅2 ⋅3 ⋅4( ) ⋅64 . Sempre per la primalità di 5, e per il fatto che 5 non divide 6, 1⋅2 ⋅3 ⋅4( ) ⋅64 ≡ 1⋅2 ⋅3 ⋅4( )mod 5( ) da cui segue 64 ≡1mod 5( ) . Abbiamo

verificato il piccolo teorema di Fermat, gettando le basi per comprenderne la dimostrazione. Prima di passare alla dimostrazione generale del teorema, consideriamo il caso a = 4, p = 7 e vediamo come si associano alle classi di resto modulo 7 i numeri 1⋅4,2 ⋅4,3 ⋅4,4 ⋅4,5 ⋅4,6 ⋅4 .

a = 4 p = 7

1⋅4 2 ⋅4 3 ⋅4 4 ⋅4 5 ⋅4 6 ⋅4↓ ↓ ↓ ↓ ↓ ↓

4#$ %&7 1#$ %&7 5#$ %&7 2#$ %&7 6#$ %&7 3#$ %&7

.

Non di rado i risultati proposti dal grande matematico francese erano sprovvisti della dimostrazione, basti pensare al celeberrimo Ultimo teorema di Fermat. La dimostrazione proposta del (piccolo) teorema di Fermat è del 1808 ed è opera di Ivory5, successivamente ripresa da Dirichlet6 nel 1828. Dimostrazione. Si tratta di generalizzare il procedimento visto nell’esempio numerico appena visto. I numeri 1a,2a,3a,...,( p−1)a non sono divisibili per p. Infatti, non essendo a divisibile per p, dovrebbero esserlo gli interi 1,2,3,4,..., p−1, cosa chiaramente impossibile dal momento sono numeri minori del numero primo p. Inoltre, i numeri 1a,2a,3a,...,( p−1)a non sono nemmeno congruenti tra loro modulo p, sempre per quanto appena detto. Ne

5JamesIvory(1765-1842)matematicoeastronomoscozzese.6JohannPeterGustavLejeuneDirichlet(1805-1859)matematicotedesco.

30

consegue che i numeri 1a,2a,3a,...,( p−1)a sono congruenti ai numeri 1,2,3,4,..., p−1 in un determinato ordine (un resto, nella divisione per p, devono pur averlo!). Se moltiplichiamo i numeri 1a,2a,3a,...,( p−1)a tra loro e riscriviamo opportunamente il risultato otteniamo 1⋅2 ⋅ ...⋅ p−1( ) ⋅ a p−1. Sempre per la primalità di p, e per il fatto che p non

divide a, 1⋅2 ⋅ ...⋅ p−1( ) ⋅ a p−1 ≡ 1⋅2 ⋅ ...⋅ p−1( )mod p( ) da cui segue

a p−1 ≡1mod p( ) , come volevasi dimostrare. Forniamo, senza dimostrazione, il seguente teorema, utile per risolvere questioni legate alla divisibilità. Teorema (Wilson). Se p è un numero primo, allora il prodotto 1⋅2 ⋅ ....⋅ p−1( ) ≡ −1( )mod p( ) . Esempio. Si trovi un numero divisibile per 7 che dà sempre resto 1 se diviso per 2,3,4,5,6. I divisori suggeriscono di formare il prodotto 2 ⋅3 ⋅4 ⋅5 ⋅6 che, per il teorema di Wilson, è congruo a -1 modulo 7. Pertanto 7 2 ⋅3 ⋅4 ⋅5 ⋅6+1. Il numero cercato è evidentemente N = 2 ⋅3 ⋅4 ⋅5 ⋅6+1= 721. Esercizi

1. Si stabilisca se 3155 +2è divisibile per 7. 2. Un numero è divisibile per tre se la somma delle cifre è un multiplo

di tre. Giustificare quest’affermazione. 3. E’ dato il numero intero z = 3n5 = 3 ⋅102 + n ⋅101 +5 , con n appartenente all’insieme di cifre da 0 a 9. Determina i valori di n tali che z :

a) Sia divisibile per 3; b) Sia divisibile per 7; c) Sia divisibile per 5; d) Dia resto 1 nella divisione per 11; e) Dia resto 4 nella divisione per 13. 4. Determinare tutti i numeri che nella divisione per 4 danno resto 3,

nella divisione per 7 danno resto 2, nella divisione per 5 danno resto 4.

31

5. Determinare a quale numero compreso tra 0 e 4 è congruo modulo 5 il numero 11⋅18 ⋅2322 ⋅13⋅19 .

6. Teorema (Wilson). Se p è un numero primo, allora il prodotto 1⋅2 ⋅ ....⋅ p−1( ) ≡ −1( )mod p( ) . Si trovi un numero divisibile per 5 che dà come resto 1 se diviso per 2,3,4 .

7. Si trovi la classe di resto del numero 3155 +2 nella divisione per 5.

Soluzioni 1. Risulta MCD 3, 7( ) =1 . Poiché 7 è un numero primo, si può applicare il

teorema di Fermat: 36 ≡1mod7 . Ora, 155 = 25 ⋅6+5⇒ 3155#

$%&= 3

25⋅6 ⋅35#$

%&= 3

5#$

%&= 5#$ %&. Allora

3155 +2!"

#$= 5!" #$+ 2!" #$= 0!" #$. Il numero 3155 +2 è quindi divisibile per 7.

2. Si osserva che 10 ≡1mod3⇒ 10#$ %&= 1#$ %&⇒ 10n#$

%&= 10#$ %&

n= 1#$ %&

n= 1#$ %& , di

conseguenza un qualsiasi numero intero z = anan−1...a0 = an10

n + an−110n−1 + ...+ a0 , è tale che z!" #$= an + an−1 + ...a0!" #$ ,

come volevasi dimostrare.

3. a) Si applica il criterio di divisibilità per tre:

3+5+ n = 3k⇒ k = 3+mn =1+3m

⎧⎨⎩

⇒ n =1,4,7 . b) In questo caso si ricorre

alle proprietà 4 e 5 della congruenza: 3 ⋅102 + n ⋅101 +5⎡⎣

⎤⎦7= 3 ⋅2+ n ⋅3+5⎡⎣ ⎤⎦7 = 3n+11

⎡⎣ ⎤⎦7 = 3n+4⎡⎣ ⎤⎦7 , da cui

segue 3n+4 = 7k⇒ 7k −3n = 4⇒ k =1+3mn =1+7m

⎧⎨⎩

⇒ n =1,8 . c)

n = 0,1,2,3,4,5,6,7,8,9 . d) 3 ⋅102 + n ⋅101 +5⎡⎣

⎤⎦11= 3 ⋅1+ n ⋅ (−1)+5⎡⎣ ⎤⎦11 = 8− n

⎡⎣ ⎤⎦11 ≡ 1⎡⎣ ⎤⎦11⇒ n = 7. e)

3 ⋅102 + n ⋅101 +5⎡⎣

⎤⎦13= 3 ⋅9+ n ⋅10+5⎡⎣ ⎤⎦13 = 6+10n

⎡⎣ ⎤⎦13 ≡ 4⎡⎣ ⎤⎦13 ⇒ n = 5.

4.

32

N ≡ 3mod(4)N ≡ 2mod(7)N ≡ 4mod(5)

⎧

⎨⎪⎪

⎩⎪⎪

⇒N = 4x +3N = 7 y+2N = 5z+4

⎧

⎨⎪

⎩⎪

⇒4x +3= 7 y+27 y+2 = 5z+4

⎧⎨⎪

⎩⎪⇒

7 y−4x =1⇒ x = −2+7ny = −1+4n

⇒ N = 28n−5

7 y−5z = 2⇒ y = −4+5mz = −6+7m

⇒ N = 35m−26

⇒ 28n−5 = 35m−26

⎧

⎨

⎪⎪⎪

⎩

⎪⎪⎪

35m−28n = 21⇒ 5m−4n = 3⇒ m = 3+4hn = 3+5h

⇒ N = 35 3+4h( )−26 = 79+140h

5. 11⋅18 ⋅2322 ⋅13 ⋅19⎡⎣ ⎤⎦5 = 11⎡⎣ ⎤⎦5 18

⎡⎣ ⎤⎦5 2322⎡⎣ ⎤⎦5 13

⎡⎣ ⎤⎦5 19⎡⎣ ⎤⎦5 = 1

⎡⎣ ⎤⎦5 3⎡⎣ ⎤⎦5 2

⎡⎣ ⎤⎦5 3⎡⎣ ⎤⎦5 4

⎡⎣ ⎤⎦5 = 2⎡⎣ ⎤⎦5

6. Per il teorema di Wilson, se p = 5allora 2 ⋅3 ⋅4 ≡ −1mod 5( )⇒ 5 (2 ⋅3 ⋅4+1) . Ora, 2 ⋅3 ⋅4+1= 25è un numero divisibile per 5 ed è tale che 25−1= 2 ⋅12 = 3 ⋅8 = 4 ⋅6 , di conseguenza 25 ≡1mod 2( ) , 25 ≡1mod 3( ) , 25 ≡1mod 4( ) , come volevasi dimostrare.

7. Osserviamo la seguente corrispondenza tra le potenze di due e le classi di resto modulo

51 2 4 8 16 32 64 128 2561⎡⎣ ⎤⎦5 2⎡⎣ ⎤⎦5 −1⎡⎣ ⎤⎦5 −2⎡⎣ ⎤⎦5 1⎡⎣ ⎤⎦5 2⎡⎣ ⎤⎦5 −1⎡⎣ ⎤⎦5 −2⎡⎣ ⎤⎦5 1⎡⎣ ⎤⎦5

. Si nota

una ripetizione di “periodo 4” della sequenza 1⎡⎣ ⎤⎦5 , 2⎡⎣ ⎤⎦5 , −1

⎡⎣ ⎤⎦5 , −2⎡⎣ ⎤⎦5 : in

particolare le potenze del tipo 24n confluiscono tutte nella classe di resto 1⎡⎣ ⎤⎦5 . Ora, poiché 155 =156−1e 156 = 4 ⋅39 , allora 2155 ∈ −2⎡⎣ ⎤⎦5 . In definitiva, poiché

3⎡⎣ ⎤⎦5 = −2⎡⎣ ⎤⎦5 ⇒ 3155⎡⎣

⎤⎦5= −2( )

155⎡⎣⎢

⎤⎦⎥5= −1⎡⎣ ⎤⎦5 2

155⎡⎣

⎤⎦5= −1⎡⎣ ⎤⎦5 −2

⎡⎣ ⎤⎦5 = 2⎡⎣ ⎤⎦5 , e

quindi 3155 +2⎡⎣

⎤⎦5= 3155⎡⎣

⎤⎦5+ 2⎡⎣ ⎤⎦5 = 2

⎡⎣ ⎤⎦5 + 2⎡⎣ ⎤⎦5 = 4

⎡⎣ ⎤⎦5 = −1⎡⎣ ⎤⎦5 . Oppure,

33

applicando iterativamente il piccolo teorema di Fermat:

3155 = 35 ⋅ 330( )5≡ 35 ⋅330 = 35 ⋅ 36( )

5≡ 35 ⋅36 = 35 ⋅35 ⋅3≡ 3 ⋅3 ⋅3≡ 2mod(5)

. Di conseguenza 3155 +2⎡⎣

⎤⎦5= 2+2⎡⎣ ⎤⎦5 = 4

⎡⎣ ⎤⎦5 .

“Liceo Scien t i f i c o Statale “Guido Caste lnuovo”

COMPITO DI MATEMATICA Classe III sezione E

12/11/2015

Problema In uno strano paese circolano solo monete da 2€ e banconote da 5€, e ogni transazione ha per valore un numero intero N di euro.

a) Dimostra che ogni transazione del valore di N euro può essere eseguita scambiando x monete da 2€ e y banconote da 5€. (Si tratta di dimostrare che l’equazione 2x +5 y = N ammette soluzione ∀x, y ∈ Z …). Quale significato attribuiresti alle soluzioni negative dell’equazione 2x +5 y = N ? Considera il caso particolare 2x +5 y =13 .

b) Utilizza il “linguaggio” delle classi di resto per determinare il minimo importo positivo che, se pagato con monete da 2€ dà come resto 1€, e se pagato con banconote da 5€ dà come resto 3€.

c) Possediamo un numero x di monete inferiore a quello y di banconote e dobbiamo pagare un importo di 40€. In quanti modi è possibile pagare tale importo? Rappresentare l’ equazione risolvente e i vincoli mediante un diagramma cartesiano.

Quesiti 1. Si determini il valore delle costanti intere a,b tali che (x − a)(x − b)(x −6) = x3 −5x2 −8x +12 .

2. E’ dato il numero naturale di quattro cifre z =15x2 . Si determinino i possibili valori delle cifre delle decine tali che z ≡ 3mod(7) . E se il numero fosse stato z = yx2 , per quali valori delle cifre x e y sarebbe stato divisibile per 7?

3. Nelle ipotesi del teorema di Fermat (di cui si chiede l’enunciato) si trovino i possibili valori dell’intero a tali che i numeri 1a,2a,...,( p−1)a appartengano rispettivamente alle classi di resto

34

1⎡⎣ ⎤⎦p , 2⎡⎣ ⎤⎦p ,..., p−1

⎡⎣ ⎤⎦p (Si tratta di risolvere l’equazione

na = nmod( p) n =1,2,..., p−1 …).

CORREZIONE Problema In uno strano paese circolano solo monete da 2€ e banconote da 5€, e ogni transazione ha per valore un numero intero N di euro.

a) Dimostra che ogni transazione del valore di N euro può essere eseguita scambiando x monete da 2€ e y banconote da 5€. (Si tratta di dimostrare che l’equazione 2x +5 y = N ammette soluzione ∀x, y ∈ Z …).

Quale significato attribuiresti alle soluzioni negative dell’equazione 2x +5 y = N ? Considera il caso particolare 2x +5 y =13 .

• Poiché MCD 2,5( ) =1 N per ogni valore di N, l’equazione 2x +5 y = N ammette soluzione ∀x, y ∈ Z . Nel caso particolare

2x +5 y =13risulta in generale x = 4−5ny =1+2n

⎧⎨⎪

⎩⎪n ∈ Z . La soluzione

corrispondente a n =1 ad esempio, corrisponde al caso in cui l’importo di 13€ viene pagato con 3 monete da 5€, ricevendo come resto (x = −1) una moneta da 2€.

b) Utilizza il “linguaggio” delle classi di resto per determinare il minimo importo positivo che, se pagato con monete da 2€ dà come resto 1€, e se pagato con banconote da 5€ dà come resto 3€.

• Si tratta di una classica applicazione del teorema cinese del resto. Indicato con N il generico importo, si ha

N ≡1mod(2)N ≡ 3mod(5)

⇒N −1= 2xN −3= 5 y

⇒ 2x −5 y = 2⎧⎨⎪

⎩⎪

⎧⎨⎪

⎩⎪⇒ x = 6+5n

y = 2+2n⇒ N =13€

Poiché non esistono monete da 1€, il problema non ammette soluzione positiva, come richiesto.

c) Possediamo un numero x di monete inferiore a quello y di banconote e dobbiamo pagare un importo di 40€. In quanti modi è possibile pagare tale importo? Rappresentare l’equazione risolvente e i vincoli mediante un diagramma cartesiano.

35

• L’equazione risolvente e i vincoli si possono riassumere attraverso il

seguente sistema misto: 2x +5 y = 40x < y

x ≥ 0, y ≥ 0

⎧

⎨⎪⎪

⎩⎪⎪

. Si ha MCD 2,5( ) =140 ,

quindi x = 40−5ny = −8+2n

⎧⎨⎪

⎩⎪. Imponiamo quindi il rispetto dei vincoli

40−5n < −8+2n40−5n ≥ 0−8+2n ≥ 0

⎧

⎨⎪

⎩⎪

⇒

n > 487

n ≤ 8n ≥ 4

⎧

⎨

⎪⎪⎪

⎩

⎪⎪⎪

⇒ n = 7,n = 8⇒x = 5 y = 6x = 0 y = 8

.

Quesiti

1. Si determini il valore delle costanti intere a,b tali che (x − a)(x − b)(x −6) = x3 −5x2 −8x +12 .

• Si applica il Principio di identità dei polinomi dopo aver svolto i prodotti al membro di sinistra: x3 − a+ b+6( )x2 + ab+6a+6b( )x −6ab = x3 −5x2 −8x +12 , da cui segue il

sistema a+ b+6 = 5

ab+6a+6b = −8−6ab =12

⎧

⎨⎪

⎩⎪

⇒ a+ b = −1ab = −2

⇒a = −2,b =1a =1,b = −2

⎧⎨⎪

⎩⎪

⎧⎨⎪

⎩⎪.

2. E’ dato il numero naturale di quattro cifre z =15x2 . Si determinino i possibili valori delle cifre delle decine tali che

36

z ≡ 3mod(7) . E se il numero fosse stato z = yx2 , per quali valori delle cifre x e y sarebbe stato divisibile per 7?

• Nella divisibilità per 7 risulta 10⎡⎣ ⎤⎦7 = 3

⎡⎣ ⎤⎦7 ⇒ 102⎡⎣

⎤⎦7= 2⎡⎣ ⎤⎦7 ⇒ 103⎡

⎣⎤⎦7= −1⎡⎣ ⎤⎦7 ; in virtù delle proprietà della

congruenza risulta z⎡⎣ ⎤⎦7 = 1⋅10

3 +5 ⋅102 + x ⋅10+2⎡⎣

⎤⎦= −1+10+3x +2⎡⎣ ⎤⎦7 = 3x +4

⎡⎣ ⎤⎦7 ; di

conseguenza, z ≡ 3mod(7) se e solo se

3x +4−3= 7 y⇒ 7 y−3x =1⇒ 0 ≤ x = 2+7n ≤ 9y =1+3n

⇒ n = 0,1 . I numeri

interi richiesti sono quindi z =1522e z =1592 . Nel secondo caso risulta z⎡⎣ ⎤⎦7 = y ⋅102 + x ⋅10+2⎡

⎣⎤⎦= 2 y+3x +2⎡⎣ ⎤⎦7 ⇒ 2 y+3x +2 = 7k .

L’appartenenza di x e di y al gruppo di cifre 0,1,…,9 porta ad escludere valori negativi per l’intero k. Risolviamo quindi l’equazione

2x +3 y+2 = 7⇒ 2x +3 y = 5⇒ 0 ≤ x =1−3n ≤ 90 < y =1+2n ≤ 9

⇒ n = 0 . In

conclusione, il più piccolo numero della forma z = yx2è z =112 . Il vincolo di avere 2 come cifra delle unità porta a concludere che tutti i numeri della forma z = yx2divisibili per 7 sono z =112+70k , con k = 0,...,12 .

3. Nelle ipotesi del teorema di Fermat (di cui si chiede l’enunciato) si

trovino i possibili valori dell’intero a tali che i numeri 1a,2a,...,( p−1)a appartengano rispettivamente alle classi di resto 1⎡⎣ ⎤⎦p , 2

⎡⎣ ⎤⎦p ,..., p−1⎡⎣ ⎤⎦p (Si tratta di risolvere l’equazione

na = nmod( p) n =1,2,..., p−1 …).

• Teorema (Fermat): Se p è un numero primo e p /| a , allora a p−1 ≡1mod( p) . Seguendo il suggerimento, p (na − n) = n(a −1) . Poiché p è primo, non può dividere alcun numero intero minore di p, quindi deve dividere necessariamente a −1( ) . Di conseguenza, i possibili valori di a saranno quelli della forma a = kp+1, con k ∈ N .

37

Approfondimento: la divisibilità per tre, e il numero minimo di pesate con la bilancia a bracci uguali Vogliamo risolvere il seguente problema: qual è il numero minimo di masse campione necessario per misurare con una bilancia a bracci uguali una massa non superiore ai 1000g? Una risposta a questa domanda può essere data interpretando opportunamente i resti nella divisione per tre. Infatti, ogni numero nella divisione per tre può dare come resto 0, 1, 2. Ora, se osserviamo che −1= 2−3 , possiamo suddividere tutti i numeri interi nelle cosiddette classi di resto −1[ ], 0[ ], 1[ ] , ed esprimere così ogni numero tra 1 e 1000 in base 3. Quindi, ogni valore numerico di massa è ottenibile combinando opportunamente masse campione da 3n g , con 3n ≤1000 , ovvero n = 6 , dal momento che 37 = 2187 >1000 . La nostra pesiera “ideale” è dunque costituita da masse campione di 1,3, 9, 27,81, 243, 729{ }g . Qual è l’idea che sta alla base del ragionamento? La risposta ci viene suggerita dalla bilancia stessa, in quanto una volta posta la massa da misurare su uno dei due bracci, per esempio quello di sinistra, possiamo raggiungere l’equilibrio mettendo le masse campione sui due bracci. In questo modo “-1” rappresenta le masse che vengono poste sul braccio dove si trova la massa da misurare, e “1” quelle che vengono poste sull’altro braccio. Vediamo come funziona il tutto con un esempio. Se vogliamo misurare una massa da 378g dobbiamo procedere così: 243< 378< 729 e 378>1+3+ 9+ 27+81+ 243= 364 quindi metteremo la massa da 729g sull’altro piatto: 729−378 = 351. Il peso da 729g non possiamo più utilizzarlo. Si ha, anzi si deve necessariamente avere, 351<1+3+ 9+ 27+81+ 243= 364 , quindi 351− 243=108 , il peso da 243g viene messo sullo stesso piatto della massa da misurare. A questo punto 108 = 81+ 27 : siamo stati fortunati, poniamo le masse da 81g e da 27g sullo stesso piatto della massa da misurare ed il gioco è fatto. Riassumendo: 378 = 729−351351= 243+108108 = 81+ 27

"

#

$$$

⇒ 378 = 729− 243−81− 27⇒ 378+ 243+81+ 27 = 729 .

378243,81,27

729