Per ogni reale x>0 si ha (x)log2(log2x)+1

Lezione del 28 marzo 2008

Nell’ambito dello studio della distribuzione dei numeri primi, può essere interessante valutare il numero di primi in un certo intervallo [0,x] della semiretta positiva dell’asse reale. Poniamo, per ogni reale x>0 :

(x)= numero dei primi  x Per esempio (22,3)= {2,3,5,7,11,13,17,19}=8

Non esistono formule algebriche per il calcolo esatto di (x). Per esempio, usando i computers, si è verificato che : (10¹⁴) = 3.204.941.750.802

(i valori massimi attualmente calcolati sono intorno a 10²²).

Sfruttando il Teorema precedente, per (x) possiamo dare un minorante:

Teorema.

Per ogni reale x>0 si ha (x)log2(log2x)+1.

Dimostrazione:

Sia n=log2(log2x)+1: dunque n è il più grande intero tale che nlog2(log2x)+1, o equivalentemente n-1log2(log2x), 2^n-1log2x, ₂^(2n1)x. Nella successione (crescente) dei primi si ha per il teorema precedente p1<p2<….<pn₂^(2n1)x. Poiché vi sono almeno n primi x, si conclude che n(x) e si ha la tesi.

Nota: il minorante log2(log2x)+1 per (x) è molto “debole”, e in generale log2(log2x)+1 è molto più piccolo di (x); per esempio per x=10⁹ si ha log2(log2x)+1=5 ma (x)5x10⁷.

Nel corso del tempo, i matematici hanno cercato funzioni che “approssimassero” (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):

li(x) = log(t)^dt

x 1

2

Anche per tale funzione si ha ^lim _li(x)^{π(x) 1}

x 



 , ma per esempio:

li(10¹⁴)  3.204.942.065.692

) li(10

) π(10

14 14 

065.692 3.204.942.

750.802 3.204.941.

 0,9999999

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.

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).

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).

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.