Система с уменьшенным количеством остатков
- В математике подмножество R целых чисел называется приведенной системой вычетов по модулю n, если gcd(r, n) = 1 для каждого r в R.
- R содержит φ(n) элементов, и никакие два элемента R не совпадают по модулю n.
- Сокращенная система вычетов может быть сформирована из полной системы вычетов путем удаления всех целых чисел, которые не являются простыми относительно n.
- Приведенная система вычетов представляет собой группу, умноженную по модулю n.
- Если {r1, r2, … , rφ(n)} — приведенная система вычетов по модулю n, тогда ∑r i ≡ 0 mod n.
- Если {r1, r2, … , rφ(n)} — приведенная система вычетов по модулю n, а a — целое число, такое, что gcd(a, n) = 1, тогда {ar1, ar2, … , arφ(n)} также является редуцированной системой вычетов по модулю n.
Полный текст статьи: