Формула

Докажите, ее, пожалуйста.

задан 7 Окт '17 0:25

10|600 символов нужно символов осталось
1

Формулу надо записать более стандартно: $%\sum\limits_{d|n}\varphi(d)=n$%. Это сумма по всем натуральным делителям числа $%n$%. В тех обозначениях, которые по ссылке, фигурируют какие-то $%a_i$%, которые нигде не определены.

Доказательство здесь такое: рассмотрим произвольное $%i$% от $%1$% до $%n$%. Его НОД с числом $%i$% равен какому-то делителю $%k$% числа $%n$%. Отсюда $%i=kj$%, где $%j$% взаимно просто с $%d=\frac{n}k$%. Количество тех $%i$%, которые дают значение $%НОД(i,n)=k$%, равно $%\varphi(d)$%, где $%d|n$%. Поэтому, суммируя по всем делителям числа $%n$%, получаем количество чисел от 1 до $%n$%, то есть $%n$%.

Для наглядности: пусть $%n=12$%. Числа от 1 до 12 разделим на группы в соответствие со значением НОД.

НОД=1 для 1,5,7,11. Таких чисел $%\varphi(12)=4.

НОД=2 для чисел 2, 10; после деления на 2 получается 1, 5 -- это числа, взаимно простые с 6=12/2, и их количество равно $%\varphi(6)=2.

НОД=3 для чисел 3, 9, что после деления на 3 даёт 1, 3 -- числа, взаимно простые с 4=12/3, и их имеется $%\varphi(4)=2.

Случаи НОД=4, 6, 12 разбираются аналогично.

ссылка

отвечен 7 Окт '17 1:11

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,706

задан
7 Окт '17 0:25

показан
232 раза

обновлен
7 Окт '17 1:11

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru