Grupo multiplicativo de módulos inteiros n -Multiplicative group of integers modulo n

Na aritmética modular , os inteiros coprime (relativamente primo) para n do conjunto de n inteiros não negativos formam um grupo sob o módulo de multiplicação n , chamado de grupo multiplicativo de módulo n de inteiros . Equivalentemente, os elementos desse grupo podem ser pensados ​​como classes de congruência , também conhecidas como resíduos módulo n , que são coprimos a n . Conseqüentemente, outro nome é o grupo de classes de resíduos primitivos módulo n . Na teoria dos anéis , um ramo da álgebra abstrata , é descrito como o grupo de unidades do anel de inteiros módulo n . Aqui, unidades referem-se a elementos com inverso multiplicativo , que, neste anel, são exatamente aqueles coprimos de n . ${\ displaystyle \ {0,1, \ dots, n-1 \}}$

Estrutura algébrica → Teoria de grupos Teoria de grupos
Noções básicas Subgrupo Subgrupo normal Grupo de quociente Produto (semi) direto Homomorfismos de grupo núcleo imagem soma direta produto de grinalda simples finito infinito contínuo multiplicativo aditivo cíclico abeliano diédrico nilpotente solucionável açao Glossário da teoria dos grupos Lista de tópicos de teoria de grupo
Grupos finitos Classificação de grupos finitos simples cíclico alternando Tipo de mentira esporádico Teorema de Cauchy Teorema de Lagrange Teoremas de Sylow Teorema de Hall p-grupo Grupo abeliano elementar Grupo Frobenius Multiplicador Schur Grupo simétrico S n Klein quatro grupos V Grupo diédrico D n Quaternion grupo Q Grupo dicíclico Dic n
Grupos discretos Treliças Inteiros ( )${\ displaystyle \ mathbb {Z}}$ Grupo livre Grupos modulares PSL (2, )${\ displaystyle \ mathbb {Z}}$ SL (2, )${\ displaystyle \ mathbb {Z}}$ Grupo aritmético Malha Grupo hiperbólico
Grupos topológicos e de Lie Solenóide Círculo GL linear geral ( n ) SL linear especial ( n ) Ortogonal O ( n ) E Euclidiano ( n ) SO ortogonal especial ( n ) Unitária U ( n ) SU unitário especial ( n ) Sp simplético ( n ) G 2 F 4 E 6 E 7 E 8 Lorentz Poincaré Conforme Difeomorfismo Ciclo Grupo de Lie dimensional infinito O (∞) SU (∞) Sp (∞)
Grupos algébricos Grupo algébrico linear Grupo redutor Variedade abeliana Curva elíptica
v t e

Este grupo de quocientes , geralmente denotado , é fundamental na teoria dos números . Ele encontrou aplicações em criptografia , fatoração de inteiros e testes de primalidade . É um abelian , finito grupo cuja ordem é dada pela função totient de Euler : para Prime n o grupo é cíclica e, em geral, a estrutura é fácil de descrever, mas mesmo para o primeiro- n fórmula geral não para encontrar geradores é conhecido. ${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {\ times}}$${\ displaystyle | (\ mathbb {Z} / n \ mathbb {Z}) ^ {\ times} | = \ varphi (n).}$

Axiomas de grupo

É um exercício direto mostrar que, sob multiplicação, o conjunto de classes de congruência módulo n que são coprimes para n satisfaz os axiomas para um grupo abeliano .

De fato, a é coprime com n se e somente se mdc ( a , n ) = 1 . Inteiros na mesma classe de congruência a ≡ b (mod n ) satisfazem mdc ( a , n ) = mdc ( b , n ) , portanto, um é coprime para n se e somente se o outro for. Assim, a noção de classes de congruência módulo n que são coprime com n está bem definida.

Como mdc ( a , n ) = 1 e mdc ( b , n ) = 1 implica mdc ( ab , n ) = 1 , o conjunto de classes coprime para n é fechado sob multiplicação.

Número inteiro de multiplicação aspectos, as classes de congruência, isto é, um ≡ um ' e b ≡ b' (mod n ) implica ab ≡ A'B' (mod n ) . Isso implica que a multiplicação é associativa, comutativa e que a classe de 1 é a identidade multiplicativa única.

