Архив задач олимпиады по математике и криптографии

Количество взаимно простых чисел

Подсчитайте, сколько всего существует натуральных чисел, которые не превосходят число 841 и не имеют с ним общих делителей, отличных от 1.

  • Решение

    • Решение

    Заметим, что 849 = 292 и 29 – простое число. Теперь нетрудно сообразить, что существует 29(29 - 1) = 812 натуральных чисел, которые не превосходят число 841 и не имеют с ним общих делителей, отличных от 1.
  • Ответ

    • Ответ

    812.