Новости
Олимпиады
Онлайн-образование
Авторизация
Архив задач олимпиады по математике и криптографии
Количество взаимно простых чисел
Подсчитайте, сколько всего существует натуральных чисел, которые не превосходят число 841 и не имеют с ним общих делителей, отличных от 1.
Решение
Решение
Заметим, что 849 = 29
2
и 29 – простое число. Теперь нетрудно сообразить, что существует 29(29 - 1) = 812 натуральных чисел, которые не превосходят число 841 и не имеют с ним общих делителей, отличных от 1.
Ответ
Ответ
812.