69
правок
Изменения
Нет описания правки
Теперь приступим непосредственно к доказательству. Число находящееся в <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>n</math>, а при добавлении <math>n</math> остаток деления по модулю <math>n</math> не меняется. Поэтому, числа взаимно простые с <math>n</math> в таблице занимают ровно <math>\varphi(n)</math> столбцов.
Перед тем как продолжить доказательство, давайте рассмотрим небольшое утверждение. Пусть нам даны <math>m</math> последовательных членов арифметической прогрессии <math>a, a + d, \dots , a + (m - 1)d</math>. Тогда, если <math>(d, m) = 1</math>, то остатки всех этих <math>m</math> чисел по модулю <math>m</math> разные, а значит , образуют все множество остатков <math>\{0, \dots , m - 1\}</math>, причем каждый остаток получается ровно из одного из членов прогрессии.
Воспользуемся данным утверждением, подставив разность арифметической прогресии <math>d = n</math>. Тогда в каждом из <math>\varphi(n)</math> столбцов есть ровно <math>\varphi(m)</math> чисел, взаимно простых с <math>m</math>. Следовательно всего чисел, взаимно простых и с <math>n</math> и с <math>m</math> равно <math>\varphi(m)\varphi(n)</math>, что и требовалось доказать.
<math></math>
Значит , <tex>\displaystyle\frac{\varphi(b)}{\varphi(a)}</tex><tex>\displaystyle = \frac{\displaystyle\prod_{i = 1}^{r_b}p_i^{\beta_i - 1}(p_i - 1)}{\displaystyle\prod_{i = 1}^{r_a}p_i^{\alpha_i - 1}(p_i - 1)} = \displaystyle(\prod_{i = 1}^{r_a}p_i^{\beta_i - \alpha_i}) \cdot \displaystyle(\prod_{i = r_a + 1}^{r_b}p_i^{\beta_i - 1}(p_i - 1))</tex>, а значит , <math>\varphi(a)\,|\, \varphi(b)</math>, что и требовалось доказать.
}}
