Don't take life too seriously: it's just a temporary situation

Indice

  1. 1. Pagina principale
  2. 2. Formule
  3. 3. Valori
  4. 4. Iterazioni della funzione

φ(n) è la funzione φ di Eulero, detta anche “toziente”, cioè il numero di interi positivi minori di n che non hanno divisori in comune con n. Per convenzione si conta sempre l’unità, pertanto φ(1) = 1 e φ(p) = p – 1 se p è primo.

 

La funzione fu definita da Eulero nel 1763, ma il grande matematico non le diede subito un nome o un simbolo; solo nel 1784 introdusse la notazione πn, piuttosto infelice, perché suggerisce piuttosto una moltiplicazione per π.

Il simbolo moderno fu introdotto da Gauss nel 1801 in Disquisitiones Arithmeticae e subito accettato, ma la notazione era φn. In seguito si affermò l’uso delle parentesi intorno agli argomenti delle funzioni, anche per evitare confusioni con le moltiplicazioni, e la notazione divenne quella che oggi conosciamo.

Il nome “toziente” si deve a J.J Sylverster (1898) e fu anch’esso rapidamente accettato.

 

La funzione è moltiplicativa e può essere calcolata a partire dalla scomposizione in fattori primi dell’argomento, sapendo che se p è primo, φ(pk) = pkpk – 1: se Scomposizione di n in fattori primi è la scomposizione di n in fattori primi, Formula per il calcolo di φ(n).

 

Alcune proprietà:

φ(n) è pari per n > 2;

φ(n) non è multiplo di 4 se e solo se n è 1, 2, 4 o uguale a pk o 2pk, dove p è un primo della forma 4m + 3;

se n ha k fattori primi distinti, 2k divide φ(n);

φ(n) = n / 2 se e solo se n è una potenza di 2;

se a e n sono primi tra loro, aφ(n) ≡ 1 mod n (teorema di Eulero);

se m divide n, φ(m) divide φ(n);

se m e n non hanno divisori in comune, mφ(n) + nφ(m) ≡ 1 mod mn;

se a è maggiore di 1, n divide φ(an – 1);

se a è maggiore di 1 e n è maggiore di 6 e non multiplo di 4, esiste un intero m ≥ 2n che divide φ(an – 1);

nφ(n) = mφ(m) se e solo se n = m;

la somma dei numeri naturali minori di kn e primi rispetto a n è Somma dei numeri naturali minori di kn e primi rispetto a n e in particolare la somma dei numeri naturali minori di n e primi rispetto a n è Somma dei numeri naturali minori di n e primi rispetto a n, per n > 1 (v. funzione φk).

 

I numeri naturali minori di n e primi rispetto a esso formano un insieme completo di resti modulo φ(n) se e solo se n è primo o è 15; infatti φ(15) = 8, gli 8 interi minori di 15 e primi rispetto a esso sono 1, 2, 4, 7, 8, 11, 13 e 14 e comprendono tutti i possibili residui modulo 8.

 

Se φ(n) / n > φ(m) / m per tutti gli interi m < n, n è primo (Leonidas Alaoglu e Paul Erdös 1944).

 

I sottoinsiemi di numeri naturali minori di n, zero incluso, tali che la loro somma sia un multiplo di n sono Numero dei sottoinsiemi di numeri naturali minori di n tali che la loro somma sia un multiplo di n, dove la somma va calcolata sui divisori dispari di n. Per esempio, nel caso n = 6 ci sono 12 insiemi: l’insieme vuoto, { 0 }, { 1, 5 }, { 0, 1, 5 }, { 1, 2, 3 }, { 0, 1, 2, 3 }, { 1, 2, 4, 5 }, { 0, 1, 2, 4, 5 }, { 2, 4 }, { 0, 2, 4 }, { 3, 4, 5 } e { 0, 3, 4, 5 }, mentre Calcolo del numero dei sottoinsiemi di numeri naturali minori di 6 tali che la loro somma sia un multiplo di 6.

 

Chiamando L(n) il numero di numeri naturali k non superiori a n e primi rispetto a φ(k), Erdös dimostrò nel 1948 che Limite che coinvolge la funzione φ.

 

Se f è una qualsiasi funzione moltiplicativa, tale che f(mn) < f(m)f(n) se MCD(m, n) > 1, dalla definizione della funzione si ricava che Formula per il calcolo di φ(n), perché nella somma i soli termini uguali a 1 sono quelli per i quali k e n sono primi tra loro, mentre i restanti sono uguali a 0. Basandosi su questa proprietà si possono costruire formule a prima vista sorprendenti, come Formula per il calcolo di φ(n) o Formula per il calcolo di φ(n).

 

