Congruenze L’aritmetica dell’orologio Dipartimento di Informatica

(1)

Congruenze

L’aritmetica dell’orologio

Dipartimento di Informatica

Olimpiadi della Matematica

31 marzo 2006

Dipartimento di Informatica Congruenze

(2)

Divisione

Tutti sanno benissimo che se mettiamo

quarantaquattro gatti in fila per sei ne restano fuori due

Più in generale, supponiamo di dover dividere una certa quantità di cose fra più persone

(3)

Divisione

Tutti sanno benissimo che se mettiamo quarantaquattro gatti in fila per sei

ne restano fuori due

(4)

Divisione

Tutti sanno benissimo che se mettiamo quarantaquattro gatti in fila per sei ne restano fuori due

(5)

Divisione

Tutti sanno benissimo che se mettiamo quarantaquattro gatti in fila per sei ne restano fuori due

(6)

Divisione

I quaranta ladroni della famosa favola di Al`ı Bab`a si ritrovano nella loro caverna (“Apriti, Sesamo”) e si siedono per dividersi il bottino

Sono ladroni modernizzati e il bottino consiste in un sacco pieno di banconote da 100 Euro

Come fanno a dividersi in parti uguali il bottino senza dover contare tutte le banconote?

Fra l’altro, sono s`ı ladroni moderni, ma ignorano l’aritmetica e non sanno eseguire le divisioni con due cifre e la divisione va fatta in 41 parti, perch´e il capo conta per due

(7)

Divisione

I quaranta ladroni della famosa favola di Al`ı Bab`a si ritrovano nella loro caverna (“Apriti, Sesamo”) e si siedono per dividersi il bottino Sono ladroni modernizzati e il bottino consiste in un sacco pieno di banconote da 100 Euro

(8)

Divisione

(9)

Divisione

Fra l’altro, sono s`ı ladroni moderni,

ma ignorano l’aritmetica e non sanno eseguire le divisioni con due cifre e la divisione va fatta in 41 parti, perch´e il capo conta per due

(10)

Divisione

(11)

Divisione

Per sistemare la cosa dal punto di vista matematico, chiamiamoa il numero di cose da dividere eb il numero di persone tra cui eseguire la divisione

Naturalmenteb > 0, altrimenti non c’`e niente da fare Il metodo trovato prima ci permette di dire che esistono due numeriq e r tali che

a = bq + r r < b

Il quozienteq è la quantità che va a ciascuno, il restor è quanto rimane e non può essere diviso

(12)

Divisione

Naturalmenteb > 0, altrimenti non c’`e niente da fare

Il metodo trovato prima ci permette di dire che esistono due numeriq e r tali che

a = bq + r r < b

(13)

Divisione

a = bq + r r < b

(14)

Divisione

a = bq + r r < b

Il quozienteq `e la quantit`a che va a ciascuno,

il restor `e quanto rimane e non pu`o essere diviso

(15)

Divisione

a = bq + r r < b

(16)

Unicit`a del quoziente e del resto

Possiamo immaginare altri metodi per eseguire la divisione del bottino; chi ci dice che il quoziente e il resto siano invariabilmente gli stessi?

Lo dimostriamo

Il metodo A d`a il quoziente q e il resto r :

a = bq + r r < b

Il metodo B d`a il quoziente q⁰ e il resto r⁰:

a = bq⁰+ r⁰ r⁰ < b

Supponiamo, per assurdo, che i due resti siano diversi e che il metodo A dia il resto maggiore

r⁰ < r

(17)

Lo dimostriamo

a = bq + r r < b

a = bq⁰+ r⁰ r⁰ < b

r⁰ < r

(18)

Lo dimostriamo

a = bq + r r < b

a = bq⁰+ r⁰ r⁰ < b

r⁰ < r

(19)

Lo dimostriamo

a = bq + r r < b

a = bq⁰+ r⁰ r⁰ < b

r⁰ < r

(20)

Lo dimostriamo

a = bq + r r < b

a = bq⁰+ r⁰ r⁰ < b

r⁰ < r

(21)

Lo dimostriamo

a = bq + r r < b

a = bq⁰+ r⁰ r⁰ < b

r⁰ < r

(22)

Abbiamo, dalle ipotesi precedenti

a = bq + r = bq⁰+ r⁰ r⁰ < r < b

Possiamo scrivere allora

r − r⁰ = b(q⁰− q) > 0 Quindi q⁰− q > 0 e perci`o b(q⁰− q) ≥ b Ma r − r⁰ < r < b

