Principali teoremi Aritmetica, Algebra

1) Assioma del Buon Ordinamento:

Ogni insieme non vuoto di numeri naturali ammette un minimo

∀S ∈ ℕ, S ≠ Ø ∃ m ∈ S t.c. m ≤ s ∀ s ∈ S

2) Principio di induzione I forma

Sia P(m) una proprietà definita ∀ n ≥ n₀, (n₀ ∈ ℤ )

Hp) a) P(n₀) vera

b) (Passo induttivo) ∀ n ≥ n₀, se P(n) è vera → P(n+1) è vera

Dim) P è vera ∀ n ≥ n₀

Dim. Induzione | Hp) S = {n≥n₀ | P(m) è falsa?}

Se S ≠ Ø

⇒ per assurdo S ≠ Ø ⇒ per il principio del minimo ∃ m₀ ∈ S minimo

⇒ per Hp (P(m₀) è falsa. m₀ > n₀, (per Ipotesi a)

⇒ m₀-1 ≥ n₀ , ma m₀-1 ∉ S

⇒ P(m₀-1) è vera

⇒ per ipotesi b (P(m₀-1) vera ⇒ P(m₀) vera

Assurdo → S = Ø

3) Principio di induzione II forma

Sia P(m) una proprietà definita ∀ n ≥ n₀, (n₀ ∈ ℤ )

Hp) a) P(n₀) vera

b) ∀ n ≥ n₀, P(k) è vera ∀ n₀ ≤ k ≤ n ⇒ P(m) è vera

Th) P(n) è vera ∀ n≥n₀

4) Def 2 insiemi sono equipotenti, cioé hanno la stessa cardinalità

a ↔ b tra loro c. biunivoca

A ↔ B equipotenti ↔ #A=#B=n

dim: A,B,f,i,j=1,...n

_fB f biiettiva A

a_i=b_i

g= f^-1 se f^-1 biiettiva ⇒ f^-1 biiettiva

dim) A α_β B ⇔ f^-1 biiettiva....

5) #{f: f:x → {0,1}ⁿ = 2^k

dim: passo base; se k = 0 ⇒ P(x) | ∅ = ∅ ⇒ # P(x) = ز=1 ok

passo ind. suppuiamo o vera la tesi per k e lo dimostro per k+1

#X=k+1

∀A⊆X x₀∉A⇒A⊆X\ A₁⊆A^A∪{x₀}

f A|A ⊆ X¹ | f A|A ⊆ X¹ | ∪ | f x₀∪ A|¹ A⊆ X¹

⇒ # P(xn) = # P(xi) + # P(xi') → P(xi') + P(xi') = 2^k+2=2^k+1

Def: #{A ⊆ Y | #A = m}:= (m _i ) = #n - uple di el di arbitrary di Y

# n - uple distinto che danno lo

stesso insieme

Teorema di divisione Euclidea

1. Dati a, b ∈ ℤ | b ≠ 0 → ∃! q, r ∈ ℤ t.c. a = qb + r

o ≤ r < b

• Dim. esistenza: b > 0
• X = {r | r = a-kb, k ∈ ℤ, r ∩ ℕ}
• X ⊆ ℕ X ≠ ∅ perché r = a+|a|b > 0
• Allora r₀ il minimo di X (ABO) ∃ q ∈ ℤ t.c. r₀ = a-qb
• Da che o ≤ r₀ < b fatti e xe
• e fosse r₁ = r₀ - 1 ex m in ec. - dovre -
• r₀ -|b| 0 → a - qb - |b| = q - q'b
• b > 0 q, r ∈ ℤ t.c. a = q(b+1)+r
• o < r < b1
• a = q(b+1) + r o < r < b1
• a - q(b+1) = a - q'(b)+r...

dim. Unicità: q₁, q₂ r₁, r₂ ∈ ℤ t.c. a = q₁b+r₁

a - q₂b+r₂

or₁ |b| or₂ < |b|

se r + r = r₂ => q₁ = q₂

se r₁ ≠ r₂ or b₁ > b₂ r₂ - r₁ = (q₁ - q₂)b=1q

Def. a, b∈ ℤ b≠0 b/a se a = qb

• Def: a, b non entrambi o ai altro che d ∈ ℤ è un MCD tra a, b
• ⇔ 1) d|a, d|b
• 2) ∀ x ∈ ℤ t.c. x|a, x|b => x|d

Def: a, b non entrambi o ai altro che m ∈ ℤ

è un mcm tra a,b

se: 1) a|m, b|m

• 2) ∀ x ∈ ℤ t.c. a|x, b|x => m|x

Il MCD esiste sempre ed è unico

dim. Unicità:

d₁(a,b) d₂(a,b) ⇒ d₁|a, d₂|b 2 x |a, x|b => x|d₁

⇒ d₁|a, d₁|b d₁|x₁d₁

d₂|a, d₂|b d₁|d₂ uvd₁

d₁ = vd₂ ⇒ d₂ uvd₁

per convenzione vi sia u = ±v ⇒ d₁ = ±d₂

dim esistenza:

• 1 d∈ ℤ t.c. d= (a,b)
• Considero X = {ax+by|x,y ∈ ℤ |} ∩ IN
• X ≠ ∅ de X minimo => d = (a,b)
• verifico ii) cla a = a+qtr a de = ax+by, e ∈ ℤ
• r ∈ Ex m ad. perché rid e il minx

proprietà: a,b∈ℤ n>2 n∈ℕ

