Sistema reducido de residuos

En matemáticas, un subconxunto R dos enteiros chámase sistema reducido de residuos módulo n se:

1. mcd(r,n) = 1 para cada r en R ,
2. R contén φ(n) elementos,
3. non hai dous elementos de R congruentes módulo n.^{[1] [2]}

Aquí φ denota a función totiente de Euler .

Un sistema de residuos reducido módulo n pódese formar a partir dun sistema de residuos completo módulo n eliminando todos os números enteiros non primos relativos a n. Por exemplo, un sistema de residuos completo módulo 12 é {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. Os chamados totativos 1, 5, 7 e 11 son os únicos enteiros deste conxunto que son relativamente primos con 12, polo que o correspondente sistema de residuos reducidos módulo 12 é {1, 5, 7, 11}. A cardinalidade deste conxunto pódese calcular coa función totiente: φ(12) = 4. Algúns outros sistemas de residuos reducidos módulo 12 son:

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

Feitos

• Todo número nun sistema reducido de residuos módulo n é un xerador para o grupo aditivo de enteiros módulo n.
• Un sistema reducido de residuos módulo n é un grupo baixo multiplicación módulo n.
• Se {r₁, r₂, ..., r_φ(n)} é un sistema reducido de residuos módulo n con n > 2, entón ${\displaystyle \sum r_{i}\equiv 0\!\!\!\!\mod n}$.
• Se {r₁, r₂, ..., r_φ(n)} é un sistema reducido de residuos módulo n, e a é un número enteiro tal que mcd(a, n) = 1, entón {ar₁, ar₂, ..., ar_φ(n)} tamén é un sistema de residuos reducido módulo n.^{[3] [4]}

Notas

1. Long (1972, p. 85)
2. Pettofrezzo & Byrkit (1970, p. 104)
3. Long (1972, p. 86)
4. Pettofrezzo & Byrkit (1970, p. 108)

Véxase tamén

Bibliografía

• Long, Calvin T. (1972). Elementary Introduction to Number Theory (2nd ed.). Lexington: D. C. Heath and Company. LCCN 77171950. 
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elements of Number Theory. Englewood Cliffs: Prentice Hall. LCCN 71081766. 

Outros artigos

• Grupo multiplicativo de números enteiros módulo n
• Relación de congruencia
• Función totiente de Euler
• Máximo común divisor
• Aritmética modular
• Teoría de números

Ligazóns externas

• Residue systems at PlanetMath
• Reduced residue system at MathWorld