♦ ♦ Il teorema di Eulero

♦ ♦ Equazioni lineari in Z

n

♦ ♦ Il teorema di Eulero

♦ ♦ Il calcolo dell’inverso in Z

n

♦ ♦ Rappresentazione trigonometrica in C

Rosalba Barattero

ESERCITAZIONE N.8

24 novembre 2009

ESERCIZIO 1.

Equazioni lineari in Z

n

Delle seguenti equazioni stabilire se hanno soluzioni, e in caso affermativo determinarle tutte

a) 12 ⋅ x = 0 in Z

₁₃

b) 6 ⋅ x = 3 in Z

₉

c) 12 ⋅ x = 0 in Z

₄₈

d) 12 ⋅ x = 9 in Z

₃₃

a) E’ un’eq.

^ne

del tipo ax=b con i coefficienti in Z

n

,di cui cer- chiamo le soluzioni in Z

_n

,cioè cerchiamo gli x ∈Z

13

t.c. 12 ⋅ x = 0 . Intanto notiamo che x = 0 è soluzione. Ce ne sono altre?

Se in Z

₁₃

esistesse x ≠ t.c. 0 12 ⋅ x = 0 allora 12 sarebbe 0-divisore e quindi non invertibile !

″ ogni elemento non nullo di Z

_n

o è invertibile o è zero divisore ( una delle due ! ) ″.

Ma sappiamo quali sono gli elementi invertibili di Z

13

: a ≠ 0 è invertibile ⇔ M.C.D.(a,13)=1.

Essendo 13 numero primo, tutti le classi non nulle di Z

₁₃

sono invertibili: Z

13

è un campo.

Se ne conclude che 12 non è 0-divisore, quindi x = 0 è l’unica soluzione di 12 ⋅ x = 0 .

b) Risolvere l’equazione 6 ⋅ x = 3 in Z

₉

Per tentativi:

6 1

6 ⋅ = ≠ 3 ⇒ 1 non è soluzione 3

12 2

6 ⋅ = = ⇒ 2 è soluzione

Ma ce ne sono altre?In questo caso ci sono ancora 6 ′controlli′

da effettuare, e non è difficile trovare tutte le soluzioni. Ma

usiamo il seguente

Teorema. In Z

_n

l’equazione a ⋅ x = b , con a ≠ 0 , ha soluzioni se e solo se d= M.C.D. (a,n) divide b.

E in tal caso ci sono d soluzioni distinte, esprimibili nella forma 1)c

(d x ,..., 2c x , c x ,

x

_{0 0}

+

₀

+

₀

+ −

dove c= d

n e x

0

è una soluzione dell’equazione.

Qui n=9, a=6,b=3 => M.C.D.(a,n)=3 => ci sono 3 sol.

ⁿⁱ

Una sol.

^ne

è x

0

= 2 ,c=n/d= 3=> le 3 sol.

ⁿⁱ

sono

2 , 2 + 3 = 5 , 2 + 2 ⋅ 3 = 8 .

c) Per l’equazione 12 ⋅ x = 0 in Z

₄₈

la situazione è diversa da a).

12 non è primo con 48 e quindi non è invertibile e come tale è 0-divisore. Del resto è immediato notare che 12 ⋅ 4 = 0 .

M.C.D.(12,48)=12=>12 soluzioni,una è 0 =>(c=n/d=48/12=4) 0 , 0 + 4 = 4 , 4 ⋅ 2 = 8 , 4 ⋅ 3 = 12 , 4 ⋅ 4 = 16 , 4 ⋅ 5 = 20 ,

24 6

4 ⋅ = , 4 ⋅ 7 = 28 , 4 ⋅ 8 = 32 , 4 ⋅ 9 = 36 , 4 ⋅ 1 0 = 40 , 44

1 1

4 ⋅ = stop ! ( si ripetono ciclicamente)

d) 12 ⋅ x = 9 in Z

₃₃

, M.C.D.(12,33)=3 => 3 sol.

ⁿⁱ

. Dobbiamo trovare una soluzione !

9 x

12 ⋅ = in Z

33

⇔ ^12x = ⁹ in Z

33

