Algebra e geometria - Congruenze lineari (parte ll)

Congruenze lineari

La congruenza lineare x = b (mod n) ha soluzioni se e solo se d = MCD(a,n) divide b. In questo caso, si esprime come combinazione lineare di a e n: d = a a' + n n'. Una soluzione è x₀ = a' * b/d. Le altre soluzioni sono x₀ + n/d * k con k ∈ ℤ.

Esempio

36x = 24 (mod 105)

MCD(36,105):

• 105 = 36 * 2 + 33
• 36 = 33 * 1 + 3
• 3 = 3 * 1 + 0

3 divide 24, quindi ci sono soluzioni. Scriviamo 3 come combinazione lineare:

• 3 = 36 - 33
• 33 = 105 - 36 * 2
• 3 = 36 - (105 - 36 * 2) = 36 * 3 - 105

Quindi, a = 36, n = 105, d = 3, a' = 3, n' = -1.

Calcoliamo 36 * 24:

• 864 - 24 è un multiplo di 105
• 864 - 24 = 105 * 8

Le soluzioni sono 24 + n/d * k = 24 + 105/3 * k = 24 + 35 * k con k ∈ ℤ.

Aritmetica modulare

Proprietà

• Se a ≡ b (mod n) allora a + c ≡ b + c (mod n).
• Se a ≡ b (mod n) e c ≡ d (mod n), allora a + c ≡ b + d (mod n).
• Se a ≡ b (mod n) allora a ∗ c ≡ b ∗ c (mod n).

Esempi

n = 4. Se a ≡ b (mod 4), allora a - b ∈ 4 ℤ.

• ℤ₄ = {[0]₄, [1]₄, [2]₄, [3]₄}
• [0]₄ = {0, 4, 8, …} = {4k | k ∈ ℤ}
• [1]₄ = {1, 5, 9, …}
• [2]₄ = {2 + 4k | k ∈ ℤ}
• [3]₄ = {3 + 4k | k ∈ ℤ}

-3 ≡ 1 (mod 4) perché -3 - 1 = -4 = 4 * (-1).

[a]₄ è l'insieme dei numeri che divisi per 4 danno resto a:

• 2 ≡ 6 (mod 4)
• 2 + 1 ≡ 6 + 5 (mod 4)
• 2 + 3 ≡ 6 + 3 (mod 4)
• 3 ≡ 11 (mod 4)
• 5 ≡ 9 (mod 4)

Definizione

n = 4, ∈ ℤ

• [0] + [0] = [0]
• [1] + [1] = [2]
• [2] + [2] = [0]
• [3] + [3] = [2]

ℤ₂ = {[0]₂, [1]₂} ∈ ℤ

• [0] + [0] = [0]
• [1] + [1] = [0]
• [0] + [1] = [1]

Moltiplicazione modulare

[a]_n * [b]_n := [a * b]_n, n = 3

• [0] * [0] = [0]
• [1] * [1] = [1]
• [2] * [2] = [1]
• [1] * [2] = [2]

Operazioni su insiemi

Un'operazione (binaria, interna) su un insieme A è una funzione * : A x A → A. Invece di scrivere *(a₁,a₂), si scrive a₁ * a₂ (notazione INFISSA).

Esempi di operazioni

• +: ℤ x ℤ → ℤ
• (x, y) → (x * y)
• U: P(A) x P(A) → P(A)
• (X, Y) → X u Y

Anche è un'operazione su P(A).

Commutatività

Un'operazione * su A è commutativa se per ogni a, b: a * b = b * a. Non è commutativa, ad esempio, f o g != g o f.

La sottrazione non è commutativa:

• n-m != m-n