Функция Эйлера. Доказательство

Функция Эйлера, это функция, которая равна количеству натуральных чисел, меньших m и взаимно простых с m. Предполагается, что число 1 взаимно просто со всеми натуральными числами (и с единицею). Обозначается функция Эйлера греческой буквой φ.

Возьмем ряд натуральных чисел до m

1, 2, 3, ..., m.

Определим, сколько в этом ряду чисел, взаимно простых с m. Так как единица взаимно простое с единицею, то

φ(1)=1.

Далее, число 2 взаимно просто с 1, тогда φ(2)=1, число 3 взаимно просто с 1 и 2, тогда φ(3)=2. Продолжая получим: φ(4)=2, φ(5)=4, и т.д.

Сформулируем следующие задачи.

Задача 1. Пусть a₁, a₂, a₃, ...все отличные друг от друга простые множители числа m. Найти число тех чисел, которые не делятся ни на одно из чисел a₁, a₂, a₃, ... .

Более общая задача имеет следующий вид:

Задача 2. Пусть a₁, a₂, a₃, ...взаимно простые числа, которые входят множителями в m. Найти число всех чисел, которые не делятся ни на одно из чисел a₁, a₂, a₃, ... .

Возьмем ряд натуральных чисел до m:

1, 2, 3, ..., m.

(1)

Исключим из ряда (1) все те числа, которые делятся на a₁. Это следующие числа

Их число равно . Исключим эти числа из ряда (1). Тогда останутся

(2)

числа, которые не делятся на a₁. Обозначим множество этих чисел через A₁.

Из чисел ряда A₁ нужно исключить все те числа, которые кратные a₂. Это те числа из ряда (1), которые делятся на a₂ и не делятся на a₁. Числа ряда (1), которые делятся на a₂ следующие:

.

Их количество равно .

Эти числа можно представить в виде ka₂, где k пробегает натуральные числа

.

(3)

Для того, чтобы ka₂ не делился на a₁ необходимо и достаточно, чтобы k не делился на a₁ (т.к. a₁ и a₂ взаимно простые числа). Нужно найти количество чисел из ряда (1), которые делятся на a₁ и исключить их из ряда (3). делится на a₁ т.к. m делится на a₁, m делится на a₂ и m делится на a₁a₂ (a₁, a₂ входят множителями в m). Задача по отношению числа та же, что и задача по отношению числа m, которое мы решили с помощью формулы (2). Из ряда A₁ нужно исключить числа, которые делятся на a₁. Тогда взяв вместо m число получим

.

(4)

(4) число тех чисел ряда A₁, которые не делятся на a₁ или это число тех чисел ряда (1), которые делятся на a₂ и не делятся на a₁.

Учитывая (2) и (4) получим число тех чисел ряда (1), которые не делятся ни на a₁, ни на a₂:

.

(5)

Обозначим множество этих чисел через A₂. Далее удалим из A₂ те числа, которые делятся на a₃. Это те числа из ряда (1), которые делятся на a₃ и не делятся на a₁ и a₂.

Числа ряда (1), которые делятся на a₃ следующие:

.

Их количество равно .

Эти числа можно представить в виде ka₃, где k пробегает натуральные числа

.

(6)

Для того, чтобы ka₃ не делился на a₁ и a₂ необходимо и достаточно, чтобы k не делился на a₁ и a₂ (т.к. a₃ и a₁ а также a₃ и a₂ числа взаимно простые). Нужно найти количество чисел из ряда (1), которые делятся на a₁ и a₂ и исключить из ряда (6). делится на a₁ и a₂, так как m делится на a₁, m делится на a₂ и m делится на a₁a₂a₃ (a₁, a₂, a₃ входят множителями в m). Задача по отношению числа та же, что и задача по отношению числа m, которое мы решили с помощью уравнения (5). Число тех чисел ряда (6), которые не делятся ни на a₁ ни на a₂ (или число тех чисел ряда (1), которые делятся на a₃ и не делятся ни на a₁, ни на a₂):

.

Тогда число тех чисел ряда (1), которые не делятся ни на a₁, ни на a₂, ни на a₃:

.

Обозначим множество этих чисел через A₃. Рассуждая таким образом, заключим, что число A_i тех чисел ряда (1), которые не делятся на a₁, a₂, ..., a_i равно

.

(7)

Мы получили число тех чисел ряда (1), которые не делятся на числа a₁, a₂, ..., a_i. Получим формулу для чисел a₁, a₂, ..., a_i, a_i+1, где a_i+1 также входит множителем в m и взаимно простое с a₁, a₂, ..., a_i.

Чтобы найти число тех чисел ряда (1), которые не делятся на a₁, a₂, ..., a_i+1, нужно из множества (7) исключить числа кратные a_i+1. Это те числа ряда (1), которые не делятся на a₁, a₂, ..., a_i и делятся на a_i+1.

Все числа ряда (1), которые делятся на a_i+1, следующие:

,

то есть это числа ka_i+1, где k=1, 2, ..., m/a_i+1 и для того, чтобы ka_i+1 не делилось на a₁, a₂, ..., a_i необходимо и достаточно, чтобы k не делилось на a₁, a₂, ..., a_i. Поэтому из ряда A_i нужно исключить столько чисел, сколько существует в ряду

