Appunti di Algebra

DEFINIZIONE:

, ∈ ℤ, (/),

Dati diremo che divide ovvero che è un divisore del

, ∈ ℤ = ⋅ .

dividendo se esiste un tale che

PROPRIETÀ:

1. Qualsiasi numero è divisore dello zero:

/0 ∀ ∈ ℤ 0 = ⋅ 0

infatti

2. Lo zero è unicamente divisore di sé stesso:

0/ ⇒ = 0 = 0 ⋅ = 0

Se infatti

3. Transitiva:

/ / ⇒ /

Se e infatti

/ ⇒ ∃ ∈ ℤ =

tale che

⏞

/ ⇒ ∃ ∈ ℤ = = =

tale che

/ ⇒ = ±

4. Se e infatti

/ ⇒ ∃ ∈ ℤ =

tale che

/ ⇒ ∃ ∈ ℤ =

tale che

= ⇒ = 1 ⇔ = = 1 ∨ = = −1 ⇒ = ±

5. Se un numero è divisore di più dividendi, sarà anche divisore della loro

combinazione lineare:

/ / ⇒ /( + )

e infatti

/ ⇒ ∃ ∈ ℤ =

tale che

/ ⇒ ∃ ∈ ℤ =

tale che

+ = + = ( + ) ⇒ /( + )

6. Divisori banali:

±1, ± ∀ ∈ ℤ

ovviamente dividono

23 5.1 Massimo comun divisore (MCD)

DEFINIZIONE:

, ∈ ℤ 0,

Dati che non siano entrambi uguali a dicesi massimo comun divisore di

e un numero intero tale che:

/ /, .

1. e ovvero è un divisore comune di e

′ ′ ′

/ / ⇒ /,

2. Se e ovvero se si considera un divisore comune di e

′,

non massimo questo sarà a sua volta divisore del massimo comun

.

divisore (, )

Il massimo comun divisore di due numeri interi si può indicare con

(, ).

oppure solamente con

PROPRIETÀ:

(, 0) =

1. (, , ) = ((, ), )

2. = ⋅ ⇒ (, ) =

3. Se

(, ) = (, )

4. (, ) = ( ⋅ , ⋅ )

5. ( ⋅ , ⋅ ) = ⋅ (, )

6.

PROPOSIZIONE:

, ∈ ℤ 0,

Siano che non siano entrambi uguali a allora esiste sicuramente un

(, ). ′

Inoltre, nel caso e siano entrambi massimi comun divisori per

(, ), = ±′.

una coppia allora sicuramente Per convenzione si assume come

quello positivo. 24

5.2 Identità di Bezout

(, ),

Sia il massimo comun divisore della coppia questo può essere riscritto

tramite l’identità di Bezout, ovvero nella forma:

= + , ∈ ℤ

0 0 0 0

Questo meccanismo sarà utile nell’ambito del metodo delle divisioni successive

(che vedremo poco più avanti).

ESEMPIO:

= 2, = 4 ⇒ (, ) = 2

(−3)

2 = 2 ⋅ + 4 ⋅ (2)

Analogamente:

(−1)

2 = 2 ⋅ + 4 ⋅ (1) ,

Questo prova che esistono varie combinazioni di che possono restituire il

0 0

.

valore (, )

5.3 Metodo delle divisioni successive per il calcolo del (, )

Il metodo delle divisioni successive è un metodo utile al calcolo del e

consiste nell’attuare una serie di divisioni in successione fino a quando il resto

(, )

dell’ultima divisione non sia 0. Il coinciderà con l’ultimo resto non

,

nullo ottenuto. Considerati positivi, il metodo viene applicato come segue:

= + 0 ≤ <

1 1

= + 0 ≤ <

1 2 2 2 1

= + 0 ≤ ≤

1 2 3 3 3 2

⋮

= + 0 ≤ ≤

+1 +2 +2 +2 +1

⋮

= + 0

−1 +1

= (, )

25 OSSERVAZIONE:

= + (, ) = (, ).

Sia , è dimostrato che

1 1 1

ESEMPIO:

(1547

⏟ , 560

⏟ )

1547 = 560 ⋅ 2 + 427

560 = 427 ⋅ 1 + 133

427 = 133 ⋅ 3 + 28

133 = 28 ⋅ 4 + 21

28 = 21 ⋅ 1 + 7

21 = 7 ⋅ 3 + 0

(1547, 560) = 7 7

Quindi poiché è l’ultimo resto non nullo ottenuto. Ora

scriviamo l’ tramite l’identità di Bezout:

(133

7 = 28 − 21 = 28 − − 28 ⋅ 4) = 28 ⋅ 5 − 133 =

(427 (−16)

= − 133 ⋅ 3) ⋅ 5 − 133 = 427 ⋅ 5 + 133 ⋅ =

(560 (−16) (−16)

= 427 ⋅ 5 + − 427) ⋅ = 427 ⋅ 21 + 560 ⋅ =

