Congruenze lineari (parte I)

Il numero di cifre

Per esprimere n in BASE 2

è <= log2 n

Nota che log2 n è

l'esponente da dare a 2 per ottenere n

Un byte sono 8 bit

=> 2^8 possibili valori

un byte si può esprimere come due cifre esadecimali (cioè in base 16)

Es. scriviamo 45 in base 16

458 = 28 * 16 + 10

28 = 1 * 16 + 12

1 = 0* 16 + 1

458 = 1 * 16^2 + 12 * 16^1 + 10 * 16^0

Si utilizzano i simboli

0 1 2 3 4 5 6 7 8 9 A B C D E F

(458)16 = 1CA

Def.

Relaz. di congruenza tra interi

n m (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

DIM. Riflessiva

n n allora n – m

≡3 ∈3 ℤ

e quindi m – n e cioè

∈3 ℤ

m n

≡3

Transitiva

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 d'equivalenza

[3]3 Notazione: Invece di scrivere

[3 ] ≡3 [n] ≡3

scrivo

[n]3

3 3

≡3

0 3

≡3

1 3 poichè 1-3 !∈ℤ

≡3

1 !≡3 3 poichè 1−3 !≡9 ℤ

[3]3 = {0,3,6,9,...}

n 3 se n-3

≡3 ∈3 ℤ

=> n-3 = 3h

=> n = 3 + 3h = 3(1+h)

n è multiplo di 3

[3]3 = {…., -9,-6,-3,0,3,6,9,...}

[0]3

[1]3 {1,4,7

n 1 se n-1

≡3 ∈3 ℤ

cioè n-1 = 3h

cioè n = 3h + 1

n 1

=> ≡3

dividendo n per 3

ottengo resto 1

[2]3 = {2,5,8,11,...}

In [2]3 ci sono i numeri che divisi per 3 danno resto 2

[0]3 = [3]3 ci sono

3 classi d'equivalenza

[1]3 = [4]3

[2]3 = [5]3

/≡3 insieme quoziente

ℤ cioè l'insieme delle

classi d'equivalenza

/≡3 = {[0]3, [1]3, [2]3}

ℤ

Classi di resto modulo 3

Def. Congruenza modulo m

≡m

[m]m è l'insieme dei numeri che divisi per m hanno resto n

Es. [7]9 = {7,16,...}

2 1

[1]2 = { ℤ+

[0]2 = { 2 ℤ

/≡2 = {[0]2, [1]2}

ℤ /≡3 = {[0]3, [1]3, [2]3}

ℤ /≡3 = {[0]m, [1]m, ... , [m-1]m}

ℤ

Quindi m è l'insieme delle classi modulo m

ℤ

| m| = m

ℤ

Esempio

Sono le 22 e metto la sveglio tra 8 ore

22 + 8 ? devo ragionare modulo 24

30≡24 6

=> la sveglia sarà alle 6 di mattina

Notazione 30≡24 6

Invece di scrivere Si scrive

30≡6 (24)

30≡ 24 6

Es.

è martedì. Che giorno della settimana è tra 9 giorni?

0 1 2 3 4 5 6

dom lun mar mer gio ven sab

2+9 = 11

11≡4(mod 7) è giovedì

Congruenze lineari

Voglio trovare il valore di una variabile se tale che

a * x = b (mod n)

Es.

2 x = 4 (mod 2)

2 * 2 = 4 (mod 2)

Ci sono altre sol.

3x 2 * 3 = 6

6 = 4 (mod2) 6-4 = 2

Es. 2x = 1 (mod2)

Non ha soluzioni

Es. 3x = 2 (mod5)

X = 4 soluz x = 9

tutti 4 + 5 é k => sono soluzioni

∈ℤ

Teorema

Una congruenza lineare

ax , n)

≡MCD(a

d divide b

Se X0 è una soluzione allora

n k

x = x0 + ∗k ∈ℤ

d sono soluzioni

Es.

60x = 8 (mod 35)

Devo calcolare MCD (60,35)

60 = 35 * 1 + 25

35 = 25 * 1 + 10

25 = 10 * 2 + 5 => MCD(60,35) = 5

10 = 5 * 2 + 0

Dato che 5 non divide 8

allora non ci sono soluzioni

60x = 10(mod35)