Agenda -...

Gregorio D’Agos,no TVG

Agenda

Correggeremo esercizi in sospeso Esercitazione sui sistemi di equazioni diofantee.

1


Forma chiusa numeri di Tartaglia

Dim per induzione su n: (Caso n=1)

(Ricorsione)

2

nk!

"#$

%&=

n!k!(n− k)!!

"#

$

%&=

n(n−1)...(n− k +1)k(k −1)...(2)1

!

"#

$

%&

10!

"#$

%&=1;

11!

"#$

%&=1

n+1k +1!

"#

$

%&=

n!(k +1)!(n− k −1)!!

"#

$

%&+

n!k!(n− k)!!

"#

$

%&

=n!

k!(n− k)!"

#$

%

&'n− k −1(k +1)

"

#$

%

&'+

n!k!(n− k)!"

#$

%

&'=

n!k!(n− k)!"

#$

%

&'

n− k −1(k +1)

"

#$

%

&'+1

(

)*

+

,-=

=n!

k!(n− k +1)!"

#$

%

&'

n− kk +1

"

#$

%

&'+1

(

)*

+

,-=

n!k!(n− k +1)!"

#$

%

&'

n+1k +1"

#$

%

&'

(

)*

+

,-=

(n+1)!(k +1)!(n− (k −1))!"

#$

%

&'=

n+1k +1

"

#$

%

&'


Ricordiamo il binomio di Newton

Dim: (per induzione su n)

(Caso n=1)

(Ricorsione)

3

(x +1)N =Nk!

"#

$

%&

k=0,N∑ (x)k

(x +1)1 =1=1k!

"#$

%&

k=0,1∑ (x)k = x1 +1= x +1

(x +1)N+1 = (x +1)Nk!

"#

$

%&

k=0,N∑ (x)k =

Nk!

"#

$

%&

k=0,N∑ (x)k+1 +

Nk!

"#

$

%&

k=0,N∑ (x)k =

=Nj −1"

#$

%

&'

j=1,N+1∑ (x) j +

Nj"

#$

%

&'

j=0,N∑ (x) j =

Nj"

#$

%

&'+

Nj −1"

#$

%

&'

)

*+

,

-.

j=1,N+1∑ (x) j =

N +1j"

#$

%

&'

j=1,N+1∑ (x) j


Esercitazione

•  Risolviamo qualche sistema diofanteo applicando il teorema dei resti cinese.

•  Scriviamo con Octave un pogramma che realizzi il metodo di Euclide per trovare il MCD e il mcm.

4


Soluzione Esercizio

Esercizio: In Zn n=11 x 13=143 Z143 Risolvere il sistema x= 3 (mod 11) x=5 (mod 13) Il sistema è compatibile perché 11 e 13 sono coprimi. x’=3+11 j con j=0,1, 2, … , 12 (3, 14, 25, 36,…,136) 3+11j =5 (mod 13) 11j=5-3=2 è j=2 x 6=12 [o -1] 6 è inverso di 11: 6 x 11=66=13 x 5+1=1 (mod 13)

x=3+11 x 12=3+132=135 [oppure -8=3-11x1] [verifica 135=13x10+5=11x12+3 oppure -8=5-13=3-11]

5


Esercizio

Esercizio: In Zn n=11 x 13=143 Z143 Risolvere: 2x= 3 (mod 11) x=5 (mod 13) Il sistema è compatibile perché (11,13)=1 e (2,11)=1. 6 . 2 x =6 . 3 (mod 11); x = 7 (mod 11); x’=7 +11j con j=0,1,…, 12; (7, 18, 29, …,139) 7+11j =5 (mod 13) 11j=5-7=-2=11; 11 j=11; j=1 6 . 11=66=13 . 5+1=1 (mod 13) X=7+11 . 1=18 verifica: 2 . 18=36=11 . 3+3, 18=13+5)

6


Esercizio

Esercizio: In Zn n=6 x 13=78 Z78 Risolvere: 2x= 4 (mod 6) ó (x=2 (mod 6) e x=5 (mod 6)) x=5 (mod 13) Il sistema è compatibile perché (6,13)=1 e (2,6)=(4,6)=2. x=2+3l (mod 6) [3=6/2, l=0,1] x’=2+3l +6j con j=0,1,…,12; (2+3l, 8+3l,…,74+3l) 2+3l+6j =5 (mod 13) 6j=5-2-3l=3-3l; 6 11 j=33-33l; 66 j=7(1-l); j=7(1-l). X=2+3l+6 (1-l)7=2+3l+42(1-l)=44+39l cioè 44 e 5 [cioè 5 in Z39] verifica: 2 . 5=10=4+6 (mod 6); 2 44=88=4 +6 (14)=4+84 (mod 6)

verifica: 5=5 (mod 13); 44=5+39 =5+3 . 13 (mod 13).

7


Molteplicità Sistema diofanteo

Dato un sistema di k equazioni diofantee a due a due compatibili e risolubili. Quante sono le soluzioni? Se l’equazione i-esima [ai x=bi] ha di soluzioni allora le soluzioni sono in totale: #sol= d1d2d3...dn-1dn

In cui di è il MCD tra il coefficiente lineare della i-esima equazione ai e la dimensione dell’anello corrispondete ni : di=(ai,ni).

8


I numeri primi sono infiniti

