Corso Algebra I

Teorema della divisione (o di Euclide)

b = a + r

Considero insieme S={m ∈ ℕ | am ≤ b}

max S = ⇒ b = a + r

Se è limitato superiormente infatti m ∈ ℕ ∃ am ≤ b ⇒ dovete maxb - am ≥ 0 per ipotesi

b - a = r b - a ≥ 0 >

1 > 0 ⇔ è assurdoq = max S ⇒ OK.

Identità di Bezout

∃d = MCD(a, b) = ∃x, y ∈ ℤ t.c d = ax + bya, b ∈ ℕ

Considero l'algoritmo di Euclide

r₀ = -q₀a + r₀ = x₀a + y₀b

xi a + yi b = qj(axj + byj) + rj _i-1 ⇒ r₂ = a(x₀ - x₁q₁ ) + b(y₀ - q₁y₁)

xm a + ym b = qm(ax_m-1 + by_m-1) + rm ⇒ rm = a(x_m-2 - q_m-1x_m-1)+ b(y_m-2 - q_m-1y_m-1)

Non è detto che la coppia(x,y) sia unica!

DEFINIZIONE MCD

∀a, b ∈ ℕ ∃ d ∈ ℕ, d = MCD(a,b) t.c.

1. d|a ∧ d|b
2. se d'|a ∧ d'|b ⇒ d'|d

ALGORITMO DI EUCLIDE

b = q₀a + r₀

a = q₁r₀ + r₁

r₀ = q₂r₁ + r₂

rᵢ₋₂ = qᵢrᵢ₋₁ + rᵢ

... rₘ₊₁ = 0

⇒ rₘ = MCD(a,b)

DIM.

PROPRIETÀ 1)

rₘ₋₁ = qₘrₘ

rₘ₋₂ = qₘ₋₁(rₘ₋₁) + rₘ = rₘ(a₁ + qₘqₘ-₁) → Sₘ

r₀ = q₁(rₘS₂) + rₘS₃ = rₘ(S₃ + q₁S₂)

a = q₀(rₘS₁) + rₘS₂ - rₘ(S₂ + a₁S₁) = S₀ = rₘS₀

b = q(rₘS₀) + rₘS₁ = rₘ(S₀ + S₁) = rₘS

⇒ rₘ | a ∧ rₘ | b OK

PROPRIETÀ 2) costruzione dell’ m.t.c. d|a ∧ d|b ⇒ a = dx ∧ b = dβ

bβ = q.a α + r₀ =r₀ = d(β - qα) = β₀

dx = q.dβ + r₁ = r₁ = d(α - qα₁) = β₁

r₀ = q.d(r₁) + r₂ = r₂ = d(β₀ - q₁β₁) = β₂

dᵢ = qᵢ₋₂dₙₘ₋₁dᵢₘ₋₁ + rₘ = rₘ = d(rₘ₋₂ - qₘ₋₁rₘ₋₁)

⇒ d|rₘ OK

TEOREMA (DI EUCLIDE)

ESISTONO INFINITI NUMERI PRIMI

DIM

# I NUMERI PRIMI SONO FINITI

P = {P₁, P₂, ..., P_N}

Q = P₁·P₂· ... ·P_N + 1

QUINDI Q NON È PARI

PROVO

CONSIDERO P_i UN DIVISORE DI Q PER CUI Q = x · P_i CON x ∈ ℕ

P₁·P₂· ... ·P_i·P_i+1· ... ·P_N + 1 = x · P_i

1 = P_i(X - P₁·P₂· ... ·P_i-1·P_i+1· ... ·P_N)

=>

P_i È L'INVERSO DI 1

OK.

PROP (1)

√2 NON È RAZIONALE

DIM

# √2 È RAZIONALE =>

√2 = P/q

CON P, q ∈ ℤ

1 =

(p² / q²) =>

p² = 2q²

1. 2 =

   (p² / q²) =>

   L'ESPONENTE DI 2 NELLA FATTORIZZAZIONE IN PRIMI DI q² È PARI, MENTRE IN p² è DISPARI, NECESSARIAMENTE, MA CIÒ È ASSURDO

2. SE P È DISPARI

   P = 2k + 1 =>

   P²(2k + 1)² = 4k² + 4k + 1 = 2q

   UK² + 4k + 1 = 2q

3. SE P È PARI

   P = 2k =>

   P² = 4k²

   3(2k² − 2q)

   =>

   q² = 2q² = 9q = PARI

dim

a ≡ b (mod m) ⇒ a ≡ b (mod d)

dim ⇒ m = c₂d

a ≡ b (mod m) ⇒ a - b = z₁ ∈ ℤ ⇒ a - b = z₂ c ∈ ℤ

a - b = z ⋅ c ∈ ℤ ⇒ d | a - b ⇒ a ≡ b (mod d) ok

a.c.p.c. (m, m) = 1

a ≡ b (mod m ⋅ m)

a ≡ b (mod m) ∧ a ≡ b (mod n)

a ≡ b (mod m ⋅ m) ⇒ a ≡ b (mod m)a ≡ b (mod m)

ok

a ≡ b (mod m) e a ≡ b (mod m) ⇒ m| a-b ∧ m | a-b

⇒ m ⋅ m | a-b ⇒ a ≡ b (mod m ⋅ m)

m o m (m) = ?

Convergenze (LINEARI mod m)