1. a≡b (n) ⇔ ∀ h∈ℤ ha≡hb (n)
2. a≡b (n) e a≡b' (n) ⇒ aa'≡bb' (n) aa'≡bb' (n)
3. a≡b (n) a≡b (d) ⇒ a≡b (d)
4. a≡b (n) a≡b (m) ⇒ a≡b (L.m.m.n.)
5. a≡b (n) a≡n.≡b (m) ⇒ a = b ( _{n n} lcm)

dim:

1. a≡rb (n) a≡b ( _{n n} lcm)
2. a≡b (n) n | a∡(a-b)
3. a≡b (n) n | (a'-b') ⇒ aa'.bb' ≡ a.b (a' b') ⇒ aa'.≡bb' ≡ a' b (a' b)
4. a≡b (n) ⇒ a - b = [K,m].a - b
5. K.n | a - b ⇒ (a.k.n. n) | (a.n)
6. ¹ /₂ [a-b] | ( ¹ /₂ (a-b)) ⇒ Q Z (k.2)

oss: non vale la legge di cancellazione

prop

e.x≡b (m'c') risolubile ⇔ (a,n) | b

e coroll, a.x≡1 (n) risolubile o (a,n) = 1

propp

f.a≡b (m) risolvibile se:

x≡b' (m)

teorema cinese del resto (I)

stcom m₁...m_{r >2 ∀ mi,mj ∈ ℕ (mi,mj) = 1 ∀i ≠ j}

∀ a₁,...a_r esiste ū sistema f.x≡a (m₁)

ha un’unica soluzione x≡x₀ f.k ≡ a_r (m_r)

dim: {x≡a₁ (m₁)...,}

e l’unica soluun e l’autica

(II) (m,n)=1 m≥2 m≥2

⇒ Φ: Z/m Z→Z/m x Z/n Z/n

[a] _Zm [A] _Zn

dim: Φ buona definizione e Φ : [a₁] _{m−> n CA m ⇒ [aj] m, [aj] m? ≡ e ≡ a' (n) ⇒ z≡a' (m,}

a≡a' (m,n) axa'e' (n) or

1. Φ c' rangetta ∀ [a] n∃ ⊴A_m (f_jk) f: ZnZ Zm.A∋, e ZnZ Zm.Z Zx0 e +A (k)

quindi (m,n)≠ 1 pu il n. cinese xi. existe ed conclusive

Th cinese

Z/mZ × Z/nZ ≅ Z/mnZ ⇔ (m, n) = 1

dim) fare dimostrare che Z/mZ × Z/nZ è ciclico. Dire che ([1]_m, [1]_n) è un generatore, cioè ha ordine un ord. t.c. [(1_m), (1_n)] = kde dove k è dim. t.c. (k([1]_m), k([1]_n)) = ([0]_m, [0]_n)

k: i = 0 (mod m) k: i = 0 (mod n) ⇒ (m, n) = k = mn

Lemma: G₁ × G₂ (x, y) ord(x, y) = [ord (x), ord(y)]

poiché Z/mZ × Z/nZ è ciclico ∃a, b t.c. ord(a, b) = m, n

Corollario: (m, n) = 1

Z/mZ × Z/nZ ≅ (Z/mZ)* × (Z/nZ)* ≅ (Z/mnZ)*

Classe laterali e insieme quoziente (Z/mZ)* × (Z/nZ)* ≅ (Z/mnZ)*

∃H: H è una relazione di equivalenza su G (riflessiva-simmetrica-transitiva)

[x]_H = {y ∈ G | y ≡_H x} = {y ∈ G | y = xh⁻¹ ∃h ∈ H} = {y ∈ G | yx⁻¹ ∈ H} ⟨classe laterale

inesima⟩ xH = {xh | h ∈ H} p.t. costruiamo una ∀x ∈ G

ord(x) = eH = H

G = xH ⇔ x ≡_H x ∈ H

Teorema di Lagrange

dim: #^x = #^H ⇔ G gruppo finito ⇒ ∀H ⊆ G |H| || |G|

G = ⋃_{x ∈ R}xH ♭. G = ∑_{x ∈ R}xH

⇒ #G = (#H)(#R) || #H | #G

1 corollario: G gruppo finito ⇒ ∀x ∈ G ord x | ord G = |C|

dim ∀x ∈ G ⟺ x^|G| = e

ord(x) = ord(x) || |G|

1 corollario: G gruppo |G| = p primo ⇔ G ≅ Z/pZ

dim: Barrow vedere che G = ciclico: ∃x ∈ G ⇒ ord x || |C| = p

⇒ ord x = p = |x>: G = G (elemento di ordine p, i di ordine p)

⇒ #{xH| x ∈ R} = C; H = R |R| = |G| = |H||R| |C: H| ^||C||G|_||H||G = ₁

Def. G gruppo finito, H ⊂ G i s.lami lat ex di H in G ⟹

Def. G gruppo H ⊂ G nor dal monorale a xH: Hx ⊕ ∀x ∈ G

prop: ∀eZ(C)_G(A) ⊂ G, A ⊂ G

dim: Z(C)_GA ⊂ G Z(C)_Gx = {x ∈ G | xg = gx ∀g ∈ C} Z(C)_G

gZ(C)g⁻¹ ⊂ Z(C) ∀ g ∈ G, devo provare che ∀x ∈ Z(C)∀g ∈ G

gxg⁻¹ = Z(C) , ∀h ∈ G (x⁻¹ x)^g h = h (gxg⁻¹)

(gx = g⁻¹) h = gx ⇔ xh = xh = h (gxg⁻¹)

AR6