!!!

Quindi deve esserer = r⁰

(23)

a = bq + r = bq⁰+ r⁰ r⁰ < r < b Possiamo scrivere allora

r − r⁰ = b(q⁰− q) > 0

Quindi q⁰− q > 0 e perci`o b(q⁰− q) ≥ b Ma r − r⁰ < r < b

!!!

(24)

r − r⁰ = b(q⁰− q) > 0 Quindi q⁰− q > 0 e perci`o b(q⁰− q) ≥ b

Ma r − r⁰ < r < b

!!!

(25)

r − r⁰ = b(q⁰− q) > 0 Quindi q⁰− q > 0 e perci`o b(q⁰− q) ≥ b Ma r − r⁰ < r

< b

!!!

(26)

!!!

(27)

!!!

(28)

Abbiamo allora dimostrato che il metodo A e il metodo B danno lo stesso resto

a = bq + r = bq⁰+ r Quindi possiamo scrivere

bq = bq⁰ e dunque, siccomeb > 0,

q = q⁰

Il metodo A e il metodo B danno lo stesso risultato di quoziente e resto

(29)

a = bq + r = bq⁰+ r

Quindi possiamo scrivere

q = q⁰

(30)

q = q⁰

(31)

q = q⁰

(32)

q = q⁰

(33)

Resto

Possiamo allora definire una nuova operazione:

a % b (a mod b)

`e il resto della divisione di a per b. Come per la divisione, c’`e la restrizione che b > 0.

Il risultato di a % b `e sempre un numero naturale minore di b. Come facciamo se vogliamo usare anche numeri interi negativi?

(34)

Resto

a % b (a mod b)

Il risultato di a % b `e sempre un numero naturale minore di b. Come facciamo se vogliamo usare anche numeri interi negativi?

(35)

Resto

a % b (a mod b)

Il risultato di a % b `e sempre un numero naturale minore di b.

Come facciamo se vogliamo usare anche numeri interi negativi?

(36)

Resto

a % b (a mod b)

Il risultato di a % b `e sempre un numero naturale minore di b.

Come facciamo se vogliamo usare anche numeri interi negativi?

(37)

Resto e numeri interi

Diremo cher `e il resto della divisione di aperb se a = bq + r

e 0 ≤ r < |b|

Come determiniamo r e q? Non come prima, se a o b sono negativi.

Facciamo prima il caso di b > 0 e a < 0: invece che sottrarre b pi`u e pi`u volte, sommiamo, fino a che troviamo il resto.

Se invece b < 0 e a `e qualunque, vediamo subito da che parte andare e sommiamo o sottraiamo.

La stessa dimostrazione di prima fa vedere che resto e quoziente sono unici.

(38)

Diremo cher `e il resto della divisione di aperb se a = bq + r e 0 ≤ r < |b|

(39)

Come determiniamo r e q?

Non come prima, se a o b sono negativi.

(40)

(41)

(42)

(43)

(44)

Resto e numeri interi — Esempi

Dividiamo −44 per 6:

−44 + 6 = −38 −38 + 6 = −32 −32 + 6 = −26

−26 + 6 = −20 −20 + 6 = −14 −14 + 6 = −8

−8 + 6 = −2 −2 + 6 =4 Dividiamo −44 per −15:

−44 − (−15) = −29 −29 − (−15) = −14

−14 − (−15) =1 Dividiamo 44 per −13:

