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

Доказательство мультипликативности функции Эйлера
Шатилов Кирилл Евгеньевич
Россия, Ханты-Мансийский автономный округ – Югра,
Россия, Тюменская область, ХМАО-Югра, Город Нефтеюганск,
Муниципальное бюджетное общеобразовательное учреждение «Лицей №1», 11 А класс

                                                                 Научная статья

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

Пусть дано некоторое число m, представим его в стандартном виде  . Тогда найдем количество чисел которые имеют общие делители с числом m в ряду чисел от 0 до m (не включительно)(в дальнейшем всегда будет иметься ввиду именно этот ряд). Для начала определим какое количество чисел делится на P1(включая ноль), так как количество чисел, которые делятся на a в ряду чисел от 1 до a*b (не включительно) равно b-1, получаем f1=m/P1. Теперь определим такое же количество для P2, но вычтем теперь из это количества количество чисел, которые делятся на P1 и на P2, так как они уже посчитаны. Такие рассуждения можно проделывать и для всех остальных чисел вплоть до P[i], таким образом если сложить все такие количества, то получится количество всех неповторяющихся чисел из нашего ряда, которые имеют общие делители с m (напрямую следует из основной теоремы арифметики).[pic 1]

 Пусть даны числа f1, f2, f3 … f[i], где f[k] это количество чисел, в ряду которые делятся на P[k] но не делится ни на P1 ни на P2 ни на P3 и так далее вплоть до P[k-1]. Докажем теперь [pic 2]

(1)[pic 3]

Доказывать будем математической индукцией.

База индукции.

[pic 4]

[pic 5]

Предположение индукции.

Для того чтобы сделать предположение рассмотрим из чего состоит f[k]. Понятно что сначала мы вычисляем кол-во чисел которые делятся на P[k] и отнимаем из него кол-во чисел которое делится на P1*P[k], и получаем число . Теперь нужно отнять из этого кол-ва кол-во чисел, которые делятся на P[k] и на P2 но не делятся на P1 (мы их уже отняли) после нужно уже из этого кол-ва отнять кол-во чисел которые делятся на P[k] и на P3 но не делятся ни на P1, ни на P2. И так далее пока не дойдем до P[k-1], и пусть все эти элементы включая (m-f1)/P[k] будут называться “островками” первой группы. Возьмем последний такой островок и рассмотрим из чего он состоит. Окажется что мы проделаем те же самые шаги за тем лишь исключением что теперь нам нужно найти кол-во чисел, которые делятся на P[k]*P[k-1] и на P[j] но не делятся ни на одно из чисел от P1 до P[j-1], такие элементы тоже будут называться островками, но только 2-ой группы. Теперь возьмем уже в этой последовательности последний элемент и проделаем тоже самое, после в этой последовательности снова возьмем последний элемент и так далее до тех пор, пока не окажется что последний элемент — это кол-во чисел, которые делятся на P1P2P3…P[i], и все возникающие в этом процессе элементы будут теперь называться островками некоторой j-ой группы. Перейдем к предположению индукции. Сделаем два предположения:[pic 6]

1. Предположим, что мы доказали формулу (1) для каждого кол-ва: f1, f2, f3 … fi, при чем в независимости от выбора простых делителей m.
2. Предположим, что кол-во элементов, которое делится на P[i]P[i-1]P[i-2]P[i-3]…P[i-h]*P[g] в ряду, но не делятся ни на одно из чисел от P1 до P[g-1] равно, где g>1, при g=1 формула изменится на следующую То есть мы рассматриваем последнее кол-во f[i] и определяем значение для каждого островка в каждой из групп островков.[pic 7][pic 8]

                                                                Шаг индукции

Нужно доказать формулу (1) для P[i+1] (следующего простого делителя m). То есть нужно доказать что каждый из островков f[i+1] 1-ой группы вычисляется по формуле f[g]/(P[i+1]), за исключением первого который равен (m-f1)/P[i+1]. Для этого в последнем кол-ве f[i] вместо P[i] рассмотрим P[i+1](получим f[i1]). По предположению мы знаем все островки f[i(1)]. То есть осталось только доказать, что последний островок 1-ой группы равен f[i]/P[i+1]. Для этого в предпоследнем кол-ве вместо  P[i-1] рассмотрим P[i]. По предположению мы знаем все островки 2-ой группы f[i(2)]. Что ж осталось только доказать, что последний островок 2-ой группы равен f[i-1]/(P[i+1]*P[i]). То есть в общем случае, если стоит задача доказать, что кол-во чисел которые делятся на P[i+1]P[i]P[i-1]P[i-2]…P[i-k], но не делятся ни на одно из чисел от P1 до P[i-k-1] равно: