Artigos

5.3: A existência de raízes primitivas - matemática


Nesta seção, demonstramos quais inteiros têm raízes primitivas. Começamos mostrando que toda potência de um primo ímpar tem uma raiz primitiva e, para fazer isso, começamos mostrando que todo quadrado de um primo ímpar tem uma raiz primitiva.

Se (p ) é um primo ímpar com raiz primitiva (r ), então pode-se ter (r ) ou (r + p ) como um módulo de raiz primitiva (p ^ 2 ).

Observe que, como (r ) é um módulo de raiz primitiva (p ), então [ord_pr = phi (p) = p-1. ] Let (m = ord_ {p ^ 2} r ) , então [r ^ m equiv 1 (mod p ^ 2). ] Assim, [r ^ m equiv 1 (mod p). ] Pelo Teorema 54, temos [p-1 mid m. ] Pelo Exercício 7 da seção 6.1, também temos que [m mid phi (p ^ 2). ] Além disso, ( phi (p ^ 2) = p (p-1) ) e, portanto, (m ) divide (p ) ou (p-1 ). E desde (p-1 mid m ) então temos [m = p-1 mbox {ou} m = p (p-1). ] Se (m = p (p -1) ) e (ord_ {p ^ 2} r = phi (p ^ 2) ) então (r ) é um módulo de raiz primitiva (p ^ 2 ). Caso contrário, temos (m = p-1 ) e, portanto, [r ^ {p-1} equiv 1 (mod p ^ 2). ] Seja (s = r + p ). Então (s ) também é um módulo de raiz primitiva (p ). Portanto, (ord_ {p ^ 2} s ) é igual a (p-1 ) ou (p (p-1) ). Mostraremos que (ord_ {p ^ 2} s neq p-1 ) de forma que (ord_ {p ^ 2} s = p (p-1) ). Observe que [ begin {alinhados} s ^ {p-1} = (r + p) ^ {p-1} & = & r ^ {p-1} + (p-1) r ^ {p-2} p + ... + p ^ {p-1} & = & r ^ {p-1} + (p-1) pr ^ {p-2} (mod p ^ 2). end {alinhado} ] Portanto, [p ^ 2 mid s ^ {p-1} - (1-pr ^ {p-2}. ] Observe também que se [p ^ 2 mid (s ^ {p-1} -1), ] então [p ^ 2 mid pr ^ {p-2}. ] Assim, temos [p mid r ^ {p-2} ] que é impossível porque (p nmid r ). Como (ord_ {p ^ 2} s neq p-1 ), podemos concluir que [ord_ ​​{p ^ 2} s = p (p-1) = phi (p ^ 2) . ] Assim, (s = r + p ) é uma raiz primitiva de (p ^ 2 ).

Observe que 7 tem 3 como raiz primitiva. Tanto (ord_ {49} 3 = 6 ) ou (ord_ {49} 3 = 42 ). Mas desde (3 ^ 6 não equiv 1 (mod 49) ). Portanto, (ord_ {49} 3 = 42 ). Portanto, 3 é uma raiz primitiva de 49.

Agora mostramos que qualquer potência de um primo ímpar tem uma raiz primitiva.

Seja (p ) um primo ímpar. Então, qualquer potência de (p ) é uma raiz primitiva. Além disso, se (r ) é um módulo raiz primitivo (p ^ 2 ), então (r ) é um módulo raiz primitivo (p ^ m ) para todos os inteiros positivos (m ).

Pelo Teorema 62, sabemos que qualquer primo (p ) tem uma raiz primitiva (r ) que também é um módulo de raiz primitiva (p ^ 2 ), portanto [ label {1} ​​p ^ 2 nmid (r ^ {p-1} -1). ] Provaremos por indução que [ label {2} p ^ m nmid (r ^ {p ^ {m-2} (p-1)} -1) ] para todos os inteiros (m geq 2 ). Depois de provar a congruência acima, mostramos que (r ) também é um módulo raiz primitivo (p ^ m ). Seja (n = ord_ {p ^ m} r ). Pelo Teorema 54, sabemos que (n mid phi (p ^ m) ). Além disso, sabemos que ( phi (p ^ m) = p ^ m (p-1) ). Portanto, (n mid p ^ m (p-1) ). Por outro lado, porque [p ^ m mid (r ^ n- 1), ] também sabemos que [p mid (r ^ n-1). ] Desde ( phi (p) = p-1 ), vemos que pelo Teorema 54, temos (n = l (p-1) ). também (n mid p ^ {m-1} (p-1) ), temos que (n = p ^ s (p-1) ), onde (0 leq s leq m- 1 ). Se (n = p ^ s (p-1) ) com (s leq m-2 ), então [p ^ k mid r ^ {p ^ {m-2} (p-1) } -1, ] que é uma contradição. Portanto, [ord_ ​​{p ^ m} r = phi (p ^ m). ]

Provamos agora ([2]) por indução. Suponha que nossa afirmação seja verdadeira para todos (m geq 2 ). Então [p ^ m nmid (r ^ {p ^ {m-2} (p-1)} - 1). ] Porque ((r, p) = 1 ), vemos que (( r, p ^ {m-1}) = 1 ). Também sabemos do teorema de Euler que [p ^ {m-1} mid (r ^ {p ^ {m-2} (p-1)} - 1). ] Portanto, existe um inteiro (k ) de modo que [r ^ {p ^ {m-2} (p-1)} = 1 + kp ^ {m-1}. ] onde (p nmid k ) porque (r ^ {p ^ {m-2} (p-1)} não equiv 1 (mod p ^ m) ). Assim, temos agora [ begin {alinhados} r ^ {p ^ {m-1} (p-1)} & = & (1 + kp ^ {m-1}) ^ p & equiv & 1 + kp ^ m (mod p ^ {m + 1}) end {alinhado} ] Porque (p nmid k ), temos [p ^ {m + 1} nmid (r ^ {p ^ { m-1} (p-1)} - 1). ]

Como 3 é uma raiz primitiva de 7, então 3 é uma raiz primitiva para (7 ^ k ) para todos os inteiros positivos (k ).

No teorema a seguir, provamos que nenhuma potência de 2, diferente de 2 ou 4, tem uma raiz primitiva e isso ocorre porque quando (m ) é um número inteiro ímpar, (ord_2 ^ km neq phi (2 ^ k) ) e isso ocorre porque (2 ^ k mid (a ^ { phi (2 ^ k) / 2} -1) ).

Se (m ) for um inteiro ímpar, e se (k geq 3 ) for um inteiro, então [m ^ {2 ^ {k-2}} equiv 1 (mod 2 ^ k). ]

Provamos o resultado por indução. Se (m ) for um número inteiro ímpar, então (m = 2n + 1 ) para algum número inteiro (n ). Portanto, [m ^ 2 = 4n ^ 2 + 4n + 1 = 4n (n + 1) +1. ] Segue-se que (8 mid (m ^ 2-1) ).

Suponha agora que [2 ^ k mid (m ^ {2 ^ {k-2}} - 1). ] Então, há um inteiro (q ) tal que [m ^ {2 ^ {k- 2}} = 1 + q.2 ^ {k}. ] Assim, elevando os dois lados ao quadrado, obtemos [m ^ {2 ^ {k-1}} = 1 + q.2 ^ {k + 1} + q ^ 22 ^ {2k}. ] Assim, [2 ^ {k + 1} mid (m ^ {2 ^ {k-1}} - 1). ]

Observe agora que 2 e 4 têm raízes primitivas 1 e 3, respectivamente.

Agora listamos o conjunto de inteiros que não possuem raízes primitivas.

Se (m ) não for (p ^ a ) ou (2p ^ a ), então (m ) não tem uma raiz primitiva.

Vamos (m = p_1 ^ {s_1} p_2 ^ {s_2} ... p_i ^ {s_i} ). Se (m ) tem uma raiz primitiva (r ), então (r ) e (m ) são relativamente primos e (ord_mr = phi (m) ). Também temos, temos ((r, p ^ s) = 1 ) onde (p ^ s ) é dos primos na fatoração de (m ). Pelo teorema de Euler, temos [p ^ s mid (r ^ { phi (p ^ s)} - 1). ] Agora vamos [L = [ phi (p_1 ^ {s_1}), phi (p_2 ^ {s_2}), ..., phi (p_i ^ {s_i})]. ] Sabemos que [r ^ L equiv 1 (mod p_k ^ {s_k}) ] para todos (1 leq k leq m ). Assim, usando o Teorema do Restante Chinês, obtemos [m mid (r ^ L-1), ] que leva a (ord_mr = phi (m) leq L ). Agora porque [ phi (m) = phi (p_1 ^ {s_1}) phi (p_2 ^ {s_2}) ... phi (p_n ^ {s_n}) leq [ phi (p_1 ^ {s_1 }), phi (p_2 ^ {s_2}), ..., phi (p_n ^ {s_n})]. ] Agora, a desigualdade acima é válida apenas se [ phi (p_1 ^ {s_1}), phi (p_2 ^ {s_2}), ..., phi (p_n ^ {s_n}) ] são relativamente primos. Observe agora que pelo Teorema 41, [ phi (p_1 ^ {s_1}), phi (p_2 ^ {s_2}), ..., phi (p_n ^ {s_n}) ] não são relativamente primos, a menos que (m = p ^ s ) ou (m = 2p ^ s ) onde (p ) é um primo ímpar e (t ) é qualquer número inteiro positivo.

Agora mostramos que todos os inteiros da forma (m = 2p ^ s ) têm raízes primitivas.

Considere um primo (p neq 2 ) e deixe (s ) ser um inteiro positivo, então (2p ^ s ) tem uma raiz primitiva. Na verdade, se (r ) é um módulo de raiz primitiva ímpar (p ^ s ), então também é um módulo de raiz primitiva (2p ^ s ), mas se (r ) é par, ( r + p ^ s ) é um módulo de raiz primitiva (2p ^ s ).

Se (r ) é um módulo de raiz primitiva (p ^ s ), então [p ^ s mid (r ^ { phi (p ^ s)} - 1) ] e nenhum expoente positivo menor que ( phi (p ^ s) ) tem esta propriedade. Observe também que [ phi (2p ^ s) = phi (p ^ s), ] de modo que [p ^ s mid (r ^ { phi (2p ^ s)} - 1). ]

Se (r ) for ímpar, então [2 mid (r ^ { phi (2p ^ s)} - 1). ] Assim, pelo Teorema 56, obtemos [2p ^ s mid (r ^ { phi (2p ^ s)} - 1). ] É importante notar que nenhuma potência menor de (r ) é congruente com 1 módulo (2p ^ s ). Este poder também seria congruente a 1 módulo (p ^ s ) contradizendo que (r ) é uma raiz primitiva de (p ^ s ). Segue-se que (r ) é um módulo raiz primitivo (2p ^ s ).

Enquanto, se (r ) é par, então (r + p ^ s ) é ímpar. Portanto, [2 mid ((r + p ^ s) ^ { phi (2p ^ s)} - 1). ]

Porque (p ^ s mid (r + p ^ sr) ), vemos que [p ^ s mid ((r + p ^ s) ^ { phi (2p ^ s)} - 1). ] Como resultado, vemos que (2p ^ s mid ((r + p ^ s) ^ { phi (2p ^ s)} - 1) ) e uma vez que para nenhuma potência menor de (r + p ^ s ) é congruente a 1 módulo (2p ^ s ), vemos que (r + p ^ s ) é um módulo raiz primitivo (2p ^ s ).

Como resultado, pelo Teorema 63, Teorema 65 e Teorema 66, vemos que

O inteiro positivo (m ) tem uma raiz primitiva se e somente se (n = 2,4, p ^ s ) ou (2p ^ s )

para primo (p neq 2 ) e (s ) é um número inteiro positivo.
Exercícios

  1. Qual dos seguintes números inteiros 4, 12, 28, 36, 125 tem uma raiz primitiva.
  2. Encontre uma raiz primitiva de 4, 25, 18.
  3. Encontre todas as raízes primitivas módulo 22.
  4. Mostre que há o mesmo número de raízes primitivas módulo (2p ^ s ) e módulo (p ^ s ), onde (p ) é um primo ímpar e (s ) é um inteiro positivo .
  5. Encontre todas as raízes primitivas módulo 25.
  6. Mostre que o inteiro (n ) tem uma raiz primitiva se e somente se as únicas soluções da congruência (x ^ 2 equiv 1 (mod n) ) são (x equiv pm1 (mod n) ).

Prova de existência de raízes primitivas

No meu livro (Teoria Elementar dos Números, Stillwell), o exercício 3.9.1 pede para dar uma prova alternativa da existência de uma raiz primitiva para qualquer primo.

Seja $ p $ primo e considere o grupo $ mathbb/ p mathbb$.

Suponha que os elementos diferentes de zero $ text p $ tem pedido máximo $ n & lt p - 1 $. Mostre que isto implica $ x ^ n equiv 1 ( text p) $ para todos os $ p - 1 $ valores diferentes de zero de $ x $, $ text p $, ao contrário do teorema de congruência polinomial de Lagrange.

O que eu considerei até agora é que todos os elementos diferentes de zero do grupo $ mathbb/ p mathbb$ gera subgrupos de ordem $ k leq n & lt p - 1 $, de modo que $ k mid p - 1 $ (pelo teorema de Lagrange para grupos). Porém, mostrar que $ k mid n $ me escapa. Mais alguma ideia?


Não existe uma fórmula geral para encontrar uma raiz primitiva. Normalmente, o que você faz é escolher um número e testar. Depois de encontrar uma raiz primitiva, você encontrará todas as outras.

Como você testa

Para testar se $ a $ é uma raiz primitiva de $ p $, você precisa fazer o seguinte. Primeiro, seja $ s = phi (p) $ onde $ phi () $ é a função totiente de Euler. Se $ p $ for primo, então $ s = p-1 $. Então você precisa determinar todos os fatores primos de $ s $: $ p_1, ldots, p_k $. Finalmente, calcule $ a ^ mod p $ para todos os $ i = 1 ldots k $, e se você encontrar $ 1 $ entre os resíduos, então NÃO é uma raiz primitiva, caso contrário, é.

Então, basicamente você precisa calcular e verificar os números de $ k $, onde $ k $ é o número de diferentes fatores primos em $ phi (p) $.

Vamos encontrar a raiz primitiva mais baixa de $ 761 $:

  • $ s = phi (761) = 760 = 2 ^ 3 times5 times19 $
  • os poderes para testar são: $ 760/2 = 380 $, $ 760/5 = 152 $ e $ 760/19 = 40 $ (apenas 3 em vez de testar todos eles)
  • teste 2:
    • $ 2 ^ <380> equiv 1 mod 761 $ ops
    • $ 3 ^ <380> equiv -1 mod 761 $ OK
    • $ 3 ^ <152> equiv 1 mod 761 $ ops
    • $ 5 ^ <380> equiv 1 mod 761 $ ops
    • $ 6 ^ <380> equiv -1 mod 761 $ OK
    • $ 6 ^ <152> equiv 67 mod 761 $ OK
    • $ 6 ^ <40> equiv -263 mod 761 $ hooray!

    Portanto, a raiz menos primitiva de 761 é 6.

    Como você escolhe

    Normalmente, você escolhe aleatoriamente, ou começando de 2 e subindo (ao procurar a raiz menos primitiva, por exemplo), ou em qualquer outra sequência dependendo de suas necessidades.

    Observe que, quando você escolhe aleatoriamente, quanto mais fatores primos existem em $ phi (p) $, menor, em geral, é a probabilidade de encontrar um ao acaso. Além disso, haverá mais poderes para testar.

    Por exemplo, se você escolher um número aleatório para testar sendo uma raiz primitiva de $ 761 $, então a probabilidade de encontrar um é aproximadamente $ frac <1> <2> times frac <4> <5> times frac <18> <19> $ ou 38%, e há 3 poderes para testar. Mas se você está procurando raízes primitivas de, digamos, $ 2311 $, então a probabilidade de encontrar uma ao acaso é de cerca de 20% e há 5 poderes para testar.

    Como você encontra todas as outras raízes primitivas

    Depois de encontrar uma raiz primitiva, você pode encontrar facilmente todas as outras. De fato, se $ a $ é um mod de raiz primitiva $ p $ e $ p $ é primo (para simplificar), então $ a $ pode gerar todos os outros restos $ 1 ldots (p-1) $ como poderes: $ a ^ 1 equiv a, a ^ 2, ldots, a ^ equiv 1 $. E $ a ^ m mod p $ é outra raiz primitiva se e somente se $ m $ e $ p-1 $ são coprimes (se $ gcd (m, p-1) = d $ então $ (a ^ m) ^ <(p-1) / d> equiv (a ^)^ equiv 1 mod p $, então precisamos de $ d = 1 $). A propósito, é exatamente por isso que você tem $ phi (p-1) $ raízes primitivas quando $ p $ é primo.

    Por exemplo, $ 6 ^ 2 = 36 $ ou $ 6 ^ <15> equiv 686 $ não são raízes primitivas de $ 761 $ porque $ gcd (2.760) = 2 & gt1 $ e $ gcd (15.760) = 5 & gt1 $, mas, para exemplo, $ 6 ^ 3 = 216 $ é outra raiz primitiva de 761.


    Subseção 10.5.1 Encontrando uma raiz root permalink superior

    Esta é uma maneira de resolver a primeira congruência. Primeiro, encontre um módulo raiz primitivo (19 ). Obviamente, poderíamos simplesmente perguntar ao Sage ou usar o Lema 10.2.3 com tentativa e erro. Em um passado não muito distante, o verso de cada texto de teoria dos números tinha uma tabela de raízes primitivas!

    Agora o que vamos fazer é tentar representar Ambas lados de começarx ^ 4 equiv 13 text <(mod> 19) end como poderes dessa raiz primitiva.

    A parte fácil é representar (x ^ 4 ) nós apenas dizemos que (x equiv 2 ^ i ) para alguns (ainda desconhecido) (i ), então beginx ^ 4 equiv left (2 ^ i right) ^ 4 equiv 2 ^ <4i> . end A parte mais difícil é descobrir qual poder de (2 ) dá (13 ). Novamente, não há atalho, embora os livros no passado tivessem enormes tabelas deles e poderes (para fácil referência). Na prática, teríamos todos os poderes de uma dada raiz primitiva disponíveis para uso com antecedência.

    Substituindo as raízes primitivas em por (x ^ 4 ) e (13 ), podemos dizer que beginx ^ 4 equiv 13 text <(mod> 19) end torna-se começo2 ^ <4i> equiv 2 ^ <5> text <(mod> 19) . End

    Este é um tipo de problema muito mais familiar. Como teríamos resolvido isso no ensino médio? Você resolveria desta forma, com equações (não congruências): begin2 ^ <4i> = 2 ^ <5> Rightarrow 4i = 5 Rightarrow i = 5/4 . End Tentaremos fazer algo muito semelhante aqui.

    O que é muito importante é que esta congruência é, em certo sentido, realmente não é mais uma congruência em ( mathbb_ <19> ). Para ser mais preciso, tudo à vista está realmente em (U_ <19> ), um grupo cíclico de ordem ( phi (19) = 18 ). Mas um grupo cíclico de ordem (18 ) seria o mesmo que pensar o módulo dezoito! Então podemos tirar os expoentes, assim como no pré-cálculo, mas fazer coisas (mod (18 )): begin4i equiv 5 text <(mod> 18) . End (Veja o Exercício 10.6.12.)

    Infelizmente, isso não tem solução. Mas descobrimos isso sem tirar cada quarta potência que existe! Na verdade, fazer isso confirma nosso resultado:

    Exemplo 10.5.1

    Vamos tentar o mesmo módulo de congruência (17 ) - isto é, podemos resolver beginx ^ 4 equiv 13 text <(mod> 17) ? end Aqui, uma raiz primitiva é (3 ), e acontece que (3 ^ 4 equiv 13 ), então podemos tentar. Isso dá begin3 ^ <4i> equiv 3 ^ 4 text <(mod> 17) Rightarrow 4i equiv 4 text <(mod> 16) ,, end que definitivamente tem soluções.

    Na verdade, existem quatro soluções ( (1,5,9,13 )) para a congruência reduzida begini equiv 1 text <(mod> 4) end portanto, há quatro soluções ( (3 ^ 1,3 ^ 5,3 ^ 9,3 ^ <13> )) para a congruência original. Vamos verificar isso:

    Você pode até vê-lo funcionando para coisas mais complicadas.

    Exemplo 10.5.2

    Se tentarmos resolver (x ^ 6 equiv 8 ) (mod (49 )), precisaremos de uma raiz primitiva de 49 3 trabalhos. Posso descobrir qual potência (3 ^ i ) de (3 ) produz (8 ):

    Então escrevemos (x = 3 ^ i ) para alguns ainda desconhecidos (i ), e obtemos begin3 ^ <6i> equiv 3 ^ <36> text <(mod> 49) , end o que nos dá começo6i equiv 36 text <(mod> phi (49) = 42) end e isso se reduz a começari equiv 6 text <(mod> 7) . end Portanto, (i = 6,13,20,27,34,41 ) todos funcionam, o que significa que (x = 3 ^ equiv 43,10,16,6,39,33 ) tudo deve funcionar.


    5.3: A existência de raízes primitivas - matemática

    Escritório: 234B, Engenharia 1
    Telefone: (312) 567-3128
    E-mail: kaul [arroba] math.iit.edu

    Horário: 15h15, terça e quinta-feira.
    Local: 103, Engenharia 1 Prédio.

    Horário de atendimento: 14h às 16h, quarta-feira, visitas e por agendamento.
    Sessões problemáticas às segundas-feiras às 17:40.

    O Apostila de informações do curso tem ampla descrição do curso - tópicos, livro-texto, política de avaliação do aluno, bem como outras informações relevantes. Leia atentamente!

    Conselhos para alunos
    Excelente conselho de Doug West sobre como escrever soluções para o dever de casa em um curso como este.
    Por que temos que aprender provas?
    Como ler matemática? Noções básicas, mais detalhes.
    Como estudar e aprender matemática.
    Em uma nota mais abstrata, aqui está uma discussão sobre Linguagem e Gramática da Matemática - que é o que você está aprendendo em um curso como este.

    Excelente conselho para alunos de matemática, especialmente aqueles que planejam fazer pós-graduação, de Terry Tao, medalhista de 2006 Fields. Leitura obrigatória.


    Teoria dos Números: em contexto e interativa

    Em breve começaremos a falar sobre criptografia e assuntos relacionados. Antes de fazermos isso, veremos nossas necessidades computacionais usando raízes primitivas para resolver algumas congruências de uma maneira legal.

    Suponha que você queira resolver uma congruência mais envolvente do que as básicas que abordamos até agora. Uma forma geral que podemos querer resolver seria semelhante a

    onde (a ) ou (b ) pode ser uma variável e (n ) seria uma potência primo. Aqui estão dois exemplos:

    Você pode pensar no primeiro como encontrar um módulo de raiz superior (n text <,> ) e o segundo como encontrar um logaritmo módulo (n text <.> )

    Como veremos abaixo, nossa estratégia geral será encontrar uma raiz primitiva (g ) de (n ) (quando isso for possível) e escrever ambas como potências de (g text <,> ). (a = g ^ i ) e (c = g ^ j ) para algum (i, j in mathbb text <.> ) Então nossa congruência se tornará

    e pensar nisso como uma solução nos expoentes (ib ) e (j ) será produtivo.

    Subseção 10.5.1 Encontrando uma raiz superior

    Com isso como introdução, vamos examinar uma maneira de resolver a primeira congruência usando essa ideia.

    Primeiro, encontre um módulo raiz primitivo (17 text <.> ) Obviamente, poderíamos apenas perguntar ao Sage e seu comando interno primitive_root, ou usar o Lema 10.2.3 com tentativa e erro. Em um passado não muito distante, o verso de cada texto de teoria dos números tinha uma tabela de raízes primitivas!

    Agora o que vamos fazer é tentar representar Ambas lados de

    como poderes dessa raiz primitiva.

    A parte fácil é representar (x ^ 3 text <> ), apenas dizemos que (x equiv 3 ^ i ) para alguns (ainda desconhecido) (i text <,> ) então

    A parte mais difícil é descobrir qual poder de (3 ) dá (5 text <.> ) Novamente, não há atalho, embora os textos de teoria dos números no passado tivessem tabelas enormes deles, e seus poderes (para referência fácil). Na prática, teríamos todos os poderes de uma dada raiz primitiva disponíveis para uso com antecedência.

    Ao substituir as raízes primitivas em por (x ^ 3 ) e (5 text <,> ), transformamos

    Este é um tipo de problema muito mais familiar. Como teríamos resolvido isso no ensino médio? Você resolveria desta forma, com equações (não congruências):

    Tentaremos fazer algo muito semelhante aqui.

    O que é muito importante é que esta congruência é, em certo sentido, realmente não é mais uma congruência em ( mathbb_ <17> text <.> ) Para ser mais preciso, tudo à vista está realmente em (U_ <17> text <,> ) um grupo cíclico de ordem ( phi (17) = 16 text <.> ) Mas um grupo cíclico de ordem (16 ) seria o mesmo que pensar no módulo dezesseis! Portanto, podemos tirar os expoentes, assim como no pré-cálculo, mas fazer coisas (mod (16 )):

    (Veja o Exercício 10.6.14 para justificar essa manipulação.)

    Uma pequena suposição e verificação (ou métodos mais poderosos anteriores no livro) mostram que (i = 7 ) é suficiente, de modo que (x = 3 ^ <7> equiv 11 ) (mod (17 )) é a solução. E descobrimos isso sem tirar todos os cubos que estavam por aí!

    Na verdade, fazer exatamente isso confirma nosso resultado. Pegamos todos os cubos começando em (2 text <,> ) e o que corresponde a (11 ) é o que queremos:

    Observe o uso de intervalo da nota 2.1.3 do Sage. Por que você acha que usamos aqui?

    Exemplo 10.5.1.

    Se mudarmos a congruência para uma quarta potência (x ^ 4 equiv 5 ) (mod (17 )), a única mudança é que agora temos que resolver (4i equiv 5 ) (mod ( 16 )). No entanto, não existem tais soluções, pois ( gcd (4,16) = 4 nmid 5 text <,> ) e confirmamos isso vendo que (5 ) não aparece nesta lista:

    Exemplo 10.5.2.

    Finalmente, vamos tentar resolver o intimamente relacionado (x ^ 3 equiv 7 ) (mod (19 )). Aqui, uma raiz primitiva é (2 text <,> ) e acontece que (2 ^ 6 equiv 7 text <,> ), portanto, podemos tentar uma solução. Nós obtemos

    que definitivamente tem soluções.

    Na verdade, existem três soluções ( (2,8,14 )) para a congruência reduzida

    portanto, há três soluções ( (2 ^ 2,2 ^ 8,2 ^ <14> )) para a congruência original. Vamos verificar isso:

    Uma estratégia semelhante pode funcionar para congruências de grau superior. (Veja [E.2.4, Teorema 8.17] para uma declaração geral sobre quando tais soluções existem, que iremos omitir por causa do espaço.)

    Exemplo 10.5.3.

    Se tentarmos resolver (x ^ 6 equiv 8 ) (mod (49 )), precisaremos de uma raiz primitiva de 49 3 trabalhos. Posso descobrir qual potência (3 ^ i ) de (3 ) produz (8 text <:> )

    Parece que é (3 ^ <36> text <.> ) Então escrevemos (x = 3 ^ i ) para alguns ainda desconhecidos (i text <,> ) e obtemos

    Portanto, (i = 6,13,20,27,34,41 ) todos funcionam, o que significa que (x = 3 ^ equiv 43,10,16,6,39,33 ) tudo deve funcionar.

    Subseção 10.5.2 Logaritmos discretos

    Da mesma forma, podemos tentar resolver exemplos logarítmicos como

    Na verdade, resolver esse problema é um exemplo do que é chamado de problema. Esses problemas são aparentemente muito, muito difíceis de resolver rapidamente, mas (!) Ninguém realmente provado isto.

    Exemplo 10.5.4.

    Vamos resolver (5 ^ x equiv 17 text <(mod> 19) text <.> ) Como observamos no Exemplo 10.5.2, uma raiz primitiva módulo 19 é 2, e podemos verificar que (5 equiv 2 ^ <16> text <(mod> 19) ) e (17 equiv 2 ^ <10> text <(mod> 19) text <.> ) Então, substituindo estes, vemos que

    Uma vez que cada um dos números nesta última congruência é par, podemos reduzir isso para (8x equiv 5 ) (mod (9 )), o que reduz ainda mais para o fácil de resolver (- x equiv 5 ) (mod (9 )).

    Tomando (x equiv -5 equiv 4 text <,> ) e tendo em mente o módulo original de (18 text <,> ) que sugere que poderíamos deixar (x equiv 4,13 ) na resolução da congruência original. E realmente

    Sage note 10.5.5. Lembrete sobre igualdade.

    Para verificar se duas coisas são iguais, lembre-se de que você pode apenas usar == com as duas expressões e ver se obtém Verdadeiro ou Falso.

    Exemplo 10.5.6.

    Vamos tentar resolver (16 ^ x equiv 13 text <(mod> 19) text <.> )

    Novamente, (2 ) é uma raiz primitiva de (19 text <,> ) e, obviamente, (16 = 2 ^ 4 text <.> ) Pode parecer mais difícil de representar (13 text < > ) é claro que poderíamos fazer isso com o computador, mas observe que (13 + 19 = 32 = 2 ^ 5 text <.> ) Às vezes, podemos realmente fazer isso manualmente!

    Assim, nossa congruência se torna

    Entretanto, como ( gcd (4,18) = 2 nmid 5 text <,> ) pela Proposição 5.1.1, esta última congruência não tem soluções, então nem a congruência original. (Acontece que (16 ) tem apenas a ordem (9 ) como um elemento de (U_ <19> text <,> ) e, evidentemente, (13 ) não é um dos elementos no subgrupo gerado por (16 text <.> ))


    Notas de matemática de Joni

    Neste artigo, provamos a existência de raízes primitivas de módulo de poderes primos, usando a teoria dos números elementares e apresentando inúmeros problemas em que raízes primitivas podem ser aplicadas. Este post é adequado, por exemplo, para treinamento olímpico.

    Introdução

    Módulo de raízes primitivas primos

    Módulos de potência principal

    No caso de potências superiores de $ p $, temos novamente um bom resultado: Se $ g $ é um módulo de raiz primitiva $ p $ e $ p ^ 2 $, é uma raiz primitiva com respeito a todas as potências. Suponha que $ g ^ k equiv 1 pmod> $. Então, pela suposição $ p (p-1) mid k $. Mostramos por indução em $ alpha $ que $ p ^ < alpha-1> (p-1) mid k. $ O caso $ alpha = 2 $ já foi considerado. Se o caso $ alpha $ foi provado, $ g ^ equiv 1 pmod> $ implica $ g ^ < frac

    > equiv 1 pmod> $ desde $ g ^ k-1 = (g ^ < frac

    > -1) (g ^ < frac

    > +. + g ^ < frac

    > +1) $ e o último fator é congruente com $ p pmod$ porque $ g ^ < frac

    > equiv 1 pmod p $. Assim, a hipótese de indução fornece $ p ^ < alpha> mid k $, e $ p-1 mid k $ já era conhecido. A afirmação agora está provada (aliás, o método que usamos para lidar com congruências $ pmod> $ pode ser generalizado para provar o chamado lema de levantamento do expoente). & # 9632

    Como $ varphi (2 ^ < alpha>) = 2 ^ < alpha-1>, $ the number $ 5 $ está muito perto de ser uma raiz primitiva e isso é suficiente para muitos aplicativos.

    Problemas solucionáveis ​​com raízes primitivas

    Problema 15. Seja $ p $ um primo. Então, a duração do período da representação decimal de $ frac <1>

    $ é $ p-1 $, se $ 10 $ é uma raiz primitiva $ pmod p $, caso contrário, o período é mais curto (é $ text_

    (10)$).

    onde $ q = p_1 ^ < alpha_1>. p_k ^ < alpha_k> $ e $ left ( frac

    right) $ é o símbolo de Legendre ($ left ( frac

    right) $ é igual a $ se $ p mid n $, e caso contrário, dá o valor $ 1 $ se $ n equiv a ^ 2 pmod p $ para algum $ a $, e dá o valor $ -1 $ caso contrário). A expressão acima é chamada de símbolo Jacobi $ pmod q $.


    Gráficos de grupos em superfícies

    14-4 O gênero de F p r

    Novamente, para abreviar, defina F p r = G F p r. Para encontrar análogos dos teoremas de Maschke e Proulx para os gêneros de grupos finitos planar e toroidal, respectivamente, Jones combinou sua análise da Seção 14-3 para o caso r = 1 com o caso r ≥ 2 desta seção. No caso geral, definimos Δ+ = <α r - l, ..., α 2 , α, 1>, uma base para Pr(α) (o espaço vetorial de todos os polinômios de grau menor que r sobre ℤp, isomórfico a ℤp r ), Onde α é uma raiz primitiva de um polinômio mônico irredutível de grau r sobre ℤp e definimos Δ× = <α k >, onde (p r − 1, k) = 1. Seja Δ = Δ+ ∪ Δx, e formar o gráfico de cores C Δ F p r, x k. Então, deixe G F p r, α k denotar que as propriedades subjacentes de incorporação do pseudógrafo não são afetadas por esta redução. Novamente, chamamos isso de gráfico de campo finito.

    O gênero do campo F p r é dado por

    Várias observações são necessárias:

    A Definição 14-8 inclui a Definição 14-6, como o caso especial r = 1.

    Se (p r − 1, k) = 1, então (p r − 1, − k) = 1 também, mas usando Δ× = <αk > em vez de <>k > simplesmente inverte todas as setas multiplicativas, de modo que os pseudógrafos subjacentes sejam isomórficos. Assim, o mínimo é efetivamente obtido em 1 2 ϕ p r - 1 geradores multiplicativos, onde ϕ é a função de euler phi.

    Para que γ F p r seja bem definido, precisamos estabelecer duas propriedades:

    Para um polinômio irredutível monic fixo m(x) de grau r sobre ℤp, G F p r, α k depende de k mas não sobre a raiz primitiva particular α do m(x) selecionado. (Veja o Problema 14-12.)

    Escolhendo um diferente m(x) Como acima produz uma coleção isomórfica de pseudógrafos. (Veja o Problema 14-13. Este problema está aberto em geral, mas a reivindicação vale para p = 4, 8, 9 e 16 - tudo de que precisamos para o restante deste capítulo. Para trabalhos posteriores, dependendo da resolução do Problema 14-13, tomaríamos o mínimo sobre todos os polinômios mônicos irredutíveis de grau r, tb.)

    Por exemplo, se p = r = 2, o único polinômio adequado é x 2 + x + 1 e nós pegamos α 2 = α + 1 para que 〈α〉 = <1, α, α + 1>. O gráfico de cores planas C(F 4, α) é dado na Figura 14-4. Usamos Δ+ = <α, 1>, adição de modelagem por α com uma aresta cruzada e Δ× = <α>.

    Agora considere p = 2 ainda, mas com r = 3. Usamos x 3 + x + 1, como no exemplo da Seção 14.2. Nós exibimos C(F 8, α) na Figura 14-5, desenhado no plano com um cruzamento. Isso estabelece que γ(F 8) ≤ 1. Para mostrar que γ(F 8) ≥ 1, podemos considerar separadamente os gráficos de cores C(F 8, α), C(F 8, α 2), e C(F 8, α 3), encontrando um subgrafo de Kuratowski em cada caso. (Esses são três gráficos mutuamente não isomórficos, como o exame das configurações dos dígitos rapidamente mostra.) Em vez disso, notamos que G 1, α, α 2 ℤ 2 3 = Q 3 em cada caso. Pelo Teorema 5-25, Q3 é exclusivamente embutido na esfera. Se pudermos mostrar que um arco multiplicativo une vértices antípodas, então G(F 8, α k ) não será planar, pelo Teorema da Curva de Jordan, uma vez que um 6-ciclo divide o plano (obtido sob projeção estereográfica) em duas regiões, com um antípoda em cada. Então, resolva a equação a + (1 + α + α 2 ) = aα k para uma = (1 + α + α 2 )(α k - 1) - 1, o único vértice inicial de tal arco. (Para a Figura 14-5, calculamos que uma = (1 + α + α 2 )(α − 1) − 1 = α 5 (α 3 ) − 1 = α 2, como é exibido na figura.) Assim α(F 8) = 1.

    Argumentos semelhantes mostram que γ F p r ≥ 2 para cada p r ≥ 16, com r ≥ 2: para p = 2, comece com K2 × K2 × K2 × K2 = C4 × C4 no toro para p ≥ 5, encontre um subgrafo de C p r homeomórfico para C5 × C5 no toro. Em ambos os casos, podemos encontrar uma aresta que não pode ser adicionada ao toro, de forma que γ F p r ≥ 1 + 1 = 2. Para p = 3 e p r ≥ 16, C3 3 é um subgrafo, e sabemos que γ(C3 3) = 7 (Teorema 7-29).

    Assim, para completar as classificações dos campos finitos planar e toroidal, temos apenas que estudar F 9. Considere a construção de F 9 fornecido na Seção 14-2, produzindo o encaixe toroidal da Figura 14-6. Mas γ(F 9) ≥ γ(C3 × C3) = 1. Assim γ(F 9) = 1.

    Coletando os resultados desta seção e da seção anterior, obtemos os dois teoremas de Jones a seguir:

    O corpo finito F p r é plano se e somente se p r = 2, 3, 4, 5, 7 ou 11.

    O corpo finito F p r é toroidal se e somente se p r = 8, 9, 13 ou 17.

    O próximo teorema fornece dois resultados assintóticos, também desenvolvidos por Jones em [J4].

    (i) F 2 r é assintoticamente 1 + 2 r − 3 (r − 4).

    (ii) F p p é assintoticamente p p + 1 4.

    Os seguintes limites [J4] serão úteis na próxima seção:


    Raízes primitivas - Álgebra, CSIR-NET Ciências Matemáticas Notas Matemáticas | EduRev

    Let Ser um inteiro positivo. UMA raiz primitiva mod n é um inteiro g tal que todo inteiro relativamente primo an é congruente a uma potência de g mod n. Ou seja, o inteiro g é uma raiz primitiva (mod n) se para cada número um relativamente primo an houver um inteiro z tal que a ≡ (g z (mod n)).

    2 é uma raiz primitiva mod 5, porque para cada número, um relativamente primo a 5 existe um. 2 z ≡ a. Todos os números relativamente primos a 5 são 1, 2, 3, 4, e cada um deles (mod 5) é ele mesmo (por exemplo 2 (mod 5) = 2).

    4 não é uma raiz primitiva mod 5, porque para cada número relativamente primo a 5 (novamente: 1, 2, 3, 4) não há uma potência de 4 que seja congruente. Potências de 4 (mod 5) são apenas congruentes com 1 ou 4. Não há potência de 4 que seja congruente com 2 ou 3.

    Quando existem raízes primitivas, muitas vezes é muito conveniente usá-las em provas e construções explícitas, por exemplo, se p é um primo ímpar eg é uma raiz primitiva mod p, os resíduos quadráticos mod p são precisamente as potências pares da raiz primitiva . As raízes primitivas também são importantes em aplicações criptológicas envolvendo o problema de log discreto, mais notavelmente o protocolo de troca de chave Diffie-Hellman.

    Terminologia e uma definição formal

    Então Z *n tem φ (n) elementos, onde φ é a função totiente de Euler.

    UMA raiz primitiva mod n é um elemento g ∈ Z *n cujos poderes geram todos Z *n. Ou seja, cada elemento b ∈ Z *n pode ser escrito como g x mod n, para algum inteiro x.

    Antecedentes e motivação

    O conjunto tem uma propriedade importante: é fechado sob o modo de multiplicação n. Ou seja, se e c é o número inteiro positivo menor que n, que é congruente com ab mod n, então também. Isso ocorre porque ab e n não têm fator comum (por fatoração única) e, portanto, c e n também não têm fator comum (porque se d | c e d | n, então d | ab também, porque ab = c + nx algum inteiro x)

    Esta propriedade, junto com outras propriedades básicas do mod n de multiplicação, implica que é um grupo em multiplicação.

    Para qualquer elemento a ∈ Z *n, considere a sequência de seus poderes . Todos os poderes de a estão no conjunto finito , então a sequência de poderes a de se repete eventualmente. Na verdade, o teorema de Euler implica que ele se repete com período

    Portanto, outra caracterização das raízes primitivas em termos desta sequência é: As raízes primitivas são os elementos para o qual a sequência de poderes de um tem mínimo período

    As potências de 1 são 1,1,1. A ordem de 1 é 1.

    Os poderes de 2 são 2,4,8,7,5,1. A ordem de 2 é 6.

    As potências de 4 são 4,7,1. A ordem de 4 é 3.

    Os poderes de 5 são 5,7,8,4,2,1. A ordem de 5 é 6.

    Os poderes de 7 são 7,4,1. A ordem de 7 é 3.

    Os poderes de 8 são 8,1. A ordem de 8 é 2.

    Portanto, as raízes primitivas mod 9 são 2 e 5.

    Existência de raízes primitivas

    As raízes primitivas não existem necessariamente mod n para qualquer n. Aqui está uma classificação completa:

    Existem raízes primitivas mod n se e somente se n = 1,2,4, p k ou 2p k onde p é um primo ímpar.

    Encontrando raízes primitivas

    A prova do teorema (parte do qual é apresentada a seguir) é essencialmente não construtiva: ou seja, não fornece uma maneira eficaz de encontrar uma raiz primitiva quando ela existe. Uma vez que uma raiz primitiva g tenha sido encontrada, as outras são fáceis de construir: simplesmente tome as potências g a onde a é relativamente primo. Mas encontrar uma raiz primitiva com eficiência é um problema computacional difícil em geral.

    Existem alguns casos especiais em que é mais fácil encontrá-los, por exemplo:

    Suponha que p seja primo tal que 2p + 1 também seja primo. (Esses p são chamados Sophie Germain primos.) Mostre que se p ≡ 1 mod 4, então 2 é uma raiz primitiva mod 2p +1.

    Solução: A questão é que a lista de possíveis ordens de elementos de é muito curto: a ordem de 2 divisões então é também Não pode ser 1 ou 2, então só precisamos descartar P. Mas é o símbolo de Legendre, pelo critério de Euler. Mas pelo segundo suplemento à reciprocidade quadrática,

    Portanto, a única possibilidade restante é que a ordem de 2 mod 2p +1 seja 2p.

    Por exemplo, isso mostra que 2 é um mod 83 de raiz primitiva.

    Formulários

    Quando há uma raiz primitiva g mod n, os elementos de Z *n pode ser escrito como Multiplying two elements corresponds to adding their exponents mod That is, the multiplicative arithmetic in Z*n reduces to additive arithmetic in

    Let k be an integer and p an odd prime number. How many nonzero kth powers are there mod p?

    The question certainly depends on the relationship between k and p. When k = 2 the answer is p-1/2 (see quadratic residues), but when k = p - 1 the answer is 1 (by Fermat's little theorem).

    As an illustration, take Then it's easy to check that g = 2 is a primitive root mod p. The ninth powers mod p are but we can consider the exponents mod 12 because So we get

    so there are four 9th powers mod 13. The exponents are multiples of 3, which is gcd. (9,13 -1). There are 13 - 1/3 = 4 of these.

    In general, since every nonzero element of Zp can be written as g a mod p for some integer x, the equation x k ≡ y mod p can be rewritten mod p. Because g is a primitive root, this happens if and only if

    So the question becomes: as a ranges over Zp-1, how many values can ak mod p-1 take on? In fact, the extended Euclidean algorithm implies that is the set of multiples of gcd

    There are exactly

    such values, so this is the answer.

    Here is another problem where it can help to write the elements of Z*p as powers of a primitive root.

    Partial proof of the theorem

    One half of this theorem is not hard to prove: Suppose where a and b are relatively prime and > 3. Suppose x is relatively prime to ab. Então desde mod a and mod b, it follows that

    Mas are both even, so their lcm is strictly less than their product. So the order of x is strictly less than So there is no primitive root mod ab.

    The only n that cannot be written in this way are and higher powers of 2. But for any odd x,

    which can be proved by the LTE lemma (or by induction). Desde there is no primitive root mod

    Some of the proof of the other direction can be found in the wiki on orders.


    Assista o vídeo: Sprawdź swoją intuicję - czy masz zdolności paranormalne? (Outubro 2021).