Задача по математике

Для доказательства данного утверждения, мы должны показать, что множество {ar1, ar2, ..., a*rk} является полной системой вычетов по модулю n.

Для начала, давайте предположим, что у нас есть два различных элемента в множестве {ar1, ar2, ..., ark}, скажем ari и arj, где i ≠ j. Нам нужно показать, что ari ≡ a*rj (mod n).

Поскольку {r1, r2, ..., rk} является полной системой вычетов по модулю n, это означает, что для каждого вычета x, где 0 ≤ x < n, существует некоторое ri такое, что x ≡ ri (mod n).

Теперь, умножив обе части этого сравнения на a, получаем:
ax ≡ ari (mod n) и ax ≡ arj (mod n).

Поскольку умножение обладает свойством сохранения сравнений (если a ≡ b (mod n), то ac ≡ bc (mod n) для любого целого числа c), мы можем умножить обе части сравнений на a и получить:
ari ≡ arj (mod n).

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

Кроме того, мы должны убедиться, что каждый вычет по модулю n присутствует в множестве {ar1, ar2, ..., ark}. Это можно показать, заметив, что каждый элемент множества {r1, r2, ..., rk} также является вычетом по модулю n. Следовательно, умножение каждого вычета на a (где a взаимно просто с n) даст нам полную систему вычетов {ar1, ar2, ..., ark}.

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