Nel 1922 Carmichael propose la congettura che se la funzione assume un certo valore, lo assume almeno due volte per due interi distinti, vale a dire che per ogni n esiste un m tale che φ(n) = φ(m).

 

Erdös e Dudley dimostrarono nel 1983 che se φ(n) = k ha m soluzioni per un valore fissato di k, esistono infiniti altri valori di k con lo stesso numero di soluzioni.

 

K. Ford nel 1998 dimostrò la congettura di Sierpiński, vale a dire che tutti i valori superiori a 1 capitano come numeri di occorrenze dei valori della funzione φ. Dalla dimostrazione di Erdös e Dudley segue quindi che per ogni n > 1 vi sono infiniti insiemi di esattamente n interi che hanno lo stesso valore della funzione toziente.

 

Se p, 2p + 1 e 4p + 3 sono primi, φ(φ(x)) = 2p ha esattamente due soluzioni, che sono 3p + 3 e 8p + 6. Per esempio, per p = 5, φ(φ(x)) =10 ha soluzioni x = 23 e x = 46 e φ(x) = 10 ha per soluzioni x = 11 e x = 22 (M.V. Subbarao e L.W. Yip, 1989).

 

Leo Moser fece notare che il valore di nφ(n) permette di determinare n, mentre il valore di nσ(n) no e il valore di nd(n) neppure, perché esistono infinite coppie di interi m e n tali che nσ(n) = mσ(m), in particolare, tutte le coppie m = 12q e n = 14q, con q non divisibile per 2, 3 o 7, e 18d(18) = 27d(27).

 

Paul Erdös dimostrò nel 1948 che al crescere di n i numeri minori di n tali che MCD(n, φ(n)) = 1 tendono a n / (e^γ * log(log(log(n)))).

 

φ(n) divide n solo se i fattori primi di n sono 2, 3 o entrambi; più precisamente gli unici interi per i quali φ(n) divida n sono:

  • 1, perché 1 = φ(1);

  • le potenze di 2, per le quali n = 2φ(n);

  • i numeri della forma 2m3k, con m anche nullo, per i quali n = 3φ(n).

 

Se n è primo, φ(n) = n – 1; D.H. Lehmer avanzò nel 1932 la congettura che per n composto φ(n) non divida n – 1 (v. numeri di Lehmer (II)).

 

Sono anche rari i casi nei quali φ(n) divide n + 1; Lehmer dimostrò che un intero n con questa proprietà:

  • è dispari;

  • non è multiplo di quadrati;

  • ha un numero dispari di fattori primi della forma 4k + 3;

  • se un primo p divide n, n non è divisibile per primi della forma kp + 1;

  • se φ(n) = 3(n – 1), n ha più di 32 fattori primi distinti;

  • per qualsiasi primo p diverso da n + 2, np non ha la stessa proprietà.

Lehmer dimostrò anche che gli unici numeri del genere con meno di 7 fattori primi sono: 2, 3, 15, 255, 65535, 83623935, 4294967295 e 6992962672132095. Non sono stati trovati altri numeri con la stessa proprietà.

 

Gli unici interi n noti per i quali Rapporto tra la somma di φ(k), per k da 1 a n^2, e la somma di φ(k), per k da 1 a n sia intero sono 1, 2, 3, 5 e 6; se ve ne sono altri, sono maggiori di 3000.

 

Paul Erdös chiese per ogni intero positivo n esistano due numeri, non necessariamente primi, p e q, tali che φ(p) + φ(q) = 2n. La risposta è affermativa se è vera la congettura di Goldbach, perché 2(n – 1) sarebbe esprimibile come p + q, con p e q primi e φ(p) + φ(p) = p + q – 2 = 2n (il caso n = 2 si risolve con p = q = 2); è però possibile che l’affermazione di Erdös sia vera anche se la congettura di Goldbach fosse falsa.

Bibliografia

  • Adler, Andrew;  Coury, John E.;  The Theory of Numbers: a Text and Source Book of Problems, Londra, Jones and Bartlett Publishers, 1995.
  • De Koninck, Jean-Marie;  Those Fascinating Numbers, American Mathematical Society, 2009 -

    Un'inesauribile miniera di notizie sugli interi, informazioni e spunti per approfondimenti.

  • Roberts, Joe;  The Lure of the Integers, The Mathematical Association of America, 1992 -

    Una miniera di informazioni sugli interi.

  • Stanley, Richard P.;  Enumerative Combinatorics, Cambridge University Press, vol. I, 1997.
  • Wells, David;  Prime Numbers, John Wiley & Sons, 2005 -

    Una miniera di informazioni sui numeri primi.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.