Изменения

Запишем <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>ms</math> последовательных членов арифметической прогрессии взаимно просто с натуральным <math>a, a + d, \dots , a + (m - 1)dk</math>. Тогдатогда и только тогда, если когда остаток деления <math>GCD(d, m) = 1s</math>, то остатки всех этих на <math>mk</math> чисел по модулю тоже взаимно прост с <math>mk</math> разные, а значит образуют все множество остатков <math>\{0, \dots , m - 1\}</math>, причем каждый остаток получается ровно из одного из членов прогрессии.

Подставив Теперь приступим невосредственно к доказательству. Число находящееся в <math>i</math>-ой строке и <math>j</math>-ом столбце нашей таблицы можно представить в виде <math>n(i - 1) + j</math>. Если это число взаимно просто с <math>n</math>, то и остаток этого числа по модулю <math>n</math> тоже заимно прост с <math>n</math>. Но тогда и все числа в данном столбце тоже взаимно просты с <math>n</math>, так как весь столбец можно представить в данные рассуждения виде арифметической прогрессии с разностью <math>d = n</math>, получима при добавлении <math>n</math> остаток деления по модулю <math>n</math> не меняется. Поэтому, что числа взаинмо простые с <math>n</math> в каждом столбце таблицы имеется таблице занимают ровно <math>\varphi(mn)</math> чиселстолбцов. Проводя аналогичные рассуждения для строк, мы получим, взаимно простых что числа взаинмо простые с <math>m</math>в таблице занимают ровно <math>\varphi(m)</math> строк.  Следовательно всего чисел, взаимно простых и с <math>n</math> и с <math>m</math> равно <math>\varphi(m)\varphi(n)</math>, что и требовалось доказать.