EulerPhi

EulerPhi[n]

gives the Euler totient function .

Details

  • EulerPhi is also known as the Euler totient function or phi function.
  • Integer mathematical function, suitable for both symbolic and numerical manipulation.
  • Typically used in cryptography and in many applications in elementary number theory.
  • EulerPhi[n] counts positive integers up to n that are relatively prime to n.
  • For a number with a unit and primes, EulerPhi[n] gives .

Examples

open allclose all

Basic Examples  (2)

Compute the Euler totient function of 10:

Plot the sequence:

Scope  (9)

Numerical Manipulation  (4)

Compute using integers:

Compute for large arguments:

EulerPhi threads over lists:

TraditionalForm formatting:

Symbolic Manipulation:  (5)

Solve equations involving EulerPhi:

Use FullSimplify with EulerPhi:

Use FunctionExpand with EulerPhi:

FindSequenceFunction can recognize the EulerPhi sequence:

DirichletTransform:

Applications  (9)

Basic Applications  (4)

Find integers n such that :

Length of the nth-order FareySequence can be expressed in terms of EulerPhi:

Power series of the generating function for GCD:

Count the number of primes using EulerPhi:

Number Theory  (5)

Model Fleck's totient function:

reproduces the Euler totient function:

Generalizations and closed forms:

Plot the cumulative sum of EulerPhi:

Compare with an asymptotic approximation:

First several -s where the difference sum_(n=1)^kTemplateBox[{n}, EulerPhi]-3 k^2/pi^2 is negative:

The probability that two randomly chosen positive integers less than x are relatively prime:

Compare with the asymptotic limit:

Build RSA-like encryption scheme. Start with the modulus:

Find the universal exponent of the multiplication group modulo n:

Private key:

Public key:

Encrypt a message:

Decrypt it:

Number of cyclic necklaces of length n that can be formed with b types of beads:

Properties & Relations  (11)

EulerPhi is non-negative:

EulerPhi is a multiplicative function:

For any prime number p and natural number r, ϕ(pr)=pr-pr-1:

Similarly, EulerPhi[n]==np|n(1-1/p) where p is prime:

Alternatively, EulerPhi[n]==nk|nMoebiusMu[k]/k:

CarmichaelLambda divides EulerPhi:

When n is a prime power, they are equal:

Show that ϕ(d)=n:

For a Cyclotomic field, the NumberFieldDiscriminant can be found using EulerPhi:

If has a primitive root, then CarmichaelLambda and EulerPhi are the same:

Determine EulerPhi through prime factorization:

For any square-free number n, the totient of n is equal to the product of the totients of each factor of n :

Possible Issues  (1)

Value at 0:

Neat Examples  (4)

Form an absolutely abnormal number as the limit of the following sequence:

Digits of the sixth approximation in various bases:

Iterate the map and display result modulo :

The only 8 solutions of TemplateBox[{x}, PrimePi]=TemplateBox[{x}, EulerPhi]:

Plot of Ulam spiral where numbers are colored based on the values of EulerPhi:

Introduced in 1988
 (1.0)
 |
Updated in 2007
 (6.0)