eulerPhi

Euler phi function

Syntax

p = eulerPhi(n)

Description

p = eulerPhi(n) evaluates the Euler phi function or (also known as the totient function) for a positive integer n.

Examples

Multiplicative Property of Euler Phi Function

Compute the Euler phi function $$\varphi (n)$$ for the integer $$n=35$$.

p = eulerPhi(35)

p = 
24

The Euler phi function satisfies the multiplicative property $$\varphi (xy)=\varphi (x)\varphi (y)$$ if the two integers $$x$$ and $$y$$ are relatively prime (also known as coprime). The integer factorization of 35 is 7 and 5, which are relatively prime. Show that $$\varphi (35)$$ satisfies the multiplicative property.

Calculate $$\varphi (x)$$ and $$\varphi (y)$$ for the two factors.

px = eulerPhi(7)

px = 
6

py = eulerPhi(5)

py = 
4

Verify that px and py satisfy the multiplicative property.

p = px*py

p = 
24

Euler's Product Formula

If a positive integer $$n$$ has prime factorization $$n=p_1^{k_1}{p}_2^{k_2}\dots p_r^{k_r}$$ with distinct prime factors $$p_1,p_2,\dots ,p_r$$, then the Euler phi function satisfies the product formula

$$\varphi (n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots (1-\frac{1}{p_r})$$.

The integer $$n=36$$ has distinct prime factors $$2$$ and $$3$$. Show that $$\varphi (36)$$ satisfies the Euler's product formula.

Declare $$36$$ as a symbolic number and evaluate $$\varphi (36)$$.

n = sym(36)

n = $$36$$

p = eulerPhi(n)

p = $$12$$

List the prime factors of $$36$$.

f_n = factor(n)

f_n = $$\left(\begin{array}{cccc}2& 2& 3& 3\end{array}\right)$$

Substitute the prime factors $$2$$ and $$3$$ into the product formula.

p_product = n*(1-1/2)*(1-1/3)

p_product = $$12$$

Euler's Theorem

Euler's theorem states that $$a^{\varphi (n)}\equiv 1(modn)$$ if and only if the two positive integers $$a$$ and $$n$$ are relatively prime. Show that the Euler phi function $$\varphi (n)$$ satisfies Euler's theorem for the integers $$a=15$$ and $$n=4$$.

a = 15;
n = 4;
isCongruent = powermod(a,eulerPhi(n),n) == mod(1,n)

isCongruent = logical
   1

Confirm that a and n are relatively prime.

g = gcd(a,n)

g = 
1

Mean Value of Euler Phi Function Results

Calculate the Euler phi function $$\varphi (n)$$ for the integers $$n$$ from 1 to 1000.

P = eulerPhi(1:1000);

Find the mean value of $$\varphi (n)/n$$.

Pave = mean(P./(1:1000))

Pave = 
0.6082

Input Arguments

n — Input

number | vector | matrix | array | symbolic number | symbolic array

Input, specified as a number, vector, matrix, array, symbolic number, or symbolic array. The elements of n must be positive integers.

Data Types: single | double | sym

More About

Euler Phi Function

The Euler phi function $$\varphi (n)$$ computes the number of integers between 1 and n that are relatively prime (also known as coprime) to n. Two integers are relatively prime if there is no integer greater than one that divides them both. In other words, their greatest common divisor is one.

References

[1] Redmond, D. Number Theory: An Introduction to Pure and Applied Mathematics. New York: Marcel Dekker, 1996.

Version History

Introduced in R2020a