⇔ 12x≡9 modulo 33 ⇔ 12x-9= 33y in Z ⇔ 12x-33y=9 in Z

Quindi risolvere in Z

33

l’equazione 12 ⋅ x = 9 equivale a risolvere in Z l’equazione diofantea 12x-33y=9 in Z. Usiamo l’algoritmo euclideo…, ma qui è facile ! M.C.D.(12,33)=3 => 12(3)-33(1)=3

=> 12(9)-33(3)=9 => x

0

= 9 . Le altre due sol., da c=n/d=11 sono: ^x

₀

+ ^c = ²⁰ e ^x

₀

+ ^{2 c} = ³¹ .

Importante ! da Z

n

a Z

ESERCIZIO 2.

Verifichiamolo !

Facciamo le seguenti divisioni: • 1835 = 7⋅262 + 1 • 1986 = 7⋅283 + 5

Così riduciamo le basi modulo 7: 1835 = , 1 1986 = . 5 L’uguaglianza da verificare si è semplificata così:

2061

1910

5

1 + = ⁰ in Z

7

Per la proprietà delle potenze negli Z

n

si ha : 1

¹⁹¹⁰

= 1

¹⁹¹⁰

= 1 L La a c co om me et ta a d di i H Ha al ll le ey y e e Z Z

_{7 7}

Le ultime tre apparizioni della cometa di Halley sono state negli anni 1835, 1910, 1986 e la prossima sarà nel 2061.

Tra questi quattro numeri c'è il legame seguente

1835

¹⁹¹⁰

+ 1986

²⁰⁶¹

= 0 in Z

7

Resta ancora da calcolare 5

²⁰⁶¹

, che deve valere 6 . Si può applicare il piccolo teorema di Fermat ?

Qui p=7 primo, a=5 è un intero non nullo e non divisibile per 7, allora il Teorema ci dice che a

^p−1

= 5

⁶

= 1 in Z

7

.

Per utilizzare questa informazione e calcolare 5

²⁰⁶¹

è sufficiente fare la divisione per 6 ad esponente, e usare le solite proprietà delle potenze in Z.

5 =

2061

5

^343⋅6+3

= 5

^343⋅6

⋅ 5

³

= 5

⁶³⁴³

⋅ 5

³

= 1 = 1 ⋅ 5

³

= 25 ⋅ 5 = 4 ⋅ 5

= 6 Ok !

L’esercizio sulla cometa è tratto da D.M.BURTON UND H.DALKOWSKI - Handbuch der elementaren Zahlentheorie

ESERCIZIO 3 C .

Il teorema di Fermat e l’inverso di un elemento in Z

n

Calcolare 3

⁹

in Z

31

e determinare, usando il teorema di Fermat , l’inverso ( moltiplicativo) di 3 .

3

9

= ^⎜ _⎝ ^{⎛ 3 ⎟}

³

_⎠ ^⎞

³

= − 4

³

= − 64 = − 2 = 29 Il teorema di Fermat dice che:

p primo, a intero non nullo e non divisibile per p => a

^p−1

= 1 in Z

p

o equivalentemente p primo, a ≠ 0 => a

^p−1

= 1 in Z

p

Quindi in Z

p

se p è primo, a ≠ 0 , moltiplicando a

^p−1

= 1 per a

⁻¹

( che esiste perché ogni elemento non nullo del campo Z

p

ha inverso) si ha

a

^p−1

⋅ a

⁻¹

= a

⁻¹

a

^p−2

= a

⁻¹

Da cui 3

⁻¹

= 3

²⁹

=> 3

²⁹

= ^{3 3}

²

9 3

⎟ ⋅

⎠ ⎞

⎜ ⎝

⎛ = 29

³

⋅ 3

²

= - 2

³

⋅ 9 = − 72 = − 10 = 21

=> 21 è l’inverso di 3 .

Osservazione Senza usare il piccolo teorema di Fermat qui è molto più rapido !

