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

2449 санымен өзара жай және осы саннан кіші неше натурал сан бар? (Егер екі бүтін сандардың ең үлкен ортақ бөлгіші $1$-ге тең болса, ондай сандарды өзара жай сан деп атаймыз.)

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

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

$2449=31*79$

$\phi(2449)=$

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

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