Funzione φ di Eulero

Da Wikipedia, l'enciclopedia libera.
bussola Disambiguazione – "Funzione di Eulero" rimanda qui. Se stai cercando altri significati, vedi Eulero (disambigua).
I primi mille valori di \varphi

In matematica, la funzione φ di Eulero o semplicemente funzione di Eulero o totiente, è una funzione definita, per ogni intero positivo n, come il numero degli interi compresi tra 1 e n che sono coprimi con n. Ad esempio, \varphi(8)= 4 poiché i numeri coprimi di 8 sono quattro: 1, 3, 5, 7. Deve il suo nome al matematico svizzero Eulero, che per primo la descrisse.

La funzione \varphi(n) è una funzione molto importante nella teoria dei numeri, principalmente perché è la cardinalità del gruppo moltiplicativo degli interi di modulo n, più precisamente è l'ordine del gruppo moltiplicativo dell'anello \mathbb{Z}/n\mathbb{Z} (vedere aritmetica modulare). Questo fatto, unito con il teorema di Lagrange, dimostra il teorema di Eulero: se a è un numero coprimo con n, allora

a^{\varphi(n)}\equiv 1\mod n

Moltiplicatività[modifica | modifica wikitesto]

La funzione φ di Eulero è moltiplicativa: per ogni coppia di interi a e b tali che MCD(a, b)=1 si ha

\varphi(ab)=\varphi(a)\varphi(b)

Questo fatto può essere dimostrato in molti modi: ad esempio, si può osservare che un numero è coprimo con ab se e solo se è coprimo sia con a che con b. Infatti, dato un x coprimo con ab, questo non ha fattori in comune con ab, e quindi non ha fattori in comune né con a né con b; viceversa, se x è coprimo con a e con b, ed esistesse un primo p che divide sia ab che x, p dovrebbe dividere, per il lemma di Euclide, almeno uno tra a e b, e quindi x non può esser coprimo con entrambi.

Una volta dimostrato questo, si osserva che ogni coppia (y, z), con y\in\mathbb{Z}_a e z\in\mathbb{Z}_b corrisponde ad uno ed un solo elemento w\in\mathbb{Z}_{ab} (o, per essere più formali, che esiste un isomorfismo tra gli anelli \mathbb{Z}_a\times\mathbb{Z}_b e \mathbb{Z}_{ab}). Quindi il numero di elementi coprimi con ab è uguale a quello delle coppie (y, z) dove y è coprimo con a e z con b.

Per definizione i primi sono \varphi(a) e i secondi \varphi(b), e quindi in definitiva ci sono \varphi(a)\varphi(b) elementi coprimi con ab che è per definizione il valore \varphi(ab)

Calcolo della funzione[modifica | modifica wikitesto]

Un'espressione per la funzione è la seguente:

\varphi(n)=n\cdot \left[\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_r}\right)\right] = 
n \prod_{p\mid n} \left(1-\frac{1}{p}\right)

dove gli p_{i} sono tutti i primi che compongono la fattorizzazione di n.

Dimostrazione[modifica | modifica wikitesto]

Mostriamo innanzitutto che, se p è un numero primo, allora  \varphi(p^k)= (p-1) p^{k-1} per ogni k > 0.

Per fare ciò, troviamo tutti i numeri m minori o uguali a p^k per i quali MCD(p^k,m) \ne \ 1. Ciò equivale a dire che m deve avere dei fattori in comune con p^k. Ma p è primo, quindi se m ha dei fattori in comune con p, questi devono essere multipli di una potenza di p. Quindi tutti i possibili valori di m sono p, 2p, 3p, \ldots , p^{k-1} \cdot p. Questi numeri sono p^{k-1}, e sono tutti i numeri che non sono primi con p^k. Tutti i numeri minori o uguali a p^k sono p^k, quindi i numeri primi con p^k minori di p^k sono i restanti p^k-p^{k-1}.

Quindi \varphi(p^k)= p^k - p^{k-1} = (p-1) p^{k-1}

Utilizzando il teorema fondamentale dell'aritmetica possiamo fattorizzare qualsiasi numero n in un prodotto di numeri primi elevati ad una certa potenza:

