Доказательство:

Пусть m = arj и n - brj, где j = 1, 2, ..., k.

Так как a и n взаимно просты, существует целое число c, такое что ac + nd = 1, где d - целое число.

Тогда m = arj = acn + adn ≡ brj(mod n), так как ac ≡ 1(mod n) и ad ≡ 0(mod n).

Следовательно, m ≡ brj(mod n) для всех j = 1, 2, ..., k и {ar1, ar2, ..., ark} также является полной системой вычетов по модулю n.

Таким образом, доказано, что если a - целое число, взаимно простое с n, то {ar1, ar2, ..., a*rk} является полной системой вычетов по модулю n.