чисел, которые не делятся на a₁, a₂, ..., a_i, т.е.

Если исключить эти числа из ряда A_i, то останутся те числа этого ряда, которые не делятся на числа a₁, a₂, ..., a_i+1. Их число равно

Мы доказали следующую теорему:

Теорема 1. Если a₁, a₂, ..., a_q, все различные взаимно простые числа, входящие в m, то число чисел, которые не делятся ни на одно из чисел a₁, a₂, ..., a_q и входящих в ряд m равно:

(8)

Таким образом справедлива и следующая теорема:

Теорема 2. Если a₁, a₂, ..., a_q, все различные простые числа, входящие в m, то число чисел, взаимно простых с m и входящих в ряд

1, 2, ..., m

определяется формулой (8).

Действительно. Всякое число, которое не делится ни на один из простых множителей, входящих в состав m является взаимно простым с m. Тогда учитывая теорему 1, получаем доказательство данной теоремы.

Найденная формула можно переписать и в другом виде. Если a₁, a₂, a₃, ... все различные простые числа, входящие множителями в m, то

Тогда

Рассмотрим численный пример.

Пример. Возьмем число 90. Числа, взаимно простые с 90 и меньше 90 следующие:

1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89.

Таких чисел 24. Учитывая, что 90=2·3²·5, для φ(m) мы находим

Мультипликативность функции Эйлера

Теорема 3. Если m₁ и m₂ числа взаимно простые, то

φ(m1m2)=φ(m1)φ(m2)

Доказательство. Если a₁, a₂, a₃,... различные простые числа, входящие в состав m₁ и b₁, b₂, b₂, ... различные простые числа, входящие в состав m₂, то

a1, a2, a3, ... b1, b2, b3, ...

(9)

различные простые числа, входящие в состав m₁m₂, так как m₁ и m₂ взаимно простые числа, т.е. они не имеют общих делителей.

Справедливо и обратное. Всякое простое число входящее в произведение m₁m₂ должно совпадать с числом из ряда (9), так как это простое число входит множителем или в m₁, или в m₂.

Таким образом числа ряда (9) представляют множество всех простых чисел, входящих в произведение m₁m₂. Следовательно

С другой стороны

Тогда

φ(m1m2)=φ(m1)φ(m2).

Теорема доказана.■

Пример.

φ(90)=φ(9·10)=φ(9)φ(10),

φ(90)=φ(9·10)=φ(9)φ(10)=6·4=24.

Эта теорема справедлива и для любого числа сомножителей, если эти сомножители взаимно простые числа.

Действительно.

φ(m1m2m3) = φ(m1)φ(m2m3) = φ(m1)φ(m2)φ(m3).

φ(m1m2m3m4) = φ(m1)φ(m2m3m4) = φ(m1)φ(m2)φ(m3)φ(m4).

и т.д.

Обобщение функции Эйлера

Как мы уже видели, функция Эйлера φ(m) показывает, сколько в ряду

1, 2, ...., m

(10)

чисел взаимно простых с m.

Более общая задача состоит в следующем:

Задача 3. Дан ряд (10) и требуется найти число тех чисел, этого ряда, которые имеют с m наибольший общий делитель λ, причем m=nλ, т.е. λ является одним из делителей числа m.

Очевидно, что искомые числа находятся среди чисел

λ, 2λ , 3λ , ..., nλ

(11)

Для того, чтобы λ было наибольшим общим делителем чисел m=nλ и kλ из ряда (11), необходимо и достаточно, чтобы k и n были числами взаимно простыми. Следовательно, т.к. k принимает значения

1, 2, ...n

(12)

то искомых чисел столько, сколько найдется чисел из ряда (12) взаимно простых с n. Число таких чисел равно φ(n) (Теорема 2).

Мы доказали следующую теорему:

Теорема 4. Если a₁, a₂, a₃, ... все различные простые числа, входящие в m, то число чисел, имеющих с m наибольший общий делитель λ (m=nλ) равен числу

φ(n)=φ(m/λ)

(12)

Далее выпишем все делители λ₁, λ₂,λ₃,... числа

m=n1λ1=n2λ2=n3λ3=...

и разобьем ряд

1, 2, ...., m

(13)

на столько групп, сколько m имеет делителей λ₁, λ₂,λ₃,...

Тогда φ(n₁) количество тех чисел, которые с m имеют наибольший общий делитель λ₁, φ(n₂) количество тех чисел, которые с m имеют наибольший общий делитель λ₂, и т.д.

Следовательно

φ(n1)+φ(n2)+φ(n3)+...=m

или

Мы доказали следующую теорему:

Теорема 5. Пусть n₁, n₂, ..., n_k все делители числа m. Тогда имеет место следующее равенство:

Рассмотрим пример.

Пример. Пусть m=90. Делители числа m следующие:

1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90

Тогда

φ(1)=1, φ(2)=1, φ(3)=2, φ(5)=4, φ(6)=2, φ(9)=6, φ(10)=4, φ(15)=8, φ(18)=6, φ(30)=8, φ(45)=24, φ(90)=24

Наконец

φ(1)+ φ(2)+ φ(3)+ φ(5)+...+ φ(90)=90