1 21 3 1 10 - 3 ) 1 )(

1 ( ) 1 )(

10 3 ( 1 - 10

3 ⋅ = ⇒ ⋅ − = − − ⇒ ⋅ = ⇒ ⋅ =

ESERCIZIO 4 C .

Il teorema di Eulero - L’inverso di un elemento in Z

n

a) In Z

45

determinare r, 0≤r<45, t.c. r = 7

³¹³

. b) Stabilire perché 7

³¹³

è invertibile in Z

45

e

determinarne l’inverso.

a) Il piccolo teorema di Fermat non ci aiuta in questo caso perché non siamo in Z

p

, con p primo. Ma c’è la seguente generalizzazione:

T

EOREMA DI

E

ULERO

:

Se a ed n sono due interi coprimi (primi fra loro) allora si ha a

^ϕ(n)

= 1 in Z

n

, dove la funzione di Eulero ϕ(n) indica il numero degli interi positivi, minori di n, che sono primi con n.

Nel nostro caso n=45, a=7, M.C.D.(7,45)=1, quindi si può applicare il teorema di Eulero. Occorre trovare ϕ(45), ossia il numero di interi positivi x<45, che sono primi con 45.

1,2,4,7,8, …

Meglio disporre di qualche regola per trovare ϕ(45).

ϕ(p)= p-1 con p primo ( in questo caso il teor. di Eulero si riduce al piccolo teorema di Fermat !)

ϕ(p

^s

) = p

^s

- p

^s-1

con p primo

se n=a⋅b,con a,b coprimi, allora ϕ(n)=ϕ(a)⋅ϕ(b) se si decompone n in fattori primi ϕ(n) è determinato con le 2 proprietà precedenti …

45= 5⋅9 =5⋅3

²

, 5 e 3

²

sono coprimi, allora risulta

ϕ(45) = ϕ(5)⋅ϕ(3

²

). Ma 5 è primo, quindi ϕ(5)= 5-1=4, anche 3 è primo, quindi ϕ(3

²

)=3

²

-3

¹

, perciò ϕ(9)=6,e di conseguenza ϕ(45)=ϕ(5)⋅ϕ(9)= 4⋅6=24.

Applichiamo il teorema di Eulero: a

^ϕ(n)

= 1 in Z

n

, perciò

1

7

^ϕ(45)

= in Z

45

, ossia 7

²⁴

= 1 in Z

45

.

Ora calcoliamo 7

³¹³

, dividendo l’esponente per 24.

7

313

= 7

^24⋅13+1

= ^⎜ _⎝ ^{⎛ 7}

²⁴

^⎟ _⎠ ^⎞

¹³

^{⋅ 7} = ( ) ¹

¹³

^{⋅ 7 = 7 .}

Quindi 7

³¹³

= 7 ⇒ r=7 risponde alla domanda a).

b) Ora usiamo la proprietà che stabilisce quali sono gli ele- menti invertibili di Z

_n

.

In Z

n

a ≠ ⁰ è invertibile ⇔ M.C.D.(a,n)=1.

Nel nostro caso: M.C.D.(7,45)=1⇒ 7 è invertibile in Z

45

. Allora si può trovare l’inverso moltiplicativo di 7 , ossia (l’unico) x ∈Z

45

tale che 7 ⋅ x =1 ( eq.

^ne

lineare in Z

45

).

x

7 ⋅ =1 in Z

45

⇔ ^7x =1

⇔ 7x ≡ 1

(due classi di eq.^va coincidono ⇔ i loro rappresentanti so- no equivalenti, che in questo caso vuol dire congruenti )

⇔ 7x -1 è multiplo di 45 in Z

( def. di congruenza)

⇔ ∃ y∈ Z t.c. 7x -1 = 45y

Dunque il problema si è ridotto alla risoluzione dell'equa- zione lineare 7x – 45y=1 in Z, più precisamente dobbiamo trovare una sua soluzione (a,b)∈ ZxZ

(in pratica poi utilizzeremo solo la "a" trovata).

Sappiamo già che questa equazione ha soluzioni in Z perché M.C.D.(7,45)=1 .

Troviamo una soluzione intera,usando l’algoritmo euclideo:

45= 7⋅6+3 3= 45 - 7⋅6 7= 3⋅2+1 1= 7- 3⋅2 3= 1⋅3

