Задача
ALG-B3-M08-P015 Линейная инволюция по модулю
#15
★★★★★ Уровень 5 из 5
Пусть \(p\) - нечётное простое, \(f(x)=ax\) на \(\mathbb Z/p\mathbb Z\), и \(f^2(x)=x\) для всех \(x\). Найдите возможные \(a\).
Условие означает \(a^2x\equiv x\).
Для всех \(x\) имеем \(a^2x\equiv x\pmod p\), значит \(a^2\equiv1\pmod p\). Тогда \((a-1)(a+1)\equiv0\pmod p\). Так как \(p\) простое, \(a\equiv1\) или \(a\equiv-1\pmod p\).
Модульная итерация коэффициента.