44 + (−13) = 31 31 + (−13) = 18 18 + (−13) =5 Qual `e la regola pratica?

(45)

−44 + 6 = −38

−38 + 6 = −32 −32 + 6 = −26

−26 + 6 = −20 −20 + 6 = −14 −14 + 6 = −8

−8 + 6 = −2 −2 + 6 =4 Dividiamo −44 per −15:

−44 − (−15) = −29 −29 − (−15) = −14

−14 − (−15) =1 Dividiamo 44 per −13:

(46)

−44 + 6 = −38 −38 + 6 = −32

−32 + 6 = −26

−26 + 6 = −20 −20 + 6 = −14 −14 + 6 = −8

−8 + 6 = −2 −2 + 6 =4 Dividiamo −44 per −15:

−44 − (−15) = −29 −29 − (−15) = −14

−14 − (−15) =1 Dividiamo 44 per −13:

(47)

−44 + 6 = −38 −38 + 6 = −32 −32 + 6 = −26

−26 + 6 = −20 −20 + 6 = −14 −14 + 6 = −8

−8 + 6 = −2 −2 + 6 =4 Dividiamo −44 per −15:

−44 − (−15) = −29 −29 − (−15) = −14

−14 − (−15) =1 Dividiamo 44 per −13:

(48)

−44 + 6 = −38 −38 + 6 = −32 −32 + 6 = −26

−26 + 6 = −20

−20 + 6 = −14 −14 + 6 = −8

−8 + 6 = −2 −2 + 6 =4 Dividiamo −44 per −15:

−44 − (−15) = −29 −29 − (−15) = −14

−14 − (−15) =1 Dividiamo 44 per −13:

(49)

−44 + 6 = −38 −38 + 6 = −32 −32 + 6 = −26

−26 + 6 = −20 −20 + 6 = −14

−14 + 6 = −8

−8 + 6 = −2 −2 + 6 =4 Dividiamo −44 per −15:

−44 − (−15) = −29 −29 − (−15) = −14

−14 − (−15) =1 Dividiamo 44 per −13:

(50)

−44 + 6 = −38 −38 + 6 = −32 −32 + 6 = −26

−26 + 6 = −20 −20 + 6 = −14 −14 + 6 = −8

−8 + 6 = −2 −2 + 6 =4 Dividiamo −44 per −15:

−44 − (−15) = −29 −29 − (−15) = −14

−14 − (−15) =1 Dividiamo 44 per −13:

(51)

−44 + 6 = −38 −38 + 6 = −32 −32 + 6 = −26

−26 + 6 = −20 −20 + 6 = −14 −14 + 6 = −8

−8 + 6 = −2

−2 + 6 =4 Dividiamo −44 per −15:

−44 − (−15) = −29 −29 − (−15) = −14

−14 − (−15) =1 Dividiamo 44 per −13:

(52)

−44 + 6 = −38 −38 + 6 = −32 −32 + 6 = −26

−26 + 6 = −20 −20 + 6 = −14 −14 + 6 = −8

−8 + 6 = −2 −2 + 6 =4

Dividiamo −44 per −15:

−44 − (−15) = −29 −29 − (−15) = −14

−14 − (−15) =1 Dividiamo 44 per −13:

(53)

−44 + 6 = −38 −38 + 6 = −32 −32 + 6 = −26

−26 + 6 = −20 −20 + 6 = −14 −14 + 6 = −8

−8 + 6 = −2 −2 + 6 =4 Dividiamo −44 per −15:

−44 − (−15) = −29 −29 − (−15) = −14

−14 − (−15) =1 Dividiamo 44 per −13:

(54)

−44 + 6 = −38 −38 + 6 = −32 −32 + 6 = −26

−26 + 6 = −20 −20 + 6 = −14 −14 + 6 = −8

−8 + 6 = −2 −2 + 6 =4 Dividiamo −44 per −15:

−44 − (−15) = −29

−29 − (−15) = −14

−14 − (−15) =1 Dividiamo 44 per −13:

(55)

−44 + 6 = −38 −38 + 6 = −32 −32 + 6 = −26

−26 + 6 = −20 −20 + 6 = −14 −14 + 6 = −8

−8 + 6 = −2 −2 + 6 =4 Dividiamo −44 per −15:

−44 − (−15) = −29 −29 − (−15) = −14

−14 − (−15) =1 Dividiamo 44 per −13:

(56)

−44 + 6 = −38 −38 + 6 = −32 −32 + 6 = −26

−26 + 6 = −20 −20 + 6 = −14 −14 + 6 = −8

−8 + 6 = −2 −2 + 6 =4 Dividiamo −44 per −15:

−44 − (−15) = −29 −29 − (−15) = −14

−14 − (−15) =1

Dividiamo 44 per −13:

(57)

−44 + 6 = −38 −38 + 6 = −32 −32 + 6 = −26

−26 + 6 = −20 −20 + 6 = −14 −14 + 6 = −8

−8 + 6 = −2 −2 + 6 =4 Dividiamo −44 per −15:

−44 − (−15) = −29 −29 − (−15) = −14

−14 − (−15) =1 Dividiamo 44 per −13:

(58)

−44 + 6 = −38 −38 + 6 = −32 −32 + 6 = −26

−26 + 6 = −20 −20 + 6 = −14 −14 + 6 = −8

−8 + 6 = −2 −2 + 6 =4 Dividiamo −44 per −15:

−44 − (−15) = −29 −29 − (−15) = −14

−14 − (−15) =1 Dividiamo 44 per −13:

44 + (−13) = 31

31 + (−13) = 18 18 + (−13) =5 Qual `e la regola pratica?

