Sistema reducido de residuos

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

 mcd(r,n) = 1 para cada r en R ,
 R contén φ(n) elementos,
 non hai dous elementos de R congruentes módulo n. 

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 {r1, r2, ..., rφ(n)} é un sistema reducido  de residuos módulo n con n > 2, entón .
 Se {r1, r2, ..., rφ(n)} é un sistema reducido de residuos módulo n, e a é un número enteiro tal que mcd(a, n) = 1, entón {ar1, ar2, ..., arφ(n)} tamén é un sistema de residuos reducido módulo n. 
 Notas 


 Véxase tamén 
 Bibliografía 



 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

Categoría:Teoría de números