Divisibilità

n = mq + r

r = resto della divisione

Classi di resto

m ∈ Z, [n]m si chiama classe di modulo m

[n]m = {x ∈ Z | n - x è multiplo di m} =

={x ∈ Z | il resto della divisione tra n e m è uguale al resto della divisione tra x e m}

={x ∈ Z | rest(x, m) = rest(n, m) }

Se x ∈ [n]m diciamo che "x è congruo a n modulo m" x === n(mod m)

NOTAZIONE:

• Zm insieme delle classi di resto modulo m
  • |Zm| = m
  • Zm ={[0]m, [1]m, ..., [m-1]m}

OPERAZIONI TRA CLASSI:

• Somma: [a]m + [b]m = [a+b]m
• Prodotto: [a]m * [b]m = [a * b]m

DEF: [n]m è invertibile se esiste [x]m tale che [n]m * [x]m = [1]m. Dico che [x]m è inverso di [n]m (x può essere = n)

PROPRIETA':

• [n]m è invertibile SE E SOLO SE MCD(n, m) = 1 (in tal caso n e m sono COPRIMI)

DEF: Funzione di Eulero: φ(m) = | {n ∈ N | MCD(n, m) = 1 e n < m} | conta quanti numeri < n e coprimi con n ci sono (quanti elementi invertibili)