Sistema de residuos reducidos

Conjunto de clases de residuos módulo n, relativamente primos a n

En matemáticas , un subconjunto R de los números enteros se denomina sistema de residuos reducido módulo n si:

1. mcd( r , n ) = 1 para cada r en R ,
2. R contiene φ( n ) elementos,
3. No hay dos elementos de R congruentes módulo n . ^{[1] [2} ]

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

Un sistema de residuos reducido módulo n se puede formar a partir de un sistema de residuos completo módulo n eliminando todos los números enteros que no sean primos entre sí con n . Por ejemplo, un sistema de residuos completo módulo 12 es {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. Los denominados totales 1, 5, 7 y 11 son los únicos números enteros de este conjunto que son primos entre sí con 12, por lo que el sistema de residuos reducido módulo 12 correspondiente es {1, 5, 7, 11}. La cardinalidad de este conjunto se puede calcular con la función totiente: φ(12) = 4. Algunos otros sistemas de residuos reducidos módulo 12 son:

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

Hechos

• Cada número en un sistema de residuos reducidos módulo n es un generador del grupo aditivo de números enteros módulo n .
• Un sistema de residuos reducidos módulo n es un grupo bajo multiplicación módulo n .
• Si { r ₁ , r ₂ , ... , r _{φ( n )} } es un sistema de residuos reducido módulo n con n > 2, entonces . ${\displaystyle \sum r_{i}\equiv 0\!\!\!\!\mod n}$
• Si { r ₁ , r ₂ , ... , r _{φ( n )} } es un sistema de residuos reducido módulo n , y a es un entero tal que mcd( a , n ) = 1, entonces { ar ₁ , ar ₂ , ... , ar _{φ( n )} } también es un sistema de residuos reducido módulo n . ^{[3] [4]}

Véase también

• Sistema de residuos completo módulo m
• Grupo multiplicativo de números enteros módulo n
• Relación de congruencia
• Función totiente de Euler
• Máximo común divisor
• Sistema de residuo mínimo módulo m
• Aritmética modular
• Teoría de números
• Sistema de numeración de residuos

Notas

1. Largo (1972, pág. 85)
2. Pettofrezzo y Byrkit (1970, pág. 104)
3. Largo (1972, pág. 86)
4. Pettofrezzo y Byrkit (1970, pág. 108)

Referencias

• Long, Calvin T. (1972), Introducción elemental a la teoría de números (2.ª ed.), Lexington: DC Heath and Company , LCCN  77171950
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elementos de la teoría de números , Englewood Cliffs: Prentice Hall , LCCN  71081766

Enlaces externos

• Sistemas de residuos en PlanetMath
• Sistema de residuos reducidos en MathWorld