Вычислите функцию Euler phi $$\varphi (n)$$ для целого числа $$n=35$$.

p = eulerPhi(35)

p = 24

Функция Euler phi удовлетворяет мультипликативному свойству $$\varphi (xy)=\varphi (x)\varphi (y)$$ если два целых чисел $$x$$ и $$y$$ относительно простые (также известные как общие). Целочисленная факторизация 35 равна 7 и 5, которые являются относительно простыми. Показать, что $$\varphi (35)$$ удовлетворяет мультипликативному свойству.

Вычислить $$\varphi (x)$$ и $$\varphi (y)$$ для двух факторов.

px = eulerPhi(7)

px = 6

py = eulerPhi(5)

py = 4

Проверьте, что px и py удовлетворить мультипликативному свойству.

p = px*py

p = 24

Если положительное целое число $$n$$ имеет простую факторизацию $$n=p_1^{k_1}{p}_2^{k_2}\dots p_r^{k_r}$$ с различными простыми множителями $$p_1,p_2,\dots ,p_r$$, тогда функция Euler phi удовлетворяет формуле продукта

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

Целое число $$n=36$$ имеет различные простые множители $$2$$ и $$3$$. Показать, что $$\varphi (36)$$ удовлетворяет формуле продукта Эйлера.

Объявить $$36$$ как символьное число и вычислить $$\varphi (36)$$.

n = sym(36)

n = $$36$$

p = eulerPhi(n)

p = $$12$$

Перечислите простые множители $$36$$.

f_n = factor(n)

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

Замените простые множители $$2$$ и $$3$$ в формулу продукта.

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

p_product = $$12$$

Теорема Эйлера утверждает, что $$a^{\varphi (n)}\equiv 1(modn)$$ если и только если два положительных целого числа $$a$$ и $$n$$ являются относительно простыми. Покажите, что функция Euler phi $$\varphi (n)$$ удовлетворяет теореме Эйлера для целых чисел $$a=15$$ и $$n=4$$.

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

isCongruent = logical
   1

Подтвердите, что a и n относительно простые.

g = gcd(a,n)

g = 1

Вычислим функцию Euler phi $$\varphi (n)$$ для целых чисел $$n$$ от 1 до 1000.

P = eulerPhi(1:1000);

Найдите среднее значение $$\varphi (n)/n$$.

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

Pave = 0.6082