Finalmente, dado a , o inverso multiplicativo de um módulo n é um inteiro x satisfazendo um eixo ≡ 1 (mod n ) . Existe precisamente quando um é coprime para n , porque, nesse caso, GCD ( a , n ) = 1 e por lema de Bézout existem números inteiros x e y satisfazendo ax + ny = 1 . Observe que a equação ax + ny = 1 implica que x é coprime com n , então o inverso multiplicativo pertence ao grupo.

Notação

O conjunto de (classes de congruência de) inteiros módulo n com as operações de adição e multiplicação é um anel . É denotado   ou    (a notação refere-se a tomar o quociente do módulo de inteiros do ideal ou consistindo nos múltiplos de n ). Fora da teoria dos números, a notação mais simples é freqüentemente usada, embora possa ser confundida com os inteiros p -adic quando n é um número primo. ${\ displaystyle \ mathbb {Z} / n \ mathbb {Z}}$${\ displaystyle \ mathbb {Z} / (n)}$ ${\ displaystyle n \ mathbb {Z}}$${\ displaystyle (n)}$${\ displaystyle \ mathbb {Z} _ {n}}$

O grupo multiplicativo de módulos inteiros n , que é o grupo de unidades neste anel, pode ser escrito como (dependendo do autor)   (para Einheit alemão , que se traduz como unidade ) , ou notações semelhantes. Este artigo usa${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {\ times},}$   ${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {*},}$   ${\ displaystyle \ mathrm {U} (\ mathbb {Z} / n \ mathbb {Z}),}$   ${\ displaystyle \ mathrm {E} (\ mathbb {Z} / n \ mathbb {Z})}$${\ displaystyle \ mathbb {Z} _ {n} ^ {*}}$${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {\ times}.}$

A notação se refere ao grupo cíclico de ordem n . É isomórfico ao grupo de inteiros módulo n sob adição. Observe que ou também pode se referir ao grupo adicionado. Por exemplo, o grupo multiplicativo de um p primo é cíclico e, portanto, isomórfico ao grupo aditivo , mas o isomorfismo não é óbvio. ${\ displaystyle \ mathrm {C} _ {n}}$${\ displaystyle \ mathbb {Z} / n \ mathbb {Z}}$${\ displaystyle \ mathbb {Z} _ {n}}$${\ displaystyle (\ mathbb {Z} / p \ mathbb {Z}) ^ {\ times}}$${\ displaystyle \ mathbb {Z} / (p-1) \ mathbb {Z}}$

Estrutura

A ordem do grupo multiplicativo de módulos inteiros n é o número de inteiros em coprime para n . É dado pela função totiente de Euler : (sequência A000010 no OEIS ). Para o primeiro- p , . ${\ displaystyle \ {0,1, \ dots, n-1 \}}$${\ displaystyle | (\ mathbb {Z} / n \ mathbb {Z}) ^ {\ times} | = \ varphi (n)}$${\ displaystyle \ varphi (p) = p-1}$

Caso cíclico

O grupo é cíclico se e somente se n for 1, 2, 4, p ^k ou 2 p ^k , onde p é um primo ímpar ek > 0 . Para todos os outros valores de n, o grupo não é cíclico. Isso foi provado pela primeira vez por Gauss . ${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {\ times}}$

Isso significa que para estes n :

${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {\ times} \ cong \ mathrm {C} _ {\ varphi (n)},}$ Onde ${\ displaystyle \ varphi (p ^ {k}) = \ varphi (2p ^ {k}) = p ^ {k} -p ^ {k-1}.}$

Por definição, o grupo é cíclico se e somente se tiver um gerador g (um conjunto gerador { g } de tamanho um), ou seja, as potências dão todos os resíduos possíveis módulo n coprime para n (as primeiras potências dão a cada um exatamente uma vez ) Um gerador de é chamado de módulo de raiz primitiva n . Se houver algum gerador, então existem . ${\ displaystyle g ^ {0}, g ^ {1}, g ^ {2}, \ dots,}$${\ displaystyle \ varphi (n)}$${\ displaystyle g ^ {0}, \ dots, g ^ {\ varphi (n) -1}}$${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {\ times}}$${\ displaystyle \ varphi (\ varphi (n))}$

Poderes de 2

Módulo 1 quaisquer dois inteiros são congruentes, ou seja, há apenas uma classe de congruência, [0], coprime para 1. Portanto, é o grupo trivial com φ (1) = 1 elemento. Por causa de sua natureza trivial, o caso de congruências módulo 1 é geralmente ignorado e alguns autores optam por não incluir o caso de n = 1 em declarações de teoremas. ${\ displaystyle (\ mathbb {Z} / 1 \, \ mathbb {Z}) ^ {\ times} \ cong \ mathrm {C} _ {1}}$