Quindi 1=7- 3⋅2

= 7- (45-7⋅6)2 = 7- 45⋅2+7⋅12 = 7⋅13- 45⋅2

Da 1=7⋅13-45⋅2 passando alle classi modulo 45, ricaviamo 1 = 7 ⋅ 13 − 45 ⋅ 2 in Z

₄₅

= 13 7 ⋅ ( 45 = 0 in Z

45

) ⇒ x = 13 è l’inverso di 7 .

U N PAIO DI UTILI TABELLE

R

APPRESENTAZIONE TRIGONOMETRICA IN

C

I numeri reali, si possono rappresentare geometrica- mente come punti di una retta. Anche i numeri com- plessi si possono rappresentare geometricamente, ma come punti del piano reale.

Si introduce nel piano reale un sistema O

x,y

di coordinate cartesiane ortogonali e si associa al numero complesso z=a+ib il punto P(a,b).

z=a+ib coppia ordinata (a,b) di RxR punto P(a,b)

x asse reale (complessi con b=0) y asse immaginario (complessi con a=0)

Piano di Argand- Gauss

ρ = distanza di P(a,b) dall'origine O ( quindi ρ>0 ) = a

²

+ b

²

= modulo di z =|z|

θ = angolo formato in senso antiorario dalla semiretta positiva dell'asse x con la semiretta OP

argomento di z = Arg(z) (∀z≠0) definito a meno di multipli di 2π, ossia

Arg(z) = θ+2kπ, k ∈Z Si suppone z≠0 poiché se z=0 l'argomento è indeterminato.

Forma algebrica Forma trigonometrica z=a+ib z= ρ (cosθ +i senθ)

Dato z=a+ib (z≠0)

si calcolano ρ e θ

Dalle formule trigometriche per i triangoli rettangoli si ha : a = ρ cosθ , b = ρ senθ e quindi

z= ρ (cosθ +i senθ) forma trigonometrica del numero complesso z = a+ib

⎪ ⎪

⎪ ⎪

⎩

⎪ ⎪

⎪ ⎪

⎨

⎧

= +

= +

= +

=

b a sen b

b , a cos a

t.c.

2π di multipli di

meno a def.

angolo l'

Pitagora) di

(teorema

2 2 2

2 2 2

ϑ ϑ

ϑ

ρ a b

ESERCIZIO 5.

Calcoli in C con la forma trigonometrica

Disegnare nel piano di Argand-Gauss i seguenti numeri complessi e rappresentarli in forma trigonometrica:

a) 2i b) -3i c) -1 d) 1+i

Verifichiamo l’esattezza dei valori trovati per ρ e θ tramite le formule precedenti: 2i = a+ib con a= 0, b = 2

⇒ ρ = a

²

+ b

²

₌ 4 = 2

2 0 cos 0

2

2

= =

= +

b a

ϑ a

_,

1

2 sen 2

2

2

= =

= +

b a ϑ b

⇒ θ = Arg(z) = π π k

2 + 2 , k ∈ Z a)

2i = 0+2i P(0,2) ρ e θ si leggono qui dal disegno.

ρ = d(P,O)=2 θ = ^π ₂ (a meno di multipli di 2π).

Quindi la forma trigonometrica di z è :

z = ρ (cos θ +i sen θ ) = 2( cos 2

π + i sen 2 π )

b) z=-3i : sta sull'asse immaginario negativo ρ = 3, θ = 2 3 π

(a meno di multipli di 2π)

⇒ z=3(cos 2 3 π

+i sen 2 3 π )

( oppure z= 3(cos ^{− π} ₂ +i sen ^{− π} ₂ ) )

scriviamo l'unico angolo θ, 0≤θ<2 π

t.c. cos θ = 0 e sen θ =1

d) z=a+ib = 1+i P(1,1)

dal disegno : θ = π/4 , ρ = a

²

+ b

²

₌ 2

⇒ z= 2 _{( cos 4} ^π _{+ i sen 4} ^π ₎

c) z=-1

sta sull'asse reale negativo

ρ = 1, θ=π (a meno di mul- tipli di 2π)

⇒ z= 1(cosπ +i senπ)