eulerPhi

Эйлерова функция phi

Синтаксис

Описание

пример

p = eulerPhi(n) выполняет Эйлеровую функцию phi или (также известный как функцию тотиента) для положительного целочисленного n.

Примеры

свернуть все

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

p = eulerPhi(35)
p = 24

Эйлерова функция phi удовлетворяет мультипликативному свойству ϕ(xy)=ϕ(x)ϕ(y) если эти два целых числа x и y являются относительно главными (также известный взаимно-простой). Целочисленная факторизация 35 равняется 7 и 5, которые являются относительно главными. Покажите это ϕ(35) удовлетворяет мультипликативному свойству.

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

px = eulerPhi(7)
px = 6
py = eulerPhi(5)
py = 4

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

p = px*py
p = 24

Если положительное целое число n имеет главную факторизацию n=p1k1p2k2prkr с отличными простыми множителями p1,p2,,pr, затем Эйлерова функция phi удовлетворяет формуле продукта

ϕ(n)=n(1-1p1)(1-1p2)(1-1pr).

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

Объявить 36 как символьное число и оценивают ϕ(36).

n = sym(36)
n = 36
p = eulerPhi(n)
p = 12

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

f_n = factor(n)
f_n = (2233)

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

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

Теорема Эйлера утверждает это aϕ(n)1(modn) если и только если два положительных целых числа a и n являются относительно главными. Покажите, что Эйлеровы phi функционируют ϕ(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 ϕ(n) для целых чисел n от 1 до 1 000.

P = eulerPhi(1:1000);

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

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

Входные параметры

свернуть все

Введите в виде номера, вектора, матрицы, массива, символьного числа или символьного массива. Элементы n должны быть положительные целые числа.

Типы данных: single | double | sym

Больше о

свернуть все

Эйлер Фи Функтион

Эйлерова функция phi ϕ(n) вычисляет количество целых чисел между 1 и n, которые являются относительно главными (также известный взаимно-простыми) к n. Два целых числа являются относительно главными, если нет никакого целого числа, больше, чем то, которое делит их обоих. Другими словами, их наибольший общий делитель является тем.

Ссылки

[1] Редмонд, D. Теория чисел: введение в чистую и прикладную математику. Нью-Йорк: Марсель Деккер, 1996.

Смотрите также

|

Введенный в R2020a
Для просмотра документации необходимо авторизоваться на сайте