Módulo 2, há apenas uma classe de congruência coprime, [1], então é o grupo trivial . ${\ displaystyle (\ mathbb {Z} / 2 \ mathbb {Z}) ^ {\ times} \ cong \ mathrm {C} _ {1}}$

Módulo 4, existem duas classes de congruência coprime, [1] e [3], portanto, o grupo cíclico com dois elementos. ${\ displaystyle (\ mathbb {Z} / 4 \ mathbb {Z}) ^ {\ times} \ cong \ mathrm {C} _ {2},}$

Módulo 8, existem quatro classes de congruência coprime, [1], [3], [5] e [7]. O quadrado de cada um deles é 1, portanto, os quatro grupos de Klein . ${\ displaystyle (\ mathbb {Z} / 8 \ mathbb {Z}) ^ {\ times} \ cong \ mathrm {C} _ {2} \ times \ mathrm {C} _ {2},}$

Módulo 16, existem oito classes de congruência coprime [1], [3], [5], [7], [9], [11], [13] e [15]. é o subgrupo de 2 torção (ou seja, o quadrado de cada elemento é 1), portanto, não é cíclico. As potências de 3 são um subgrupo de ordem 4, assim como as potências de 5,   portanto${\ displaystyle \ {\ pm 1, \ pm 7 \} \ cong \ mathrm {C} _ {2} \ times \ mathrm {C} _ {2},}$${\ displaystyle (\ mathbb {Z} / 16 \ mathbb {Z}) ^ {\ times}}$${\ displaystyle \ {1,3,9,11 \}}$${\ displaystyle \ {1,5,9,13 \}.}$${\ displaystyle (\ mathbb {Z} / 16 \ mathbb {Z}) ^ {\ times} \ cong \ mathrm {C} _ {2} \ times \ mathrm {C} _ {4}.}$

O padrão mostrado por 8 e 16 é válido para potências superiores 2 ^k , k > 2 : é o subgrupo de 2 torção (portanto, não é cíclico) e as potências de 3 são um subgrupo cíclico de ordem 2 ^{k - 2} , então${\ displaystyle \ {\ pm 1,2 ^ {k-1} \ pm 1 \} \ cong \ mathrm {C} _ {2} \ times \ mathrm {C} _ {2},}$${\ displaystyle (\ mathbb {Z} / 2 ^ {k} \ mathbb {Z}) ^ {\ times}}$${\ displaystyle (\ mathbb {Z} / 2 ^ {k} \ mathbb {Z}) ^ {\ times} \ cong \ mathrm {C} _ {2} \ times \ mathrm {C} _ {2 ^ {k -2}}.}$

Números compostos gerais

Pelo teorema fundamental dos grupos abelianos finitos , o grupo é isomórfico a um produto direto de grupos cíclicos de ordens de potência primária. ${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {\ times}}$

Mais especificamente, o teorema do resto chinês diz que se então o anel é o produto direto dos anéis correspondentes a cada um de seus fatores de potência principais: ${\ displaystyle \; \; n = p_ {1} ^ {k_ {1}} p_ {2} ^ {k_ {2}} p_ {3} ^ {k_ {3}} \ dots, \;}$${\ displaystyle \ mathbb {Z} / n \ mathbb {Z}}$

${\ displaystyle \ mathbb {Z} / n \ mathbb {Z} \ cong \ mathbb {Z} / {p_ {1} ^ {k_ {1}}} \ mathbb {Z} \; \ times \; \ mathbb { Z} / {p_ {2} ^ {k_ {2}}} \ mathbb {Z} \; \ times \; \ mathbb {Z} / {p_ {3} ^ {k_ {3}}} \ mathbb {Z } \ dots \; \;}$

Da mesma forma, o grupo de unidades é o produto direto dos grupos correspondentes a cada um dos fatores de potência principais: ${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {\ times}}$

${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {\ times} \ cong (\ mathbb {Z} / {p_ {1} ^ {k_ {1}}} \ mathbb {Z}) ^ {\ times} \ times (\ mathbb {Z} / {p_ {2} ^ {k_ {2}}} \ mathbb {Z}) ^ {\ times} \ times (\ mathbb {Z} / {p_ { 3} ^ {k_ {3}}} \ mathbb {Z}) ^ {\ times} \ dots \ ;.}$

