Функция Эйлера

[bayah]

Привет, математики!
В книге "Что такое математика" Куранта приводится формула Эйлера для количества взаимно простых чисел c $n$ в отрезке от $1$ до $n$: $\varphi(n) = n\Big(1-\frac 1 p_1\Big)\Big(1-\frac 1 p_2\Big)\dots\Big(1-\frac 1 p_r\Big)$, где $n = p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r}$, и где $p_i$ - простые.
И написано:

Цитата:

Доказательство приведенный теоремы совершенно элементарно, но мы его не приводим.

Ну, понятно, что если $n = p$, где $p$ - простое, то $\varphi(n) = n-1$.
Если $n = p^\alpha$, то $\varphi(n) = p^\alpha - p^{\alpha - 1}$.
Это ясно, если вычесть все не взаимно простые числа с $p^\alpha$ Это все кратные $p$ числа.

Становится ясно, что формула Эйлера это тогда
$\varphi(n) = p_1^{\alpha_1}\Big(1-\frac 1 p_1\Big)p_2^{\alpha_2}\Big(1-\frac 1 p_2\Big)\dots p_r^{\alpha_r}\Big(1-\frac 1 p_r\Big) = \\ \Big(p_1^\alpha - p_1^{\alpha - 1}\Big)\Big(p_2^\alpha - p_2^{\alpha - 1}\Big)\dots\Big(p_r^\alpha - p_r^{\alpha - 1}\Big) = \varphi(p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r})$

То есть $\varphi(p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r}) = \varphi(p_1^{\alpha_1}) \varphi(p_2^{\alpha_2}) \dots \varphi(p_r^{\alpha_r})$.
Это единственное что осталось доказать.
Но как это доказать "совершенно элементарно" я что-то не вижу.

Подскажите?

[iifat]

Доказывают мультипликативность, то бишь, $\varphi(ab)=\varphi(a)\varphi(b)$ для взаимно простых $a$, $b$. Попробуйте записать их в квадратную таблицу. Я, помнится, как-то так делал. Ну или поищите Виноградов, Основы теории чисел — там, по-моему, есть.

[VAL]

iifat в сообщении #1342948 писал(а):

Попробуйте записать их в квадратную таблицу.

Только не в квадратную (взаимно простые редко бывают равны ), а в прямоугольную.
Запишите в первую строку числа от 1 до $a$, во вторую - от $a+1$ до $2a$ и т. д.
Где будут расположены взаимно простые с $a$? Сколько взаимно простых с $b$ будет в каждом столбце?

[RIP]

(Оффтоп)

Можно ещё раскрыть скобки в произведении $\displaystyle{}n\prod_{k=1}^{r}\left(1-\frac{1}{p_k}\right)$ и понять, что это просто формула включения–исключения (аналогично случаю $n=p^{\alpha}$). Но нужно немного напрячься, чтобы это понять.

[bayah]

VAL в сообщении #1342990 писал(а):

Только не в квадратную (взаимно простые редко бывают равны ), а в прямоугольную.
Запишите в первую строку числа от 1 до $a$, во вторую - от $a+1$ до $2a$ и т. д.
Где будут расположены взаимно простые с $a$? Сколько взаимно простых с $b$ будет в каждом столбце?

Ага, понял.
Получается взаимно простые с $a$ это вертикальные столбцы проходящие по первым от $1$ до $a$ взаимно простым с $a$.
А в каждом столбце получается столько взаимно простых c $b$ сколько взаимно простых с $b$ от $1$ до $b$.
Вопрос, почему в каждом столбце взаимно простых с $b$ все таки одно число. Ну если $b$ простое, то в столбце из $b$ элементов может быть не более и не менее $b$-кратных чисел, то есть ровно $b-1$ взаимно простых. Если $b$ составное, то есть, например, $b = p_1p_2$, тогда в столбце может быть ровно $p_2$ элементов кратных $p_1$, и $p_1$ элементов крастных с $p_2$. То есть опять для каждого столбца одно и то же число взаимно простых с $b$.

Это можно считтать доказательством мультимпликативности $\varphi(ab)=\varphi(a)\varphi(b)$?

[VAL]

bayah в сообщении #1343152 писал(а):

Вопрос, почему в каждом столбце взаимно простых с $b$ все таки одно число.

В каждом столбце числа идут с шагом $a$. Легко показать от противного, что у них разные остатки от деления на $b$. И их ровно $b$ штук, т. е. каждый остаток встречается ровно один раз.