In pratica il valore li(x) misura l’area sottesa dalla curva della funzione 1/log(t) rispettoall’intervallo [2,x].Anche per tale funzione si può dimostrare che si ha

Lezione del 27 marzo 2009

Nel corso del tempo, i matematici hanno cercato funzioni che “approssimassero” la funzione (x) (che calcola il numero dei primi non superiori al reale positivo x). Il risultato più famoso è il seguente, che si dimostra con metodi analitici (omettiamo la dimostrazione):

Teorema di Hadamard-De La Vallé Poussin.

Considerata la funzione f(x)=x/log(x) (definita per x>0, x1) dove log(x) è il logaritmo neperiano, si ha: ^{lim π(x)}_f(x) ¹

x 





Quindi, per x abbastanza grande, il rapporto “percentuale” ^π(x)_f(x) è abbastanza vicino a 1, e in questo senso f(x)=x/log(x) approssima (x).

Per esempio f(10¹⁴)  3.102.103.442.166, da cui

) f(10

) π(10

14 14

3.102.103.442.166 750.802 3.204.941.

1.033.

Una funzione che approssima ancora meglio (x) è la funzione (definita per x2 e detta “logaritmo integrale”):

li(x) = ^{log(t)1 dt}

x

2

In pratica il valore li(x) misura l’area sottesa dalla curva della funzione 1/log(t) rispetto all’intervallo [2,x].

Anche per tale funzione si può dimostrare che si ha ¹ li(x) lim π(x)

x 



 , ma per esempio:

li(10¹⁴)  3.204.942.065.692

) li(10

) π(10

14 14

3.204.942.065.692 750.802 3.204.941.

 0,9999999

(approssimazione migliore di quella ottenuta con la funzione x/log(x)).

Per x>7 la funzione li(x) sembra approssimare sempre per eccesso (x): con i moderni calcolatori si è arrivati al calcolo delle 2 funzioni per valori di x intorno a 410²², e si è sempre verificato che li(x)>(x). Molti matematici (tra cui Gauss e Riemann) congetturarono che ciò fosse vero per ogni valore x>7, ma Littlewood (1914) dimostrò che la differenza li(x)-(x) cambia segno infinite volte per x che tende a infinito (dimostrazione non costruttiva). Tuttavia non è stato ancora trovato effettivamente un valore di x per cui li(x)< (x). Nel 1933 Skewes dimostrò che il più piccolo di tali x è <₁₀⁽¹⁰³⁴⁾ (un numero con 10³⁴+1 cifre in base 10). Tale maggiorazione è stata nel tempo migliorata: nel 2000 si é dimostrato che il più piccolo di tali x è <1,410³¹⁶ (un numero ancora al di là delle capacità dei calcolatori moderni).

Calcoliamo approssimativamente la probabilità che, scelto casualmente un numero naturale x di n cifre (in base 10), esso sia primo. Si ha 10^n-1x<10ⁿ, quindi i naturali in tale range sono in numero di (10ⁿ-10^n-1), mentre i valori primi nello stesso range sono in numero di (10ⁿ)-(10^n-1); utilizzando l’approssimazione di (x) mediante x/log(x), la probabilità che x sia primo è:

[(10ⁿ)-(10^n-1)]/(10ⁿ-10^n-1)  [(10ⁿ/logⁿ(x))- (10^n-1/log^n-1(x))]/(910^n-1) = (9n-10)/[9n(n-1)log(10)]  1/[nlog(10)].

Tenendo conto che log(10)2,3, la probabilità che un numero x di n cifre, scelto casualmente, sia primo è 1/[2,3n]. Per esempio la probabilità che un numero di 100 cifre sia primo è 1/230: se scegliamo casualmente 230 numeri di 100 cifre, statisticamente dovremmo aspettarci che uno di essi sia primo.

Quindi per trovare un numero primo di un fissato numero n di cifre (in base 10), si può scegliere casualmente un numero di n cifre, sottoporlo a un “test di primalità” e se il test non è superato cambiare la scelta del numero, e così via: statisticamente dovrebbero bastare circa 2,3n tentativi per trovare un numero primo.

Congruenze aritmetiche.

Ricordiamo la teoria delle congruenze aritmetiche.

La nozione di divisore (e simmetricamente quella di multiplo) si estende facilmente dall’insieme N dei numeri naturali all’insieme Z dei numeri interi relativi: dati gli interi relativi a,bZ si dice che a è divisore di b (o che b è multiplo di a) e si scrive ab, se esiste un intero relativo cZ tale che ac=b.

Fissato un naturale m>1 (detto modulo), e dati i numeri interi relativi a,b, diremo che a è congruo b modulo m (e scriveremo ab (mod m)) se m(a-b).

In questo modo definiamo nell’insieme Z degli interi relativi una relazione, detta appunto congruenza modulo m, che è una relazione di equivalenza in quanto soddisfa le proprietà:

- riflessiva (per ogni aZ si ha aa (mod m) perché a-a=0=0m)

- simmetrica (per ogni a,bZ se ab (mod m) si ha a-b=mk con kZ, quindi b-a=m(-k) e si conclude che ab (mod m))

- transitiva ((per ogni a,b,cZ se ab (mod m), e se bc (mod m) si ha a-b=mk, b-c=mh con k,hZ, quindi a-c=m(k+h) e si conclude che ac (mod m))

Per ogni aZ si può allora costruire la classe di equivalenza rappresentata da a (detta classe di congruenza modulo m rappresentata da a):

[a]m = { xZ / xa (mod m) } = { xZ / x-a=km, con kZ } = { xZ / x=a+km, con kZ } (se non vi è possibilità di equivoco sul modulo m, useremo semplicemente il simbolo [a])

Per la teoria generale delle relazioni di equivalenza, dati a,bZ si ha [a]=[b] ab (mod m), e inoltre le classi di congruenza modulo m formano una partizione dell’insieme Z .

Teorema.

Fissato il naturale m>1, le classi di congruenza modulo m distinte sono tutte e sole le seguenti:

[0], [1], ……, [m-1] (*) Dimostrazione:

Le classi (*) sono distinte: se per assurdo fosse [a]=[b] con 0b<a<n, si avrebbe ab (mod m), dunque 0<a-b<m sarebbe un multiplo di m (contraddizione).

Per ogni aZ la classe di congruenza [a] coincide con una delle classi (*): infatti se a>0 allora, dividendo a per m con quoziente q e resto r si ha a=mq+r , a-r=mq, ar (mod m), [a]=[r], con r compreso fra i valori 0,1,…,m-1; se invece a<0 allora, dividendo (-a) per m con quoziente q e resto r si ha -a=mq+r , a-(m-r)=m(-q-1), am-r (mod m), [a]=[m-r], con m-r compreso fra 1,…,m-1 (se r>0) oppure (se r=0) con [a]=[m]=[0].

Poiché 0,1,…,m-1 sono i possibili resti delle divisioni di un numero naturale per m, le classi di congruenza modulo m sono anche dette classi resto modulo m, e il loro insieme è indicato con Zm : per il Teorema precedente si ha Zm = { [0], [1], ……, [m-1] }, e la cardinalità di Zm è uguale al modulo m.

Nella dimostrazione del Teorema, per ogni intero relativo aZ si è costruito un (unico) intero t compreso fra i valori 0,1,…,m-1 tale che [a]=[t] (o equivalentemente at (mod m)): tale t è detto riduzione modulo m dell’intero a ed è indicato con a mod m .

Dato comunque aZ, un algoritmo per il calcolo della sua riduzione modulo m è indicato nella dimostrazione del Teorema: se a>0 la riduzione coincide con il resto r della divisione di a per m, se a<0 la riduzione coincide invece con (m-r) dove r è il resto r della divisione di (-a) per m (se r>0, mentre se r=0 allora la riduzione è 0). In particolare la complessità dell’algoritmo per il calcolo della riduzione modulo m di un numero naturale a è di ordine quadratico nella dimensione dell’input (perché coinvolge una divisione di a per m).

Congruenze di primo grado ad una incognita.

Fissato il modulo m>1 e i numeri naturali a,b, poniamoci il problema di trovare (se esistono) tutti e soli gli interi relativi x tali che axb (mod m) . Diremo anche che tali valori x sono le soluzioni della congruenza axb (mod m) di primo grado nell’incognita x.

Vediamo quando una soluzione x esiste:

Teorema.

Fissati i numeri naturali a,b,m con m>1 si ha, posto d=mcd(a,b):

esiste una soluzione x della congruenza axb (mod m)  d é divisore di b.

Dimostrazione:

(): Se axb (mod m), si ha ax-b=km, con kZ, da cui, essendo da, dm, ovviamente db.

(): Se db, posto dt=b, con tZ, e posto d=mcd(a,m)=az+mw, con z,wZ, si ottiene b=dt=azt+mwt, da cui aztb (mod m), e basta porre x=zt per ottenere una soluzione della congruenza.

Osservazione. Dal punto di vista algoritmico, per verificare se esiste una soluzione della congruenza axb (mod m) basta usare l’algoritmo Euclideo delle divisioni successive per calcolare d=mcd(a,m), e poi eseguire una divisione per verificare se db.

La dimostrazione precedente fornisce anche un algoritmo per il calcolo di una soluzione x (se essa esiste cioè se db): basta moltiplicare t (ottenuto dividendo b per d) per z (coefficiente di a nella espressione del mcd(a,m) come combinazione lineare di a,m, calcolato con l’algoritmo Euclideo esteso). Globalmente la complessità dell’algoritmo per il calcolo della soluzione della congruenza è di ordine polinomiale (come quella di tutti i sottoalgoritmi utilizzati).

La soluzione (se esiste) della congruenza axb (mod m) non è unica, ma è possibile determinare tutte le soluzioni, conoscendone una:

Teorema.

Fissati i numeri naturali a,b,m con m>1, si ha:

se esiste una soluzione x0 della congruenza axb (mod m) , tutte e sole le soluzioni sono i numeri interi relativi x1 tali che x1x0 (mod m/d) (ossia i numeri della classe di congruenza [x0]m/d

rappresentata da x0 modulo m/d).

Dimostrazione:

Sia x1 una soluzione della congruenza.

Allora ax1b (mod m), ax0b (mod m), da cui per transitività ax1ax0 (mod m), ax1-ax0=mk con k intero, (a/d)(x1-x0)=(m/d)k.

Ma per una proprietà del mcd, i numeri a/d, m/d sono coprimi (essendo d=mcd(a,m)). Per una proprietà dei numeri coprimi essendo (m/d)(a/d)(x1-x0) si ha (m/d)(x1-x0) ottenendo infine la tesi x1x0 (mod m/d).

Viceversa sia x1 un intero relativo tale che x1x0 (mod m/d).

Allora x1-x0=km/d, con k intero, ax1-ax0=k(a/d)m, ax1ax0 (mod m).

Ma per ipotesi ax0b (mod m), e per transitività anche ax1b (mod m), dunque anche x1 è soluzione della congruenza.