(1547 (−16)

= − 560 ⋅ 2) ⋅ 21 + 560 ⋅ = 1547

⏟ ⋅ 21

⏟ + 560

⏟ ⋅ (−58

⏟ )

0 0 26

5.4 Numeri primi

DEFINIZIONE:

, ∈ ℤ (, ) = 1.

Due numeri si dicono coprimi se

DEFINIZIONE:

∈ ℤ, ≠ 0, ±1 ±1 ±.

Un numero si dice primo se i suoi unici divisori sono e

PROPRIETÀ:

/ (, ) = 1 ⇒ /

1. Se e

/ / /.

2. Sia primo e allora o o

ESEMPIO:

10/(5 ⋅ 2) ⇒ 10/2 10/5

e

7/(14 ⋅ 2) ⇒ 7 ⇒ 7/14

è primo

27 5.5 Teorema fondamentale dell’aritmetica

TEOREMA:

∈ ℕ, > 1.

Sia Allora si può decomporre in prodotto di numeri primi. Tale

decomposizione è unica a meno dell’ordine dei numeri primi stessi:

= … = … ⇒ = = .

Se e per qualche e

1 2 1 2

PROPOSIZIONE:

Esistono infiniti numeri primi.

5.6 Numeri di Fermat

DEFINIZIONE: ∈ ℤ

Un numero di Fermat è un numero esprimibile come:

2

= 2 + 1

2 4

= 3, = 2 + 1 = 5, = 2 + 1 = 17 …

0 1 2

2

= 2 + 1 ∀.

Fermat avanzò la congettura che tali numeri fossero primi Tale

supposizione venne confutata da Eulero dimostrando che:

= 4294967297 = 641 ⋅ 6700417 quindi non è primo.

5

5.7 Numeri di Mersenne

DEFINIZIONE: ∈ ℤ

Un numero di Mersenne è un numero primo esprimibile come:

= 2 − 1 ≥ 2

2 3 4

= 2 − 1 = 3, = 2 − 1 = 7, = 2 − 1 = 15 …

2 3 4

⇔ = 2047

è primo è primo? No, infatti non è primo.

11

⇒

È vero però che se è primo è primo.

28

5.8 Minimo comune multiplo (mcm)

DEFINIZIONE:

, ∈ ℤ ≠ 0,

Siano entrambi dicesi minimo comune multiplo di e un numero

intero tale che:

.

1. è multiplo di e di

′ ⇒ ′ .

2. Se è un multiplo comune non minimo di e è multiplo di

PROPOSIZIONE:

, ∈ ℤ ≠ 0, (, ) = [, ].

Dati entrambi allora esiste sicuramente un

In particolare: | ⋅ |

[, ] = (, )

ESEMPIO:

(1547, 560) (1547, 560) = 7.

Abbiamo calcolato in precedenza

1547 ⋅ 560 866320

[1547,560] = = = 123760

7 7

29 6. Funzioni e calcolo combinatorio

DEFINIZIONE: : →

Come già anticipato in precedenza, è una legge che associa ad ogni

elemento del dominio A uno e un solo elemento del codominio B.

: →

Più specificatamente, in termini matematici, si dice funzione o

applicazione se:

∀ ∈ ∃ ∈ | = () ()) ∈ ×

(,

1. e

= () .

si dice immagine di ( , ( )) ( , ( )),

2. Dati due elementi con le corrispondenti immagini e

1 1 2 2

)

= ( = ( ).

se allora necessariamente

1 2 1 2

ESEMPIO (1):

: ℤ → ℕ è una funzione?

2

→ )

= ⇒ ( = ( )

Se 1 2 1 2

12 22

)

( = = = ( )

1 2

Quindi è una funzione. 30

ESEMPIO (2):

: ℤ → ℤ è una funzione?

→ 2

∉ ℤ, ∈ ℚ.

non è una funzione perché infatti In particolare:

2 2

⇒ ∈ℤ

Se fosse pari 2

⇒ ∈ℚ

Se fosse dispari 2

ESEMPIO (3):

: ℚ → ℤ è una funzione?

→

non è una funzione, infatti, ad esempio:

1

= → ( = 2

)

2 = 2,

Inoltre, supposto un è vero anche che:

1 ⋅ 2 2 2

= = = → = = 8

( )

2 ⋅ 2 4

Per definizione, poiché a un elemento del dominio è associato più di un elemento

del codominio, non può essere funzione.

OSSERVAZIONE:

|| ||

= =

Siano e rispettivamente le cardinalità del dominio A e del

: → = { , , … , }

codominio B, quante funzioni esistono? Sia e un

1 2

qualsiasi elemento di B:

: →

→

1

→

2

⋮

→

||

|| =

Il numero di funzioni esistenti è dato dalla formula:

31 ESEMPIO:

{1,

= 2} = {, }

|| ||

= 2 = 2 || 2

||

° = = 2 = 4

Tutte le possibili funzioni sono:

: → : →