Пусть даны m и φ(m)=k
Имеем число a, причем (a,m)=1
Берем ряд натуральных чисел:
a1 , a2
, …. , ak
0, 1, … m-1 – из этого диапазона чисел выбираем взаимнопростые с модулем
(k штук)
a ×a1 , a* a2 , …, a* ak – взаимнопросты с модулем
a × a1
a ×a1
≡ ai1
≡ ai 2
mod m mod m
……
a × a1
≡ aik
mod m
ak ≡ 1 mod m, φ(m)=k
aj(m) ≡ 1 mod m
a ≡ b mod m a ≡ c mod m a ≡ d mod m