Физтех 2025, отборочный этап, 10 класс, первый тур, задача 7
Найдите количество всех пар натуральных чисел , при которых является верным равенство
Ответ
Ответ. .
Решение. Правая часть равенства имеет остаток от деления на . Левая часть имеет остаток от деления на , только если имеет остаток или от деления на . Разберём эти случаи.
Пусть , где — целое неотрицательное число. Тогда равенство можно преобразовать к виду . Заметим, что для каждого целого , такого, что , число натуральное и определяется однозначно. Значит, количество пар в этом случае равно количеству таких, что , то есть . Отсюда количество пар равно .
Пусть . Тогда равенство можно преобразовать к виду . Аналогично предыдущему случаю получаем, что количество пар равно количеству таких, что , то есть . Отсюда количество пар равно .
Общее количество пар равно .