69
правок
Изменения
→Функция Эйлера
{{Определение
|definition=
''Функция Эйлера'' <tex>\varphi (n) </tex> {{---}} определяется как количество натуральных чисел, не превосходящих <tex>n</tex> и взаимно-простых с <tex>n</tex>.
}}
{{Определение
|definition=
Функция <tex>f : \mathbb{N} \to \mathbb{Z} </tex> называется ''мультипликативной'', если <tex>f(mn) = f(m)f(n)</tex> для любых взаимно-простых <tex>m, n</tex>.
}}
{{Теорема
|about = Мультипликативность функции Эйлера
|statement = Для любых взаимно-простых чисел <tex>m, n</tex>
: <math>\varphi(mn)=\varphi(m)\varphi(n)</math>
|proof =
Запишем <math>n \cdot m</math> натуральных чисел, не превосходящих <math>n \cdot m</math>, в виде прямоугольной таблицы с <math>n</math> столбцами и <math>m</math> строками, располагая первые <math>n</math> чисел в первой строке, вторые <math>n</math> чисел во второй и т.д.
Поскольку <math>n</math> и <math>m</math> взаимно-просты, то целое <math>s</math> взаимно-просто с <math>n \cdot m</math> если и только если оно взаимно-просто как с <math>n</math>, так и с <math>m</math>. Итак, нужно доказать, что количество чисел в таблице, взаимно-простых с <math>n</math> и с <math>m</math> равно <math>\varphi(m)\varphi(n)</math>. Мы знаем, что число <math>s</math> взаимно-просто с натуральным <math>k</math> если и только если его остаток при делении на <math>k</math> взаимно-просто с <math>k</math>. Поэтому, числа в таблице, взаимно-простые с <math>n</math>, заполняют ровно <math>\varphi(n)</math> столбцов таблицы.
Давайте рассмотрим <math>m</math> последовательных членов арифметической прогрессии <math>a, a + d, \dots , a + (m - 1)d</math>. Тогда, если <math>GCD(d, m) = 1</math>, то остатки всех этих <math>m</math> чисел по модулю <math>m</math> разные, а значит образуют все множество остатков <math>\{0, \dots , m - 1\}</math>, причем каждый остаток получается ровно из одного из членов прогрессии.
Подставив в данные рассуждения <math>d = n</math>, получим, что в каждом столбце таблицы имеется ровно <math>\varphi(m)</math> чисел, взаимно-простых с <math>m</math>. Следовательно всего чисел, взаимно-простых и с <math>n</math> и с <math>m</math> равно <math>\varphi(m)\varphi(n)</math>, что и требовалось доказать.
}}
