ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1204. Идемпотенты

Easy Accepted
Послано Axmed 4 авг 2025 13:11
At first N = p * q, let's find this prime numbers p and q.
Now we have x * x = x mod N.
x * x - x = 0 mod N
x * (x - 1) = 0 mod N
Let's note that x != pq, because x < n. That means x mod p = 0, x - 1 mod q = 0 or x mod q = 0, x - 1 mod p = 0.
Consider {
x mod p = 0
x mod q = 1
}
another case is symmetrical.
x = k * p, because x mod p = 0.
Now we have k * p mod q = 1
k = 1 / p mod q
k = p ^ (-1) mod q
Use Fermat's little theorem k = p ^ (q - 2) mod q.
We find x = k * p, problem is solved.