(59)

−44 + 6 = −38 −38 + 6 = −32 −32 + 6 = −26

−26 + 6 = −20 −20 + 6 = −14 −14 + 6 = −8

−8 + 6 = −2 −2 + 6 =4 Dividiamo −44 per −15:

−44 − (−15) = −29 −29 − (−15) = −14

−14 − (−15) =1 Dividiamo 44 per −13:

44 + (−13) = 31 31 + (−13) = 18

18 + (−13) =5 Qual `e la regola pratica?

(60)

−44 + 6 = −38 −38 + 6 = −32 −32 + 6 = −26

−26 + 6 = −20 −20 + 6 = −14 −14 + 6 = −8

−8 + 6 = −2 −2 + 6 =4 Dividiamo −44 per −15:

−44 − (−15) = −29 −29 − (−15) = −14

−14 − (−15) =1 Dividiamo 44 per −13:

(61)

Divisione nella realt`a di tutti i giorni

Che cos’hanno in comune tutti i luned`ı? Che cos’hanno in comune tutti i mezzogiorno? Se passano 72 ore da adesso, che ore saranno?

Non teniamo conto della riforma del calendario e basiamoci sull’usanza moderna di contare i giorni della settimana a partire dal luned`ı.

Assumiamo che il giorno 1 gennaio dell’anno 1 sia stato di luned`ı e numeriamo tutti i giorni.

Che cos’hanno in comune tutti i luned`ı?

Che il numero del giorno diviso per 7 d`a resto 1

(62)

Che cos’hanno in comune tutti i mezzogiorno?

Se passano 72 ore da adesso, che ore saranno?

(63)

(64)

(65)

(66)

(67)

Congruenze

Fissiamo un intero n > 0

Diciamo che gli interi a e b sonocongruenti modulo nse a % n = b % n

cio`e se la divisione di a e b per n d`a lo stesso resto Scriveremo, in questo caso

a ≡ b (mod n) oppure

a ≡nb

(68)

Congruenze

Diciamo che gli interi a e b sonocongruenti modulo n se a % n = b % n

cio`e se la divisione di a e b per n d`a lo stesso resto

Scriveremo, in questo caso

a ≡nb

(69)

Congruenze

Diciamo che gli interi a e b sonocongruenti modulo n se a % n = b % n

cio`e se la divisione di a e b per n d`a lo stesso resto Scriveremo, in questo caso

a ≡nb

(70)

Congruenze

C’`e un altro modo di esprimere la relazione a ≡ b (mod n)?

