Теорема 2. Нехай A, m, n - натуральні числа; (A, m)=1, xºx₀(mod m) – один з розв’язків порівняння xⁿºA(mod m).

Тоді всі розв’язки цього порівняння одержуються множенням x₀ на лишки розв’язків порівняння yⁿº1(mod m).

Доказ. Перемножимо порівняння:

звідки видно, що x₀y — розв’язок порівняння xⁿºA(mod m).

Якщо тепер y₁¹y₂(mod m), то x₀y₁¹x₀y₂(mod m). Дійсно, припустимо, що x₀y₁º x₀y₂(mod m). Очевидно, що (x₀, m)=1, тому що інакше було б:

x₀=d×x₀^Ñ, m=d×m^Ñ,

x₀=dⁿ(x₀)ⁿºA(mod d m^Ñ),

отже d ділить А і ділить m, що суперечить взаємній простоті А і m. Отже (x₀, m)=1 і порівняння x₀ y₁ºx₀ y₂(mod m) можна поділити на x₀: y₁ºy₂(mod m) – а це суперечить початковому припущенню. Таким чином, для різних y₁ і y₂, виходять різні розв’язки.

Залишилося переконатися, що кожний розв’язок порівняння xⁿºA(mod m) одержується саме таким способом. Маємо:

xⁿºA(mod m)                                             x₀ⁿºA(mod m),

отже, xⁿºx₀ⁿ(mod m). Візьмемо число y таке, що xºy×x₀(mod m). Тоді yⁿx₀ⁿº x₀ⁿ(mod m), тобто yⁿº1(mod m).