Algebra e geometria - algoritmi sui numeri interi

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

Allora P è vera per ogni n>= n0

Dimostrazione del teorema

+

n∈ℕ Se n è primo allora il teorema vale banalmente

Se n non è primo allora ha dei divisori != 1, n

n = a * b a,b != 1

Applico passo si induzione

a < n supp che il teorema vale per a e b

b < n

a = p1 …... ps b = q1 ….... qt pi,q; sono numeri primi

n = p1.........ps * q1 ….... qt

Teorema

Esistono infiniti numeri primi

Dim PER ASSURDO supponiamo che l'insieme dei numeri

primi sia finito P= {p1,....,pn} TUTTI I NUMERI PRIMI