69
правок
Изменения
→Функция Эйлера
Запишем <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>s</math> на <math>k</math> тоже взаимно прост с <math>k</math>.
