Задача по математике Докажите. Пусть n - положительное целое число, и {r1, r2. . . rk} полная система вычетов по модулю n. Если a целое число, взаимно простое с n, то {a*r1, a*r2. . . a*rk} полная система вычетов по модулю n.

Предыдущий
вопрос Следующий
вопрос

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

Пусть 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.