Para cada potência primária ímpar, o fator correspondente é o grupo cíclico de ordem , que pode ser fatorado em grupos cíclicos de ordens de potência primária. Para potências de 2, o fator não é cíclico, a menos que k = 0, 1, 2, mas fatores em grupos cíclicos como descrito acima. ${\ displaystyle p ^ {k}}$${\ displaystyle (\ mathbb {Z} / {p ^ {k}} \ mathbb {Z}) ^ {\ times}}$${\ displaystyle \ varphi (p ^ {k}) = p ^ {k} -p ^ {k-1}}$${\ displaystyle (\ mathbb {Z} / {2 ^ {k}} \ mathbb {Z}) ^ {\ times}}$

A ordem do grupo é o produto das ordens dos grupos cíclicos no produto direto. O expoente do grupo, ou seja, o mínimo múltiplo comum das ordens nos grupos cíclicos, é dado pela função de Carmichael (sequência A002322 no OEIS ). Em outras palavras, é o menor número tal que para cada um coprime para n , detém. Ele se divide e é igual a ele se e somente se o grupo é cíclico. ${\ displaystyle \ varphi (n)}$ ${\ displaystyle \ lambda (n)}$${\ displaystyle \ lambda (n)}$${\ displaystyle a ^ {\ lambda (n)} \ equiv 1 {\ pmod {n}}}$${\ displaystyle \ varphi (n)}$

Subgrupo de testemunhas falsas

Se n é composto, existe um subgrupo do grupo multiplicativo, denominado "grupo de falsas testemunhas", em que os elementos, quando elevados à potência n - 1 , são congruentes a 1 módulo n . (Porque o resíduo 1 quando elevado a qualquer potência é congruente a 1 módulo n , o conjunto de tais elementos não é vazio.) Pode-se dizer, por causa do Pequeno Teorema de Fermat , que tais resíduos são "falsos positivos" ou "falsas testemunhas" para a primalidade do n . O número 2 é o resíduo mais frequentemente usado nesta verificação de primalidade básica, portanto, 341 = 11 × 31 é famoso porque 2 ³⁴⁰ é congruente com 1 módulo 341 e 341 é o menor número composto (em relação a 2). Para 341, o subgrupo de testemunhas falsas contém 100 resíduos e, portanto, é de índice 3 dentro do mod de grupo multiplicativo de 300 elementos 341.

Exemplos

n = 9

O menor exemplo com um subgrupo não trivial de testemunhas falsas é 9 = 3 × 3 . Existem 6 resíduos coprime com 9: 1, 2, 4, 5, 7, 8. Visto que 8 é congruente com −1 módulo 9 , segue-se que 8 ⁸ é congruente com 1 módulo 9. Portanto, 1 e 8 são falsos positivos para a "primalidade" de 9 (já que 9 não é realmente primo). Na verdade, esses são os únicos, então o subgrupo {1,8} é o subgrupo das testemunhas falsas. O mesmo argumento mostra que n - 1 é uma "falsa testemunha" para qualquer composto ímpar n .

n = 91

Para n = 91 (= 7 × 13), há resíduos coprime para 91, metade deles (ou seja, 36 deles) são falsas testemunhas de 91, a saber, 1, 3, 4, 9, 10, 12, 16, 17 , 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82 , 87, 88 e 90, uma vez que para esses valores de x , x ⁹⁰ é congruente com 1 mod 91. ${\ displaystyle \ varphi (91) = 72}$

n = 561

n = 561 (= 3 × 11 × 17) é um número de Carmichael , portanto s ⁵⁶⁰ é congruente a 1 módulo 561 para qualquer co-crime s inteiro com 561. O subgrupo de testemunhas falsas não é, neste caso, adequado; é todo o grupo de unidades multiplicativas módulo 561, que consiste em 320 resíduos.

Exemplos

Esta tabela mostra a decomposição cíclica de e um conjunto gerador para n ≤ 128. A decomposição e os conjuntos geradores não são únicos; por exemplo, ${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {\ times}}$

