Algebra e geometria - Congruenze lineari (parte ll)

MCD(36,105) 105 = 36 * 2 + 33

36 = 33 * 1 + 3

33 = 3 * 11 + 0

3 divide 24

quindi ci sono soluzioni

3 = 36 – 33

33 = 105 – 36 * 2

3 = 36 – (105 -36 * 2) = 36 * 3 - 105

a = 36 n = 105 d = 3

a' = 3 n' = -1

36 * 24 = 24 (mod105)

36 * 24 – 24 è un multiplo di 105

864 – 24 = 105 * 8 24 + n/d * k = 24 + 105/3 * k

= 24 + 35 * k

k ∈ℤ

Aritmetica modulare

Proprietà Se a≡b n) allora a+ c≡b+ c(mod n)

(mod

* a≡b(mod n) e c≡d mod n), allora a n)

( +c≡b +d (mod

* Se a≡b( mod allora a∗c≡b∗c mod n)

) (

Esempio n = 4

a≡b 4) se a−b∈4

(mod ℤ

4={[0]4, [1]4, [2]4, [3]4}

ℤ k }

[0]4 = {0,4,8, … } [2]4 = {2 + 4k | ∈ℤ

k }

[1]4 = {1,5,9, -3} [3]4 = {3 + 4k | ∈ℤ

-3 -1 = -4 - 3 = 4 * (-1) + 1

−4∈4 ℤ

4)

−3≡1(mod

[a]4 è 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 n)

(mod

DEF. n

[a]n + [b]n := [a + b]n n = 4

∈ℤ [0] [1] [2] [3]

+

[0] [0] [1] [2] [3]

4

[1] [1] [2] [3] [4]=[0]

4

[2] [2] [3] [0] [1]

4

[3] [3] [0] [1] [2]

4

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

ℤ [0] [1]

[0] [0] [1]

[1] [1] [0]

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

X [0] [1] [2]

[0] [0] [0] [0]

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

[2] [0] [2] [1]

DEF. Un'operazione (binaria, interna) su un insieme A

è una funzione

* : A x A → A

Invece di scrivere *(a1,a2) si scrive a1 * a2 (notazione INFISSA)

x -> x ->

Es. +: ℤ ℤ ℤ ℝ ℝ ℝ

(x,y) → (x * y)

m x m -> m

+: ℤ ℤ ℤ

([a]m , [b]m) → [a+b]m

U: P(A) x P(A) → P(A)

(X,Y) → X u Y

Anche è un'operazione su P(A)

∩ A

Es. è l'insieme delle funzioni f:A → A

A A A A

Se => la composizione di funz. È una operazione su

f , g allora f o g A A

∈A ∈ a , b∈ A

DEF. Un'operazione * su A è COMMUTATIVA se per ogni

a * b = b * a

NON E' COMMUTATIVA f o g != g o f

x => n−m∈ℤ

Es. (n,m) ∈ℤ ℤ

la sottrazione non è commutativa n-m != m-n

Es. A = {a,b,c} g

f: a a a g(f(a)) = g(b) = a f(g(a)) = f(c) = c

b b b g(f(a)) = g(a) = c f(g(b)) = f(a) = b

c c c g(f(c)) = g(c) = b f(g(c)) = f(b) = a

g o f != f o g a , b , c∈ A

DEF. Un'operazione * su A è ASSOCIATIVA se per ogni

(a * b) * c = a * ( b * c) = a * b * c

Es. (2 + 3) + 4 = 2 + (3 + 4) = 2 + 3 + 4 la somma è associativa

Es. (2/3) / 4 != 2/(3/4)

2

( )

3 2 1 1 2 4 8 => la divisione non è associativa

=2∗( )=

= ∗( )=

4 3 4 6 3 3 3

( )

4

DEF. Una STRUTTURA ALGEBRICA è un insieme con un' operazione e si denota con (A,*)

,+) , (P(A),u) ,( m , *)

Es. ( sono strutture algebriche

ℕ ℤ

,+) e (

( sono due strutture diverse

ℕ ℕ,*) e A

DEF. L'elemento NEUTRO in una struttura (A,*) è un elemento ∈

a∈ A

tale che per ogni

,+)

Esempi ( 0 è l'elemento neutro 0 + n = n = n + 0

ℕ ,∗)

( 1 è l'elemento neutro 1 * n = n = n * 1

ℕ è l'elemento neutro x∪∅=x

(P(a),U) ∅

(P(a), ) A è l'elemento neutro X A = X = A X

∩ ∩ ∩

Es. A

( ) l'elemento neutro è la funzione identica

A , 0 a∈ A-> a∈ A

a a a idA :

b b b f o idA = idA o f = f

c c c a∈ A

DEF. (A, *) un elemento si dice SIMMETRIZZABILE

a∈ A

Se esiste un elemento tale che a * a' = e

,+)

Es. ( 0 el.neutro 3 è simmetriz.? No perchè non (0+0=0)

ℕ esiste in N un elemento che sommato a 3 mi dia 0

,∗)

Es. ( 1 il neutro, 3 non è simetrizz. Però 1 è simmetr. 1*1 = 1

ℕ

Esercizi

ax n)

≡b (mod

calcolare d = MCD(a,n)

scrivere d = aa' + nn' k

Se d divide b allora le soluz. a'*b/d + n/d * k ∈ℤ

Applicando l'algoritmo delle divisione successive calcolare

d = MCD(52,68)

e scrivere d come combinazione lineare 52 e 68

68 = 52 * 1 + 16

52 = 16 * 3 + 4 → MCD

16 = 4 * 4 + 0

4 = 52 – 16 * 3

16 = 68 – 52 * 1

4 = 52 – (68 – 52 * 1) * 3

4 = 52 * 4 – 68 * 3 ovvero d = a * a' + n * n'

d = 4

Dire se le congruenze lineari 52 x hanno soluzioni e, in caso

68) e 68x≡17 52)

≡16(mod (mod

affermativo.

Il primo ha soluzioni perchè il 16 è multiplo di d (ovvero 4) , il secondo invece no

Calcoliamo le soluzioni

a = 52 d = 4

b = 16 a' = 4

n = 68 x = 4 * 16 / 4 + 68 / 4 * k = 16 + 17k

Risolvere le seguenti congruenze lineari

a) x = 12 mod 7

b

b) 3x = 1 mod 5

c) 27x = 3(mod12)

5 = 3 * 1 + 2

3 = 2 * 1 + 1 → MCD

2 = 1 * 2 + 0 d = 1

1 = 3 – 2 * 1

2 = 5 – 3 * 1

1 = 3 – (5 – 3 * 1)

a a' n n'

1 = 3 * 2 – 5 * 1

x = 2 * 1/1 + 5/1 * k = 2 + 5k

c)

27 = 12 * 2 + 3 → MCD

12 = 3 * 4 + 0

d = 3

3 = 27 – 12 * 2

x = 1*3/3 + 12/3 * k = 1 + 4k

a)

x = 12 mod 7

7 = 1* 7 + 0 → MCD

1 = 1 * (-6) + 7 * 1

d = 1

a = 7 a' = -6

b = 12