eulerPhi

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

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 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

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