n = p_{1}^{k_{1}} p_{2}^{k_{2}} \ldots p_{r}^{k_{r}}

dove i p_{i} sono numeri primi distinti, e ogni r_{i} > 0

Quindi \varphi(n)= \varphi(p_{1}^{k_{1}} p_{2}^{k_{2}} \ldots p_{r}^{k_{r}} )

Ora, poiché \varphi è moltiplicativa possiamo espandere la funzione:

\varphi(n)=\varphi(p_{1}^{k_{1}}) \varphi(p_{2}^{k_{2}}) \ldots \varphi(p_{r}^{k_{r}})=p_1^{k_1-1}(p_1-1)\cdot p_2^{k_2-1}(p_2-1)\cdots p_r^{k_r-1}(p_r-1)

(La funzione è moltiplicativa tra due numeri se e solo se essi sono primi tra loro. Nel nostro caso, i numeri p_{i} sono tutti primi, e quindi primi tra loro)

La formula può essere riscritta in una forma più compatta:

\varphi(n)=n\cdot \left[\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_r}\right)\right] = 
n \prod_{p\mid n} \left(1-\frac{1}{p}\right)

Andamento asintotico[modifica | modifica wikitesto]

La scrittura prima trovata permette inoltre di dimostrare che i valori della funzione φ possono essere arbitrariamente piccoli rispetto ad n (cioè il rapporto \varphi(n)/n è minore di qualunque \epsilon per qualche valore di n): estendendo infatti il prodotto a tutti i primi, si ottiene

\frac{p_1-1}{p_1}\frac{p_2-1}{p_2}\cdots=\left[\frac{p_1}{p_1-1}\cdot\frac{p_2}{p_2-1}\cdots\right]^{-1}

Quella tra parentesi è la scrittura del prodotto di Eulero della funzione zeta di Riemann per s=1, cioè la somma

\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots

ovvero la serie armonica, che diverge. Quindi il suo inverso è 0, e la successione

\frac{\varphi(n)}{n}

diventa arbitrariamente vicina a 0.

Altre proprietà[modifica | modifica wikitesto]

  • Il numero φ(n) è anche pari al numero di generatori del gruppo ciclico Cn. Da ciascun elemento di Cn si può generare un sottogruppo ciclico Cd dove d divide n (la notazione è d|n), ottenendo:
\sum_{d\mid n}\varphi(d)=n

dove la somma è estesa a tutti i divisori d di n.

Si può ora utilizzare la funzione di inversione di Möbius per invertire questa somma e ottenere un'altra formula per la φ(n):

\varphi(n)=\sum_{d\mid n} d \cdot \mu\left({n\over d}\right)

dove \mu è l'usuale funzione di Möbius definita sugli interi positivi.

  • Abbiamo inoltre che, se n è un numero primo:
\varphi(n) = n - 1

Dato che, ovviamente, ogni numero minore di n gli è coprimo, essendo n primo.

  • Esiste una sequenza di valori di n tale che
\varphi(n) = \varphi(n+1)

i primi sono 1, 3, 15, 104, 164, 194, 255, 495, 584, 975, ... (sequenza A001274 dell'OEIS).

  • Esiste un solo numero n < 10^{10} tale che
\varphi(n) = \varphi(n+1) = \varphi(n+2)

e si tratta di 5186, per il quale si ha infatti

\varphi(5186) = \varphi(5186+1) = \varphi(5186+2) = 2^5 \cdot 3^4
  • Esiste una progressione aritmetica di ragione 30 composta da sei numeri, che generano tutti lo stesso valore di φ:
\varphi(583200) = \varphi(583230) = \varphi(583260) = \,
\varphi(583290) = \varphi(583320) = \varphi(583350) = \,
 = 155520 = 2^7 \cdot 3^5 \cdot 5
  • a\mid b implica \varphi(a)\mid\varphi(b)
  • \varphi(n) è pari per n \geq 3. Inoltre, se n ha r fattori primi distinti dispari, allora 2^r \mid \varphi(n)

Funzione generatrice[modifica | modifica wikitesto]

Le due funzioni generatrici presentate qui sono entrambe conseguenze del fatto che

\sum_{d|n} \varphi(d) = n.

Una serie di Dirichlet che genera la φ(n) è

\sum_{n=0}^{\infty} \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}