In genere con p indichiamo un numero primo p.

I numeri primi sono infiniti (numerabili). Dim (per assurdo): se fossero finiti si potrebbero numerare con i primi m numeri ed ordinare: Lista ordinata: p1,p2 … pm-1, pm. pm è il più grande.

Il numero p= (p1p2 … pm-1pm)+1 è primo rispetto a tutti i primi (resto 1) ed è diverso da tutti loro; quindi i primi sono infiniti.

9


Anelli primali

Hp: p primo: (p,k)=1 Zp ={1,2,…,p-1} Th Zp è un campo Dim: [ricordiamo che 0<k<p-1 , k≠0 forma gruppo] •  Tutti gli Zn sono anelli. •  Tutti i numeri non nulli minori di p sono primi con

p e quindi hanno un inverso. •  Tutti i numeri non nulli formano un gruppo

abeliano rispetto al prodotto. Quindi Zp è un campo. [Nota Z*p posside p-1 elementi, non p]

10


Teorema di Fermat

11

Il primo teorema che dimostreremo è denominato “Piccolo teorema di Fermat” in omaggio ad un altro dei padri della teoria dei numeri che lo enunciò e dimostrò per primo “Dato un numero primo p, per ogni naturale n: np=n (mod p)” np=n + kp (scrittura nei naturali)

Pierre de Fermat 1601-‐1665


Potenze primali

Th”Dato un numero primo p, per ogni n: np=n” Dim: (per induzione su n) (1)p=1 (Caso n=1)

(Ricorsione)

12

(n+1)p = np +pk!

"#$

%&

k=1,p−1∑ (n)k +1

!

"##

$

%&&mod p( )

= np +1= n+1

pk!

"#$

%&=

p!k!(p− k)!

=p(p−1)...(p− k +1)k(k −1)...(2)1

pk!

"#$

%&mod( p)

=p!

k!(p− k)!!

"#

$

%&mod( p )

=p(p−1)...(p− k +1)k(k −1)...(2)1

!

"#

$

%&mod( p )

= 0


Potenze in ZP

Se a è primo con p: (a,p)=1, ap-1=1

Dim: esiste inv(a) ap=a; Inv(a)ap=inv(a) a; Inv(a)ap=1; Inv(a)ap=inv(a) a ap-1 =ap-1

ap-1=1

13


Potenze

In Zn (e Z*n) le potenze NON sono una operazione interna: Il numero n è un rappresentante dello 0 in Zn,ma an non è a0=1 In generale se b+c>n-1 ab+c non è ab+c-n, quindi l’operazione dipende dal rappresentante.

14


Dopo Fermat: Eulero

•  Eulero è uno dei fondatori della teoria dei numeri

•  Vedremo molti dei risultati che portano il suo nome

15

Leonhard Euler Basilea 1707 San Pietroburgo1783


Quanti numeri hanno inverso in Zn

•  Solo i numeri primi con n posseggono un inverso in Zn. •  Quanti sono? Chiamiamo questo numero “Funzione di Eulero” φ(n) •  Sia n=n1 n2 ed (n1 ,n2) =1. Se a è primo con n, allora è primo con n1

ed n2.

•  I numeri in Zn primi con n1 sono quelli che modulo n1 sono primi con n1 (perché il resto, il dividendo ed il divisore hanno lo stesso MCD). x=1,…, n1 -1 (mod n1) tutti i numeri primi con n1 [φ(n1) eq. Diverse] x=1,…, n2 -1 (mod n2) tutti i numeri primi con n2 [φ(n2) eq. Diverse]

•  Per il teorema cinese dei resti in Zn1 n2=Zn esiste uno ed un solo numero che sodisfa le due equazioni (che sono .

•  Quindi ci sono φ(n1) φ(n2) sistemi diversi e quindi x coprimi con n, minori di n. φ(n1 n2) =φ(n1) φ(n2)

16


Quanti numeri sono primi con pk?

•  Quanti sono tutti i numeri primi con una potenza di un primo n=pk?

Sono tutti tranne i multipli di p. I multipli di p sono pk/p=pk-1 [uno ogni p numeri] φ(pk)= tutti i pk tranne i multipli di p φ(pk)= pk-pk-1=pk-1(p-1)

17


I numeri primi con n

Data la fattorizzazione unica: n=(p1) h1 (p2) h2 …. (pm) hm n=((p1) h1 )n2=n1 n2 [n1=(p1) h1 ; n2=(p2) h2 …. (pm) hm] I numeri minori di n primi con esso sono quindi: φ(n)=φ(n1) φ(n2)=φ ((p1) h1) φ(n2)=(p1) h1

-1(p1-1) φ(n2)

E iterando: φ(n)=(p1) h1

-1(p1-1) (p2) h2-1(p2-1) …. (pm) hm—1(pm-1)

18


Messaggio

•  Abbiamo risolto alcuni sistemi diofantei con il teorema dei resti cinese.

•  Abbiamo visto alcune identità valide per numeri primi comunque grandi.

Le trasformazioni per cifrare le sequenze in chiaro si riducono spesso ad operazione numeriche, tipicamente potenze o polinomi, sui numeri che le rappresentano in Zn. I teoremi dimostrati ci mostrano che esistono delle periodicità.

19

Agenda -...

Documents

Transcript of Agenda -...