Congruenze lineari (parte I)

Numerazione in base n

Esempio di calcolo

458 = 4 * 100 + 5 * 10 + 8 * 1 = 4 * 10² + 5 * 10¹ + 8 * 10⁰

Base 2

Un bit può assumere solo 2 valori: 0 e 1. Per esprimere un numero in base 2, devo scrivere come somma di potenze di 2.

Esempio Base 2

458 = 45 * 10 + 8
458 = 229 * 2 + 0
45 = 4 * 10 + 5
229 = 114 * 2 + 1
4 = 0 * 10 + 4
114 = 57 * 2 + 0
57 = 28 * 2 + 1
28 = 14 * 2 + 0
14 = 7 * 2 + 0
7 = 3 * 2 + 1
3 = 1 * 2 + 1
1 = 0 * 2 + 1
(458)₂ = 1 1 1 0 0 1 0 1 0

Es.8 Quante cifre ci vogliono per scrivere 8 in base 2?

8 = 4 * 2 + 0
4 = 2 * 2 + 0
2 = 1 * 2 + 0
1 = 0 * 2 + 1
1000 = (8)₂
8 = 2³ + 0 * 2² + 0 * 2¹ + 0 * 2⁰
=> Servono 4 cifre

Per scrivere 16?

(16)₂ = 10000 (5 cifre)

Il numero di cifre

Per esprimere n in BASE 2 è <= log₂ n. Nota che log₂ n è l'esponente da dare a 2 per ottenere n.

Un byte

Un byte sono 8 bit => 2⁸ possibili valori. Un byte si può esprimere come due cifre esadecimali (cioè in base 16).

Esempio: scriviamo 45 in base 16

458 = 28 * 16 + 10
28 = 1 * 16 + 12
21 = 0 * 16 + 1
458 = 1 * 16² + 12 * 16¹ + 10 * 16⁰
Si utilizzano i simboli: 0 1 2 3 4 5 6 7 8 9 A B C D E F
(458)₁₆ = 1CAD

Relazione di congruenza

Tra interi in modulo (n è congruo a m modulo 3)≡3
Se n = m ∈ 3 ℤ
4 1 4 – 1 = 3≡3 ∈ 3 ℤ
3 0 18 = 3≡3
17 !≡ 3 3
Proprietà
equiv 3 è una rel. d ' equivalenza

Dimostrazione

Riflessività
n n allora n – m≡3 ∈ 3 ℤ
e quindi m – n e cioè ∈ 3 ℤ
m n≡3

Transitività

n m m t
Se e≡3 ≡3
allora n-m n-m = 3h∈3 ℤ
m-t m-t = 3k∈3 ℤ
n-t = n – m + m -t = 3h + 3k = 3(h+k)=> n-t ∈ 3 ℤ
n t=> ≡3

Classi di equivalenza

[3]₃
Notazione: Invece di scrivere [3] ≡3 [n] ≡3 scrivo [n]₃3
3≡30 3≡31 3
poiché 1-3 !∈ℤ≡31 !≡3 3
poiché 1−3 !≡9 ℤ
[3]₃ = {0,3,6,9,...}

Multiplo di 3

n 3 se n-3≡3 ∈3 ℤ
=> n-3 = 3h=> n = 3 + 3h = 3(1+h)
n è multiplo di 3
[3]₃ = {..., -9,-6,-3,0,3,6,9,...}
[0]₃[1]₃ {1,4,7n 1 se n-1≡3 ∈3 ℤ
cioè n-1 = 3h cioè n = 3h + 1n 1=> ≡3 dividendo n per 3 ottengo resto 1
[2]₃ = {2,5,8,11,...}
In [2]₃ ci sono i numeri che divisi per 3 danno resto 2
[0]₃ = [3]₃ ci sono 3 classi di equivalenza
[1]₃ = [4]₃
[2]₃