dove \zeta è la funzione zeta di Riemann. Ciò deriva da quanto segue:

\zeta(s) \sum_{f=1}^\infty \frac{\varphi(f)}{f^s} = \left(\sum_{g=1}^\infty \frac{1}{g^s}\right)\left(\sum_{f=1}^\infty \frac{\varphi(f)}{f^s}\right)
\left(\sum_{g=1}^\infty \frac{1}{g^s}\right) \left(\sum_{f=1}^\infty \frac{\varphi(f)}{f^s}\right) = \sum_{h=1}^\infty \left(\sum_{fg=h} 1 \cdot \varphi(g)\right) \frac{1}{h^s}
\sum_{h=1}^\infty \left(\sum_{fg=h} \varphi(g) \right) \frac{1}{h^s} = \sum_{h=1}^\infty \left(\sum_{d|h} \varphi(d) \right) \frac{1}{h^s}
\sum_{h=1}^\infty \left(\sum_{d|h} \varphi(d) \right) \frac{1}{h^s} =\sum_{h=1}^\infty\frac{h}{h^s}
\sum_{h=1}^\infty \frac{h}{h^s} = \zeta(s-1).

La funzione generatrice di una serie di Lambert è

\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n}= \frac{q}{(1-q)^2}

che converge per |q| < 1. Ciò deriva da

\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n} =
\sum_{n=1}^{\infty} \varphi(n) \sum_{r=1}^{\infty} q^{rn}

che è


\sum_{k=1}^{\infty} q^k \sum_{n|k} \varphi(n) =
\sum_{k=1}^{\infty} k q^k = \frac{q}{(1-q)^2}.

Disuguaglianze[modifica | modifica wikitesto]

Alcune disuguaglianze riguardanti la funzione \varphi sono:


\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}}
per n > 2, dove γ è la costante di Eulero-Mascheroni,[1]

\varphi(n) \ge \sqrt{\frac {n} {2} }
per n > 0,

e


\varphi(n) \ge \sqrt{n}\text{ for } n > 6.

Se n è composto abbiamo


\varphi(n) \le n-\sqrt{n}

Per ogni numero pari 2n, dove 2n non è della forma 2k, abbiamo


\varphi(2n) \le n-1

Se invece 2n è pari e della forma 2k, abbiamo


\varphi(2n) = n

Per valori di n arbitrariamente grandi, si avrà

\liminf \frac{\varphi (n)}{n}=0 \mbox{ e } \limsup \frac{\varphi (n)}{n}=1.

Un paio di disuguaglianze che combinano la funzione \varphi con la funzione \sigma sono:


\frac {6 n^2}{\pi^2} < \varphi(n) \sigma(n) < n^2
\mbox{ per } n>1.

Alcuni valori della funzione[modifica | modifica wikitesto]

\varphi(n) 0 1 2 3 4 5 6 7 8 9
0+   1 1 2 2 4 2 6 4 6
10+ 4 10 4 12 6 8 8 16 6 18
20+ 8 12 10 22 8 20 12 18 12 28
30+ 8 30 16 20 16 24 12 36 18 24
40+ 16 40 12 42 20 24 22 46 16 42
50+ 20 32 24 52 18 40 24 36 28 58
60+ 16 60 30 36 32 48 20 66 32 44
70+ 24 70 24 72 36 40 36 60 24 78
80+ 32 54 40 82 24 64 42 56 40 88
90+ 24 72 44 60 46 72 32 96 42 60

Note[modifica | modifica wikitesto]

  1. ^ E. Bach e J. Shallit, Theorem 8.8.7 in Algorithmic Number Theory, vol. 1, Cambridge, MA, MIT Press, 1996, p. 512, ISBN 0-262-02405-5.

Bibliografia[modifica | modifica wikitesto]

  • Tom M. Apostol (1976): Introduction to Analytic Number Theory, Springer-Verlag, New York. ISBN 0-387-90163-9, (Chapter 2)
  • H. Davenport, Aritmetica superiore, Zanichelli, Bologna, 1994, ISBN 88-08-09154-6 - Capitolo II.4

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica