Система пониженного остатка

В математике подмножество R n целых чисел называется приведенной системой вычетов по модулю , если:

1. НОД( r , n ) = 1 для каждого r в R ,
2. R содержит φ( n ) элементов,
3. никакие два элемента R не конгруэнтны по модулю n .

Здесь φ обозначает тотент-функцию Эйлера .

Приведенная система вычетов по модулю n может быть сформирована из полной системы вычетов по модулю n путем удаления всех целых чисел, не являющихся взаимно простыми с n . Например, полная система вычетов по модулю 12 равна {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. Так называемые тотативы 1, 5, 7 и 11 — единственные целые числа в этом наборе, которые взаимно просты с 12, поэтому соответствующая приведенная система вычетов по модулю 12 равна {1, 5, 7, 11}. Мощность этого набора можно вычислить с помощью функции тотента: φ(12) = 4. Некоторые другие системы приведенных вычетов по модулю 12:

• {13,17,19,23}
• {−11,−7,−5,−1}
• {−7,−13,13,31}
• {35,43,53,61}

Факты

• Каждое число в приведенной системе вычетов по модулю n является генератором аддитивной группы целых чисел по модулю n .
• Приведенная система вычетов по модулю n — это группа при умножении по модулю n .
• Если { r ₁ , r ₂ , ... , r _{φ( n )} } является приведенной системой вычетов по модулю n с n > 2, то $\sum r_{i}\equiv 0\!\!\!\!\mod n$.
• Если { r ₁ , r ₂ , ... , r _{φ( n )} } — приведенная система вычетов по модулю n , а a — целое число такое, что НОД( a , n ) = 1, то { ar ₁ , ar ₂ , ... , ar _{φ( n )} } также является приведенной системой вычетов по модулю n .

См. также

• Полная система остатков по модулю м
• Мультипликативная группа целых чисел по модулю n
• Отношение конгруэнтности
• Функция Эйлера
• Наибольший общий делитель
• Система наименьшего остатка по модулю m
• Модульная арифметика
• Теория чисел
• Система нумерации остатков

Ссылки

• Лонг, Кэлвин Т. (1972), Элементарное введение в теорию чисел (2-е изд.), Лексингтон: DC Heath and Company , LCCN   77171950
• Петтофреззо, Энтони Дж.; Биркит, Дональд Р. (1970), Элементы теории чисел , Энглвуд Клиффс: Прентис Холл , LCCN   71081766

Внешние ссылки

• Системы остатков в PlanetMath
• Система уменьшенного остатка в MathWorld