7-я олимпиада им. Шалтая Смагулова, 7 класс, 1 тур
Найдите количество натуральных чисел, меньших чем 2449, и взаимно простых с ним. (Два целых числа называются взаимно простыми, если их наибольший общий делитель равен единице.)
посмотреть в олимпиаде
Комментарий/решение:
В данной задаче необходимо посчитать количество взаимно простых чисел от 1 до 2449 к 2449, что в свою очередь является прямой иллюстраций функции Эйлера. Другими словами нам нужно посчитать чему равен $\phi(2449)$.
$2449=31*79$
$\phi(2449)=$
$=\phi(31)*\phi(79)=$
$=(31-1)*(79-1)=2340$
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.