a.x ≡ b (mod m) ha soluzione ⇔ m.c.d. (a, m) = d | b

∃x ∈ ℤ t.c. a.x ≡ b (mod m)

d = m.c.d. (a, m) ⇒ a = d.α ∧ m = d.µ

d.α x ≡ b (mod d) µ ⇔ d.α x - b = d.µ t ⇒

b = d.α x - d.µ t ⇒ b = d (α x - µ t) ⇒ d | b ok

m.c.d a, m = d ⇒ a = d.α ∧ m = d.µ ∧ b = d.β

d = α t + m n µ β ⇒ b = α β + m µ β ⇔ b ≡ bl (mod m) = a (t β) (mod m) o esaur

t⍴ : x ⇒ a (t⍴) ≡ b (mod m) ⇒ a x ≡ b (mod m) t⍴' una soluzione

ok

Conclusione

Se p(x) = a_mx^m + ... + a₀, m ≥ 1 a coeff. reali con m = 2k+1 per un opportuno k

⇒ ∃ x ∈ R t.c. p(x) = 0

Se a_m > 0 ⇒ lim p(x) = lim a_m(x²)^k, x = ∞ → x = −∞

Se a_m < 0 ⇒ lim p(x) = lim a_m(x²)^k, x = ∞ → x = −∞

∀ a_m ∈ R, C = ] − ∞ ∞ [ = R polinomio p(x) ∈ C(R)

Ogni polinomio assume tutti i valori compresi tra gli estremi del dominio ⇒ ∃ x_i ∈ R t.c. p(x_i) = 0

NB: ƒ: [a,b] → R continua

ƒ(a) ≤ y₀ ≤ ƒ(b) ⇒ ∃ x₀ t.c. ƒ(x₀) = y₀

TEOREMA DI EULERO

MCD (a,m) = 1 ⇒ a^ϕ(m) ≡ 1 (mod m)

X = {x ∈ [0,m−1] | MCD (x,m) = 1} ∀ x ∈ X

#x ∈ X ⇒ MCD (x,m) = 1 ⇒ ∃ p : β . q (x) = p (β q (x) + α x) ⇒ p | α x ⇒

⇒p x | X ∧ MCD(a,m) = 1 e MCD (x,m) = 1 #

⇒(p)^(e) x ∈ X

OSSERVAZIONE

x,y ∈ X con x+y ⇒ π (x) + π (y) con π(x) π(y)∈ X

α x ≡ π (x) (mod m) # π (x)≡π (y) ⇒ α x ≡ α y (mod m) ⇒

α y ≡ π (y) (mod m) ⇒ x = y (mod m) ⇒ x = y #

MCD (a,m) = 1

⇒X = {x ∈ 0,m−1| ∀n ∈ MCD (x,m)=1} − {x|π(t), x ∈ X}

• ∏ x∈X = ∏ μ (x) = ∏ x (mod m) ⇒ a ∏ x = ∏(x (mod m)

a^ϕ(m))

• MCD (m,x) = 1; ∀x ∈ X

OK

SOLUZIONE DI UN SISTEMA LINEARE

• x ≡ a (mod m)
• x ≡ 0 (mod m) MCD (m,m)=1
• x ≡ a.m^{ϕ(m) + b m} (mod m: m)

INFATTI

a^0ϕ(m) + b^0ϕ(m) (mod m) ≡ a (mod m) OK

a^mϕ(m) + b^lϕ(m) (mod m) ≡ b (mod m) OK

0 1 (TEO. DI EULERO)

OSS

|A|=m e |B|=m

• # delle applicazioni f: A → B è m^m
• l'insieme di tutte queste applicazioni si denota con B^A
• # delle applicazioni f: A → B iniettive è n(n-1)...(n-m+1) (iniezioni)
• # delle applicazioni f: A → B biettive è n! (permutazioni)

PROP

|A| = |B| ⇒ f è biettiva

f è iniettiva

DIM

f: A → B t.c. ∀a_i∈A f(a_i) =b_i iniettiva

|B|= |A| = m A = {a₁,...,a_m} B = {b₁, ..., b_m}

f(A) = {b₁, ..., b_m}⊆B ⇒ f è suriettiva ⇒ f è biettiva ok

PROP

|A| = |B| ⇒ f è biettiva

f è suriettiva

DIM

f: A → B ∀b_i∈B ∃a_i∈A t.c. f(a_i)=b_i suriettiva

B = {b₁,...,b_m} = {f(a₁),..., f(a_m)} ⇒ f(a_j) ⇒ {a₁,...,a_m}⊆ A

⇒ f è iniettiva ⇒ f è biettiva ok

PROP

• f: A → B iniettiva ①
• g: B → C suriettiva ②
• g ∘ f: B → C biettiva ③

⇒ g ∘ f: A = C

ok iniettiva (1)

ok suriettiva (2)

biettiva (3)

DIM

∀a_i∈A con a≠a'_i ⇒ g(a) ≠ g(a') con f(a) f(a')∈B

(poiché f è iniettiva)

⇒ g(f(a)) ≠ g(f(a'))

(poiché g è iniettiva) ok

∀c ∈ C ⇒ ∃b ∈ B: t.c. g(b) = c ∀ b ∈ B ⇒ ∃a ∈ A t.c. f(a) = b

g(f(a)) = c ∀c ∈ C ok.