Algebra e geometria - algoritmi sui numeri interi

+

N

NUMERI INTERI ℤ ℕ q , r

DIVISIONE per ogni a,b esistono ∈ ℤ

∈ℤ

tali che a = q * b + r con 0 <= r < b

q quoziente

r resto

ALGORITMO DELLE SOTTRAZIONI SUCCESSIVE

Es, a = 17 b = 3

17 – 3 = 14

14 – 3 = 11

11 – 3 = 8

8 – 3 = 5

5 – 3 = 2 < 3

17 = 3 * 5 + 2

DEF. a DIVIDE b a / b se b è un multiplo di a

oppure equivalentemente esiste c tale che b = a * c

Es. 2 divide 18 3 divide 15 7 non divide 15

DEF. Il Massimo Comune Divisore di a e b (MCD(a,b))

è un numero d tale che

d divide a, d divide b

• Se t divide a e t divide b

•

Es. MCD(14,16) = 2

MCD (16,20) = 4

ALGORITMO DELLE DIVISIONI SUCCESSIVE PER MCD

(EUCLIDEO)

a>b a = b * q1 + r1 se r1 = 0 allora b divide a

e MCD(a,b) = b

se r1> 0 b = r1 * q2 + r2

se r2> 0 r1 = r2 * q3 + r3 Si ripetono i passaggi fino ad ottenere rn = 0

MCD(a,b) = rn-1

Esempio MCD(14,16) 16,20

a = 16

b = 14 16 = 14 * 1 + 2

14 = 2 * 7 + 0

MCD(1218,132)

1218 = 132 – 9 + 30

132 = 30 * 4 + 12

30 = 12 * 2 + 6

12 = 6 * 2 + 0

6 = 30 – 12 * 2

d = 6

PROPRIETÀ

Se d = MCD(a,b)

d è una combinazione lineare di a e b, cioè esistono x,y ∈ ℤ

tali che d = a * x + b * y

12 = 132 – 30 * 4

30 = 1218 – 132 * 9

12 = 132 – (1218 – 132 * 9) * 4

= 132 – 1218 * 4 + 132 * 36

= 132 * 37 – 1218 * 4

6 = 30 – 12 * 2

= 1218 – 132 * 9 – (132 * 37 – 1218 * 4) * 2 =

= 1218 * 9 – 132 * (37 * 2 + 9) =

Es.

MCD (15,32)

32 = 15 * 2 + 2

15 = 2 * 7 +1

2 = 1 * 2 + 0

1 = 15 – 2 * 7

2 = 15 - 32 * 7 + 15 * 14 =

= 15 * 15 – 32 * 7

MCD (42,15)

42 = 15 * 2 + 12

15 = 12 * 1 + 3

12 = 3 * 4 + 0

L'ultimo resto non 0 è il massimo comune divisore

DEF. Se MCD(a,b) = 1 allora a e b si dicono COPRIMI (Primi tra loro)

Es. 3,5 sono coprimi 3,15 non sono coprimi

15,7 sono coprimi 10,8 non sono coprimi

15,32 sono coprimi 42,5 non sono coprimi

DEF.

Sia p>1

p è primo se qli

unici divisori di p

sono 1 e p

p > 1 primo se

se p divide ab

allora p divide a oppure divide b

Es.

2,3,5,7,11,13, 17, …...

Teorema fondamentale dell'aritmetica

Ogni numero intero (diverso da 0) e prodotto di numeri primi in modo unico ( a meno di

permutazioni dei fattori)

II forma del principio di induzione

Se P vale per n0

• Se Supponendo che P sia vera per tutti i numeri < n

•

Si dimostra che P è vera per m

Allo