${\ displaystyle \ displaystyle {\ begin {align} (\ mathbb {Z} / 35 \ mathbb {Z}) ^ {\ times} & \ cong (\ mathbb {Z} / 5 \ mathbb {Z}) ^ {\ times} \ times (\ mathbb {Z} / 7 \ mathbb {Z}) ^ {\ times} \ cong \ mathrm {C} _ {4} \ times \ mathrm {C} _ {6} \ cong \ mathrm { C} _ {4} \ times \ mathrm {C} _ {2} \ times \ mathrm {C} _ {3} \ cong \ mathrm {C} _ {2} \ times \ mathrm {C} _ {12} \ cong (\ mathbb {Z} / 4 \ mathbb {Z}) ^ {\ times} \ times (\ mathbb {Z} / 13 \ mathbb {Z}) ^ {\ times} \\ & \ cong (\ mathbb {Z} / 52 \ mathbb {Z}) ^ {\ times} \ end {alinhado}}}$

(mas ). A tabela abaixo lista a decomposição mais curta (entre essas, a lexicograficamente primeiro é escolhida - isso garante que os grupos isomórficos sejam listados com as mesmas decomposições). O conjunto gerador também é escolhido para ser o mais curto possível e, para n com raiz primitiva, a menor raiz primitiva módulo n é listada. ${\ displaystyle \ not \ cong \ mathrm {C} _ {24} \ cong \ mathrm {C} _ {8} \ times \ mathrm {C} _ {3}}$

Por exemplo, pegue . Então significa que a ordem do grupo é 8 (ou seja, há 8 números menores que 20 e coprime para isso); significa que a ordem de cada elemento divide 4, ou seja, a quarta potência de qualquer número coprime a 20 é congruente a 1 (mod 20). O conjunto {3,19} gera o grupo, o que significa que cada elemento de é da forma 3 ^a × 19 ^b (onde a é 0, 1, 2 ou 3, porque o elemento 3 tem ordem 4, e da mesma forma b é 0 ou 1, porque o elemento 19 tem ordem 2). ${\ displaystyle (\ mathbb {Z} / 20 \ mathbb {Z}) ^ {\ times}}$${\ displaystyle \ varphi (20) = 8}$${\ displaystyle \ lambda (20) = 4}$${\ displaystyle (\ mathbb {Z} / 20 \ mathbb {Z}) ^ {\ times}}$

Os menores mod n da raiz primitiva são (0 se nenhuma raiz existir)

0, 1, 2, 3, 2, 5, 3, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3, 5, 2, 0, 0, 7, 5, 0, 2, 7, 2, 0, 2, 0, 3, 0, 0, 3, 0, 0, 2, 3, 0, 0, 6, 0, 3, 0, 0, 5, 5, 0, 3, 3, 0, 0, 2, 5, 0, 0, 0, 3, 2, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 7, 0, 5, 5, 0, 0, 0, 0, 3, 0, 2, 7, 2, 0, 0, 3, 0, 0, 3, 0, ... (sequência A046145 no OEIS )

Os números dos elementos em um conjunto gerador mínimo de mod n são

0, 0, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 3, 1, 2, 1, 2, 2, 1, 1, 3, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 3, 1, 1, 1, 3, 2, 1, 2, 3, 1, 2, ... (sequência A046072 no OEIS )

Veja também

• Fatoração de curva elíptica Lenstra

Notas

Referências

O Disquisitiones Arithmeticae foi traduzido do latim ciceroniano de Gauss para o inglês e o alemão . A edição alemã inclui todos os seus artigos sobre a teoria dos números: todas as provas de reciprocidade quadrática , a determinação do sinal da soma de Gauss , as investigações sobre a reciprocidade biquadrática e notas não publicadas.

• Gauss, Carl Friedrich; Clarke, Arthur A. (tradutor para o inglês) (1986), Disquisitiones Arithmeticae (Segunda, edição corrigida) , Nova York: Springer , ISBN 978-0-387-96254-2
• Gauss, Carl Friedrich; Maser, H. (tradutor para o alemão) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Segunda edição) , New York: Chelsea, ISBN 978-0-8284-0191-3
• Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (segunda edição) , Boston: Birkhäuser, ISBN 978-0-8176-3743-9
• Vinogradov, IM (2003), "§ VI PRIMITIVE ROOTS AND INDICES" , Elements of Number Theory , Mineola, NY: Dover Publications, pp. 105-121, ISBN 978-0-486-49530-9

links externos

• Weisstein, Eric W. "Modulo Multiplication Group" . MathWorld .
• Weisstein, Eric W. "Primitive Root" . MathWorld .
• Ferramenta baseada na web para computar tabelas de grupos interativamente por John Jones