Prendiamo due numeri a e b tali che a ≡ b (mod n) Allora a = nx + r e b = ny + r , quindi

a − b = (nx + r ) − (ny + r ) = nx + r − ny − r = n(x − y ) cio`e a − b `e un multiplo di n

(71)

Congruenze

Prendiamo due numeri a e b tali che a ≡ b (mod n)

Allora a = nx + r e b = ny + r , quindi

(72)

Congruenze

(73)

Congruenze

a − b = (nx + r ) − (ny + r ) =

nx + r − ny − r = n(x − y ) cio`e a − b `e un multiplo di n

(74)

Congruenze

a − b = (nx + r ) − (ny + r ) = nx + r − ny − r =

n(x − y ) cio`e a − b `e un multiplo di n

(75)

Congruenze

a − b = (nx + r ) − (ny + r ) = nx + r − ny − r = n(x − y )

cio`e a − b `e un multiplo di n

(76)

Congruenze

(77)

Congruenze

Supponiamo adesso che a − b sia un multiplo di n:

a − b = nk che si pu`o scrivere anche a = nk + b

Possiamo eseguire la divisione di b per n: b = nq + r Ma allora

a = nk + b = nk + nq + r = n(k + q) + r e quindi

r = b % n = a % n cio`e

a ≡ b (mod n)

(78)

Congruenze

a − b = nk che si pu`o scrivere anche a = nk + b Possiamo eseguire la divisione di b per n:

b = nq + r

Ma allora

r = b % n = a % n cio`e

a ≡ b (mod n)

(79)

Congruenze

b = nq + r Ma allora

a = nk + b =

nk + nq + r = n(k + q) + r e quindi

r = b % n = a % n cio`e

a ≡ b (mod n)

(80)

Congruenze

a = nk + b = nk + nq + r =

n(k + q) + r e quindi

r = b % n = a % n cio`e

a ≡ b (mod n)

(81)

Congruenze

r = b % n = a % n cio`e

a ≡ b (mod n)

(82)

Congruenze

r = b % n =

a % n cio`e

a ≡ b (mod n)

(83)

Congruenze

r = b % n = a % n cio`e

a ≡ b (mod n)

(84)

Congruenze e operazioni

Supponiamo chea ≡ b (mod n)e che c ≡ d (mod n)

Alloraa − b = nx ec − d = ny; dunque (a − b) + (c − d ) = nx + ny che si pu`o scrivere anche

(a + c) − (b + d ) = n(x + y )

a ≡ b (mod n) c ≡ d (mod n) (a + c) ≡ (b + d ) (mod n)

Le congruenze possono essere sommate come le uguaglianze

(85)

Supponiamo chea ≡ b (mod n)e che c ≡ d (mod n) Alloraa − b = nx ec − d = ny; dunque

(a − b) + (c − d ) = nx + ny che si pu`o scrivere anche

(a + c) − (b + d ) = n(x + y )

(86)

(a − b) + (c − d ) = nx + ny

che si pu`o scrivere anche

(a + c) − (b + d ) = n(x + y )

(87)

(a + c) − (b + d ) = n(x + y )

(88)

(a + c) − (b + d ) = n(x + y )

(89)

(a + c) − (b + d ) = n(x + y )

(90)

Supponiamo di nuovo chea ≡ b (mod n) e chec ≡ d (mod n)

Possiamo moltiplicare le congruenze come le uguaglianze? Cio`e, `e vero che ac ≡ bd (mod n)?

44 ≡ 2 (mod 6) 28 ≡ 4 (mod 6) 44 · 28 = 1232 1232 = 205 · 6 + 2 2 · 4 = 8 8 = 1 · 6 + 2

Quindi 44 · 28 ≡ 2 · 4 (mod 6)

`E un caso? NO