Система с уменьшенными остатками

редактировать

Набор классов остатка по модулю n, взаимно простое с n

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

gcd (r, n) = 1 для каждого r в R,
R содержит φ (n) элементов,
никакие два элемента 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}

Содержание

1 Факты
2 См. Также
3 Примечания
4 Ссылки
5 Внешние ссылки

Факты

Если {r 1, r 2,..., r φ (n) } - это система приведенных остатков по модулю n с n>2, тогда $∑ ri ≡ 0 mod n {\ displaystyle \ sum r_ {i} \ Equiv 0 \! \! \! \! \ mod n}$ ${\ displaystyle \ sum r_ {i} \ Equiv 0 \! \! \! \! \ mod n}$ .
Каждое число в приведенной системе вычетов по модулю n является генератором для аддитивной группы целые числа по модулю n.

См. также

Примечания

^Лонг (1972, стр. 85)
^Петтофреццо и Биркит (1970, стр. 104)

Ссылки

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

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

Остаточные системы в PlanetMath
Система сокращенных остатков в MathWorld