Gregorio D’Agos,no TVG
Agenda
Correggeremo esercizi in sospeso Esercitazione sui sistemi di equazioni diofantee.
1
Gregorio D’Agos,no TVG
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
"
#$
%
&'
Gregorio D’Agos,no TVG
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
Gregorio D’Agos,no TVG
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
Gregorio D’Agos,no TVG
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
Gregorio D’Agos,no TVG
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
Gregorio D’Agos,no TVG
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
Gregorio D’Agos,no TVG
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
Gregorio D’Agos,no TVG
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
Gregorio D’Agos,no TVG
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
Gregorio D’Agos,no TVG
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
Gregorio D’Agos,no TVG
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
Gregorio D’Agos,no TVG
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
Gregorio D’Agos,no TVG
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
Gregorio D’Agos,no TVG
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
Gregorio D’Agos,no TVG
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
Gregorio D’Agos,no TVG
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
Gregorio D’Agos,no TVG
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
Gregorio D’Agos,no TVG
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
Top Related