About the Project
NIST

Euler totient

AdvancedHelp

(0.001 seconds)

1—10 of 13 matching pages

1: 27.16 Cryptography
To do this, let s denote the reciprocal of r modulo ϕ ( n ) , so that r s = 1 + t ϕ ( n ) for some integer t . (Here ϕ ( n ) is Euler’s totient27.2).) By the Euler–Fermat theorem (27.2.8), x ϕ ( n ) 1 ( mod n ) ; hence x t ϕ ( n ) 1 ( mod n ) . But y s x r s x 1 + t ϕ ( n ) x ( mod n ) , so y s is the same as x modulo n . …
2: 27.2 Functions
27.2.6 ϕ k ( n ) = ( m , n ) = 1 m k ,
27.2.7 ϕ ( n ) = ϕ 0 ( n ) .
The ϕ ( n ) numbers a , a 2 , , a ϕ ( n ) are relatively prime to n and distinct (mod n ). …Note that J 1 ( n ) = ϕ ( n ) . …
Table 27.2.2: Functions related to division.
n ϕ ( n ) d ( n ) σ ( n ) n ϕ ( n ) d ( n ) σ ( n ) n ϕ ( n ) d ( n ) σ ( n ) n ϕ ( n ) d ( n ) σ ( n )
3: 27.3 Multiplicative Properties
27.3.3 ϕ ( n ) = n p | n ( 1 - p - 1 ) ,
27.3.8 ϕ ( m ) ϕ ( n ) = ϕ ( m n ) ϕ ( ( m , n ) ) / ( m , n ) .
4: 27.6 Divisor Sums
27.6.5 d | n | μ ( d ) | ϕ ( d ) = n ϕ ( n ) ,
27.6.6 d | n ϕ k ( d ) ( n d ) k = 1 k + 2 k + + n k ,
5: 27.21 Tables
Glaisher (1940) contains four tables: Table I tabulates, for all n 10 4 : (a) the canonical factorization of n into powers of primes; (b) the Euler totient ϕ ( n ) ; (c) the divisor function d ( n ) ; (d) the sum σ ( n ) of these divisors. …6 lists ϕ ( n ) , d ( n ) , and σ ( n ) for n 1000 ; Table 24. …
6: 27.8 Dirichlet Characters
For any character χ ( mod k ) , χ ( n ) 0 if and only if ( n , k ) = 1 , in which case the Euler–Fermat theorem (27.2.8) implies ( χ ( n ) ) ϕ ( k ) = 1 . There are exactly ϕ ( k ) different characters (mod k ), which can be labeled as χ 1 , , χ ϕ ( k ) . …
27.8.6 r = 1 ϕ ( k ) χ r ( m ) χ ¯ r ( n ) = { ϕ ( k ) , m n ( mod k ) , 0 , otherwise .
7: 27.11 Asymptotic Formulas: Partial Sums
27.11.6 n x ϕ ( n ) = 3 π 2 x 2 + O ( x ln x ) .
27.11.7 n x ϕ ( n ) n = 6 π 2 x + O ( ln x ) .
27.11.9 p x p h ( mod k ) 1 p = 1 ϕ ( k ) ln ln x + B + O ( 1 ln x ) ,
27.11.11 p x p h ( mod k ) ln p p = 1 ϕ ( k ) ln x + O ( 1 ) ,
The prime number theorem for arithmetic progressions—an extension of (27.2.3) and first proved in de la Vallée Poussin (1896a, b)—states that if ( h , k ) = 1 , then the number of primes p x with p h ( mod k ) is asymptotic to x / ( ϕ ( k ) ln x ) as x .
8: 27.5 Inversion Formulas
27.5.4 n = d | n ϕ ( d ) ϕ ( n ) = d | n d μ ( n d ) ,
9: 27.7 Lambert Series as Generating Functions
27.7.4 n = 1 ϕ ( n ) x n 1 - x n = x ( 1 - x ) 2 ,
10: 27.12 Asymptotic Formulas: Primes
27.12.8 li ( x ) ϕ ( m ) + O ( x exp ( - λ ( α ) ( ln x ) 1 / 2 ) ) , m ( ln x ) α , α > 0 ,
where λ ( α ) depends only on α , and ϕ ( m ) is the Euler totient function (§27.2). …