7-я олимпиада им. Шалтая Смагулова, 7 класс, 1 тур

Найдите количество натуральных чисел, меньших чем 2449, и взаимно простых с ним. (Два целых числа называются взаимно простыми, если их наибольший общий делитель равен единице.)

Комментарий/решение

В данной задаче необходимо посчитать количество взаимно простых чисел от 1 до 2449 к 2449, что в свою очередь является прямой иллюстраций функции Эйлера. Другими словами нам нужно посчитать чему равен $\phi(2449)$.

$2449=31*79$

$\phi(2449)=$

$=\phi(31)*\phi(79)=$

$=(31-1)*(79-1)=2340$