Funzione φ di Eulero

funzione matematica
Disambiguazione – "Funzione di Eulero" rimanda qui. Se stai cercando altri significati, vedi Eulero (disambigua).

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.

I primi mille valori di

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

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

Un'espressione per la funzione è la seguente:

 

dove i   sono tutti i primi che compongono la fattorizzazione di n.

Dimostrazione modifica

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

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

  • 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

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

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

  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

  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.

Bibliografia modifica

  • 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

Altri progetti modifica

Collegamenti esterni modifica

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