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

p = eulerPhi(35)

p = 24

Эйлерова функция 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$$, затем Эйлерова функция 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$$

Перечислите простые множители $$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$$ являются относительно главными. Покажите, что Эйлеровы 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

Вычислите Эйлеровую функцию phi $$\varphi (n)$$ для целых чисел $$n$$ от 1 до 1 000.

P = eulerPhi(1:1000);

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

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

Pave = 0.6082