Funzione φ di Eulero

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Funzione phi di Eulero)
Vai alla navigazione Vai alla ricerca
Disambiguazione – "Funzione di Eulero" rimanda qui. Se stai cercando altri significati, vedi Eulero (disambigua).
I primi mille valori di

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
  1. ^ (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.
  2. ^ 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.
  • 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]

Altri progetti

[modifica | modifica wikitesto]

Collegamenti esterni

[modifica | modifica wikitesto]
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica