Funzione φ di Eulero
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/9/9b/EulerPhi.svg/400px-EulerPhi.svg.png)
In matematica, la funzione φ di Eulero o semplicemente funzione di Eulero o toziente, è una funzione definita, per ogni intero positivo , come il numero degli interi compresi tra e che sono coprimi con . Ad esempio, 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 è una funzione molto importante nella teoria dei numeri, principalmente perché è la cardinalità del gruppo moltiplicativo degli interi modulo , più precisamente è l'ordine del gruppo moltiplicativo dell'anello (vedere aritmetica modulare). Questo fatto, unito con il teorema di Lagrange, dimostra il teorema di Eulero: se è un numero coprimo con , allora:
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:
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 sia 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 sia 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 e corrisponde a uno e un solo elemento (o, per essere più formali, che esiste un isomorfismo tra gli anelli e ). 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 e i secondi , e quindi in definitiva ci sono elementi coprimi con ab che è per definizione il valore
Calcolo della funzione
[modifica | modifica wikitesto]Un'espressione per la funzione è la seguente:
dove i sono tutti i primi che compongono la fattorizzazione di n.
Dimostrazione
[modifica | modifica wikitesto]Mostriamo innanzitutto che, se p è un numero primo, allora per ogni .
Per fare ciò, troviamo tutti i numeri m minori o uguali a per i quali . Ciò equivale a dire che m deve avere dei fattori in comune con . 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 . Questi numeri sono , e sono tutti i numeri che non sono coprimi con . Tutti i numeri minori o uguali a sono , quindi i numeri primi con minori di sono i restanti .
Quindi
Utilizzando il teorema fondamentale dell'aritmetica possiamo fattorizzare qualsiasi numero in un prodotto di numeri primi elevati a una certa potenza:
dove i sono numeri primi distinti, e ogni
Quindi
Ora, poiché è moltiplicativa possiamo espandere la funzione:
(La funzione è moltiplicativa tra due numeri se e solo se essi sono primi tra loro. Nel nostro caso, i numeri sono tutti primi, e quindi primi tra loro)
La formula può essere riscritta in una forma più compatta:
Andamento asintotico
[modifica | modifica wikitesto]La scrittura prima trovata permette inoltre di dimostrare che i valori della funzione φ possono essere arbitrariamente piccoli rispetto a n (cioè il rapporto è minore di qualunque per qualche valore di n): estendendo infatti il prodotto a tutti i primi, si ottiene
Quella tra parentesi è la scrittura del prodotto di Eulero della funzione zeta di Riemann per s=1, cioè la somma
ovvero la serie armonica, che diverge. Quindi il suo inverso è infinitesimale, e la successione
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:
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):
dove è l'usuale funzione di Möbius definita sugli interi positivi.
- Abbiamo inoltre che, se n è un numero primo:
Dato che, ovviamente, ogni numero minore di n gli è coprimo, essendo n primo.
- Esiste una sequenza di valori di n tale che
i primi sono 1, 3, 15, 104, 164, 194, 255, 495, 584, 975, ... (sequenza A001274 dell'OEIS).
- Esiste un solo numero tale che
e si tratta di 5186, per il quale si ha infatti
- Esiste una progressione aritmetica di ragione 30 composta da sei numeri, che generano tutti lo stesso valore di φ :
- implica
- è pari per . Inoltre, se n ha r fattori primi distinti dispari, allora
Funzione generatrice
[modifica | modifica wikitesto]Le due funzioni generatrici presentate qui sono entrambe conseguenze del fatto che
Una serie di Dirichlet che genera la φ(n) è
dove è la funzione zeta di Riemann. Ciò deriva da quanto segue:
La funzione generatrice di una serie di Lambert è
che converge per |q| < 1. Ciò deriva da
che è
Disuguaglianze
[modifica | modifica wikitesto]Alcune disuguaglianze riguardanti la funzione sono:
- per n > 2, dove γ è la costante di Eulero-Mascheroni,[1][2]
- per n > 0,
e
Se n è composto abbiamo
Per ogni numero pari 2n, dove 2n non è della forma 2k, abbiamo
Se invece 2n è pari e della forma 2k, abbiamo
Per valori di n arbitrariamente grandi, si avrà
- e
Un paio di disuguaglianze che combinano la funzione con la funzione sono:
Alcuni valori della funzione
[modifica | modifica wikitesto]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]- ^ (EN) Eric Bach, Jeffrey Outlaw Shallit e Professor Jeffrey Shallit, Algorithmic Number Theory: Efficient algorithms, MIT Press, 1996, ISBN 978-0-262-02405-1. URL consultato il 16 febbraio 2022.
- ^ Eric Library Genesis e Jeffrey Outlaw Shallit, Algorithmic number theory, Cambridge, Mass. : MIT Press, 1996, ISBN 978-0-262-02405-1. URL consultato il 16 febbraio 2022.
Bibliografia
[modifica | modifica wikitesto]- Luca Barbieri Viale, Teorema 4.27, Che cos'è un numero ? Raffaello Cortina, 2013, ISBN 978-88-6030-604-3
- 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]- Aritmetica modulare
- Interi coprimi
- Nontotiente
- Noncototiente
- Funzione aritmetica
- Teorema di Eulero (aritmetica modulare)
- Campo ciclotomico
Altri progetti
[modifica | modifica wikitesto]Wikimedia Commons contiene immagini o altri file sulla funzione φ di Eulero
Collegamenti esterni
[modifica | modifica wikitesto]- Eulero, funzione toziente di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
- (EN) Euler phi function, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
- (EN) Eric W. Weisstein, Funzione φ di Eulero, su MathWorld, Wolfram Research.
- (EN) Funzione φ di Eulero, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
- (EN) Euler Totient Function, su functions.wolfram.com.
- Kirby Urner, Computing totient function in Python and scheme, (2003)
- JavaScript totient calculator, su www25.brinkster.com. URL consultato il 14 gennaio 2011 (archiviato dall'url originale il 15 giugno 2011).
- Miyata, Daisuke & Yamashita, Michinori, Derived logarithmic function of Euler's function
- Bordellès, Olivier, Numbers prime to q in
- Plytage, Loomis, Polhill Summing Up The Euler Phi Function Archiviato il 23 luglio 2011 in Internet Archive.
- Fabrizio Romano, Python implementation[collegamento interrotto]