Eulero, funzione toziente di
Eulero, funzione toziente di in teoria dei numeri, fornisce il numero degli interi positivi minori di n che sono coprimi rispetto a n, cioè che non hanno fattori primi comuni [...] con n. È indicata con φ(n), essendo n ∈ N. Per esempio, i numeri minori di 20 che sono coprimi con 20 sono 1, 3, 7, 9, 11, 13, 17,19, per cui φ(20) = 8. Se p è primo, allora φ(p) = p − 1. Se n = pm, allora ...
Leggi Tutto
indicatore
indicatore particolare funzione φ(n) che, per ogni intero positivo n, fornisce il numero degli interi positivi non superiori a n e primi con n (interi di Eulero-Gauss). L’indicatore è, quindi, [...] un altro nome per la funzione toziente di → Eulero. Mediante l’indicatore è possibile risolvere la congruenza lineare nell’incognita x, ax = b (mod n), essendo a e b due interi qualsiasi: se a è primo con n, sono soluzioni tutti e soli i numeri del ...
Leggi Tutto
Eulero-Fermat, teorema di
Eulero-Fermat, teorema di in teoria dei numeri, stabilisce che se a e b sono due numeri coprimi (vale a dire privi di fattori in comune), allora vale la relazione aφ(b) ≡ 1 [...] (mod b), dove φ indica la funzione toziente di Eulero (→ congruenza modulo n). Il teorema di Eulero-Fermat generalizza il piccolo teorema di → Fermat. ...
Leggi Tutto
numeri primi, funzione enumerativa dei
numeri primi, funzione enumerativa dei in teoria dei numeri, funzione, indicata con il simbolo π (n), che associa a un numero naturale n il numero di numeri primi [...] non superiori a esso. L’andamento della funzione enumerativa dei numeri primi è oggetto del teorema dei numeri primi (→ numeri primi, teorema dei; → Eulero, funzione toziente di). ...
Leggi Tutto
funzione generatrice
funzione generatrice della successione {cn(z)}, è una funzione w(z, t) che ammetta lo sviluppo di → Maclaurin
La funzione generatrice delle partizioni di un insieme di n elementi [...] funzioni aritmetiche è tuttavia di solito definita diversamente, utilizzando delle serie di → Dirichlet, come la funzione
Per esempio, la funzione toziente di → Eulero è generata da
e la funzione di → Möbius è generata da
dove con ζ(s) si è ...
Leggi Tutto
Fermat, piccolo teorema di
Fermat, piccolo teorema di in algebra, stabilisce che, se p è un numero primo, allora per ogni numero intero a vale la congruenza ap ≡ a(modp). In modo equivalente, il teorema [...] teorema di Eulero-Fermat: se a e b sono numeri coprimi, allora aφ(b) ≡ 1 (modb), dove φ(b) è la funzione toziente di Eulero. Il piccolo teorema di Fermat permette di stabilire un importante test di non primalità, detto test di Fermat (→ Fermat, test ...
Leggi Tutto
Farey, successione di
Farey, successione di successione indicata con Fn formata dalle frazioni dell’intervallo [0, 1] aventi un denominatore non superiore a un intero n fissato, detto ordine della successione, [...] , se, una volta ridotto ai minimi termini, il denominatore risulta non superiore a n + 1. Il numero di elementi di Fn è dato da
dove φ(k) è la funzione toziente di Eulero. La successione di Farey è a volte impropriamente chiamata serie di Farey. ...
Leggi Tutto
Mobius, funzione di
Möbius, funzione di funzione aritmetica µ(n) che a un numero naturale n associa il valore (−1)k se n ha k fattori primi tutti distinti e associa il valore 0 se n ha fattori primi [...] questioni di teoria dei numeri. La trasformata di Möbius di una funzione ƒ(n) è la funzione
l’inversione di tale trasformazione si ottiene dalla formula
Per esempio, n è la trasformata di Möbius della funzione toziente di → Eulero φ(n), e quindi ...
Leggi Tutto
numeri, teoria dei
numeri, teoria dei settore della matematica che ha per oggetto i numeri interi e le entità matematiche dotate di proprietà formali analoghe a quelle degli interi. Sono esempi di questioni [...] de Fermat (→ Fermat, numero di; → Fermat, piccolo teorema di; → Fermat, ultimo teorema di) e, successivamente, con Eulero, la cui funzione toziente fornisce il numero degli interi positivi minori o uguali a n che non hanno fattori primi comuni con n ...
Leggi Tutto