NUMERI NATURALI E INTERI Flashcards
LA TERNA DI PEANO
Sia l’elemento 0∈ℕ, funzione succ: ℕ➝ℕ n⟼n+1
PA 1 ➛ succ. è funzione iniettiva:
n, m distinti ⇒ succ(n) ≠ succ(m) cioè n+1 ≠ m+1
PA 2 ➛ 0∉ Im(succ):
succ. non è funzione suriettiva, cioè ∄ alcun n t.c. 0 è il suo successore
PA 3 ➛ Principio di induzione:
∀A⊆ℕ se 0∈A e se n∈A allora n+1 ∈A ⟹ A = ℕ
La terna (PA1), (PA2), (PA3) caratterizza l'insieme ℕ. In particolare (PA 3) fornisce una tecnica di dimostrazione di enunciati che coinvolgono i numeri naturali.
PRINCIPIO DEL MINIMO
Sia A⊆ℕ, A ≠ Ø, allora A ammette un minimo rispetto alla relazione ≤.
DIMOSTRAZIONE: assumiamo falsa la tesi: A privo di minimo.
costruiamo B = {n∈ℕ : 0, 1, …, n ∉A}, possiamo dire su B
- 0∈B poiché se 0 appartenesse ad A sarebbe il minimo.
- se n∈B (per costruzione di B 0, 1, …, n ∉A) allora anche succ(n)∈B, perché se non appartenesse a B apparterrebbe ad A e quindi succ(n) [n+1] sarebbe il minimo in A.
⟹B = ℕ, ma allora A = Ø
↳ contraddizione perché per ipotesi A ≠ Ø
PRINCIPIO DI INDUZIONE COMPLETA
Sia A⊆ℕ, n∈ℕ;
ogni volta che dalla condizione {m∈ℕ : m < n} ⊆A si dimostra n∈A allora A = ℕ
DIMOSTRAZIONE: Assumiamo falsa la tesi: A ≠ ℕ ➝ ℕ - A =Ø
insieme complementare di ℕ
Per il principio del minimo ℕ - A ammette minimo min(ℕ - a) = n, deduco per definizione di complementare, che n∉A
Segue che m : m < n sono in A ma dalle condizioni del teorema se
{m : m < n}⊆A allora n∈A ⟹ contraddizione.
⟹ La tesi è vera.
DIVISIBILITÀ SU ℕ (definizione e proprietà)
La relazione di divisibilità | su ℕ, definita ∀a,b∈ℕ
a | b sse ∃q∈ℕ : b = qa è una relazione di ordine parziale.
Proprietà:
1. ∀b∈ℕ 1 | b ➝ ∃q∈ℕ : b = 1q ➝ q = b [1 = min ℕ]
b | b ➝ ∃q∈ℕ : b = bq ➝ q = 1 [ riflessiva di | ]
b | 0 ➝ ∃q∈ℕ : 0 = bq ➝ q = 0 [0 = maxℕ]
2. ∀a,a¹,b,r∈ℕ se b | a e b | a¹ allora
b | a + a¹
b | a - a¹ (a ≥ a¹)
b | r • a
3. ∀a,b∈ℕ, a ≠ b ≠ 0. Se b | a allora b ≤ a
TEOREMA (del quoziente e resto)
Siano a,b∈ℕ, b ≠ 0.
Allora esistono (e sono unici) q,r∈ℕ t.c. a = b • q + r r < b
q si dice quoziente della divisione di a per b
r si dice resto della divisione di a per b
DIMOSTRAZIONE: bisogna dimostrare l’esistenza di q ed r e la loro unicità
RAPPRESENTAZIONE DI UN NUMERO
ad esempio 1527 si scrive come 1•10³ + 5•10² + 2•10 + 7
applico il teorema del quoziente e resto: a = 1527, b = 10 (Base 10)
1527 = 152•10 + 7 ➝ 152 = q , 7 = r < 10
152 = 15•10 + 2
15 = 1•10 +5
1 = 0•10 + 1 mi fermo quando ottengo q = 0.
La sequenza dei resti, presi dal basso, rappresenta 1527.
allo stesso modo si rappresentano anche i numeri in altre basi utilizzando numeri adatti come resto ( ad es. in base 2 si usano 0 e 1 ).
LUNGHEZZA DI UN NUMERO
- in base 10: la lunghezza di un numero a in base 10, cioè il numero di cifre necessarie per rappresentare a è ⎣log₁₀a⎦+ 1
- in base 2: la lunghezza di un numero a in base 2, cioè il numero di cifre necessarie per rappresentare a è ⎣log₂a⎦+ 1
MASSIMO COMUN DIVISORE
Siano a,b∈ℕ, a ≠ 0 oppure b ≠ 0.
Si dice che d è il massimo comun divisori a e b, si indica con (a, b), se
- d | a e d | b
- e∈ℕ : e | a ed e | b allora e ≤ d
OSSERVAZIONI:
- c’è almeno un divisore comune di a e b ed è 1
- a ≠ 0, allora l’insieme dei divisori comuni di a e b è incluso nell’insieme dei numeri naturali n t.c. 1 ≤ n ≤ a. Tale insieme è finito, ammette un minimo elemento rispetto a ≤.
lo stesso vale per b ≠ 0
⟹ MCD ∃ ed è unico.
PROPRIETÀ DEL MCD
Siano a,b∈ℕ a ≠ 0 oppure b ≠ 0, allora:
- (a, b) = (b, a)
- assumiamo che a = 0, allora b ≠ 0 ➝ b | 0 e b | b
b è chiaramente il massimo tra i suoi divisori, (0, b) = b
[lo stesso vale anche per b = 0]
- se a,b ≠ 0 e se b | a allora (a, b) = b infatti b | a e b | b
TEOREMA (MCD)
Siano a,b∈ℕ, b ≠ 0
Siano q ed r il quoziente ed il resto della divisione di a per b. Allora:
(a, b) = (b, r) [r < b]
DIMOSTRAZIONE:
- dimostro che (a, b) ≥ (b, r) ➝ (b, r) ≤ (a, b)
per il Teo. del quoziente e resto, a = b • q + r con r < b
i divisori comuni di b per r dividono anche a (proprietà della divisibilità)
⟹ (b, r) ≤ (a, b)
- dimostro che (a, b) ≤ (b, r)
da a = b • q + r posso scrivere r = a - b • q
i divisori di a e b dividono anche r quindi (a, b) ≤ (b, r).
mettendo insieme i due risultati, per la proprietà antisimmetrica di ≤
⟹ (a, b) = (b, r)
ALGORITMO DI EUCLIDE (delle divisioni successive)
è un algoritmo per calcolare il MCD tre due numeri.
INPUT: a,b∈ℕ, a,b ≠ 0, a ≥ b
OUTPUT: (a, b)
PROCEDIMENTO: si esegue la prima divisione di a per b, con il teorema del quoziente e resto ➝ a = b•q₀ + r₀ con r₀ < b
- se r₀ = 0 allora si deduce che b | a e (a, b) = b, il procedimento si
arresta. ⟹ OUTPUT: b
- se r₀ ≠ 0 si prosegue effettuando una divisione tra b e r₀
➝ b = r₀•q + r₁ con r₁ < r₀
- se r₁ = 0 allora r₀ | b, (b, r₀) = r₀
si deduce quindi che (a, b) = (b, r₀) = r₀ ⟹ OUTPUT: r₀
- se r₁ ≠ 0 si prosegue effettuando una altre divisione
➝ r₀ = r₁•q + r₂ con r₂ < r₁.
osserviamo che il procedimento prima o poi si arresta perché se non si arrestasse avrei una successione decrescente infinita di naturali e quindi si determinerebbe un insieme di naturali privo di minimo ➝ impossibile.
⟹ sia S l’ultimo passo del procedimento dove si ottiene resto nullo: r = 0.
➝ r(s-2) = r(s-1)•q il MCD è l’ultimo resto non nullo.
r(s-1) | r(s-2)
⟹ (a, b) = (b, r₀) = (r₀, r₁) = … = (r(s-2), r(s-1)) = r(s-1) ➝ OUTPUT: r(s-1) = (a, b)
IDENTITÀ DI BÈZOUT
Siano a,b∈ℕ, non entrambi nulli, e sia d = (a, b)
Allora ∃ x, y∈ℤ t.c. d = a•x + b•y
DIMOSTRAZIONE:
- se a = 0 (o b = 0) la tesi è ovvia: d = b = a•o + b•1, x = 0, y = 1 ∈ℤ
- se a,b ≠ 0 si procede con la dimostrazione per induzione sui passi dell’algoritmo di Euclide:
Si verifica per S = 0 ➝ se S = 0 a = b•q + 0 r = 0
d = b = a•o + b•1 tesi verificata.
Sia S > 0. Assumiamo la tesi vera per S - 1. Si applica il Teo del quoziente e resto ➝ a = b•q₀ + r₀ r₀ < b
possiamo osservare ce la ricerca di (b, r₀) richiede al più S - 1 passi allora sfrutto l’ipotesi induttiva ➝ ∃ x,y ∈ℤ t.c. (b, r₀) = b•x₁ + r₀•y₁
⟹ d = (a, b) = (b, r₀) = b•x₁ + r₀•y₁ =
= b•x₁ + (a - b•q₀)•y₁ =
= b•x₁ + a•y₁ - b•q₀•y₁ =
= a•y₁ + b•(x₁ - q₀•y₁) =
∈ℤ ∈ℤ
COROLLARI DELL’IDENTITÀ DI BÈZOUT
- Siano a,b ∈ℕ e∈ℕ t.c. e | a ed e | b. Allora e | (a, b)
DIMOSTRAZIONE:
e | a ➝ a = e•p con p∈ℕ
e | b ➝ b = e•q con q∈ℕ
(a, b) = (I. B.) a•x + b•y (x,y∈ℕ) = e•px + e•qy = e•(px + qy) ⟹ e | (a, b) - Siano a,b,c ∈ℕ∖{0} t.c. a | b•c e (a, b) = 1. Allora a | c
DIMOSTRAZIONE:
a | b•c ➝ ∃q∈ℕ : bc = aq
(a, b) = 1, allora per I. B. ∃x,y∈ℕ : 1 = ax + by
c = c•1 = c • (ax + by) = acx + bcy = acx + aqy = a • (cx +qy)
↳∈ℕ ⟹ a | c
MINIIMO COMUNE MULTIPLO
Siano a,b∈ℕ a,b ≠ 0. Si dice che m è il minimo comune multiplo di a e b, si indica con [a, b], se m ≠ 0 e
- a | m e b | m
- n ≠ 0 t.c. a | n e b | n ⟹ m ≤ n
osservazione: se b | a allora [a, b] = a
NUMERI PRIMI
- Un numero naturale p > 1 si dice PRIMO se gli unici suoi divisori sono 1 e se stesso.
- Un numero naturale a > 1 si dice COMPOSTO se ammette altri divisori oltre a 1 e se stesso.
