Fórum PiR2
Gostaria de reagir a esta mensagem? Crie uma conta em poucos cliques ou inicie sessão para continuar.

Dúvida sobre o Teorema Chinês dos Restos

2 participantes

Página 1 de 2 1, 2  Seguinte

Ir para baixo

Dúvida sobre o Teorema Chinês dos Restos Empty Dúvida sobre o Teorema Chinês dos Restos

Mensagem por Perceval Seg 11 Out 2021, 20:34

(Teorema Chinês dos Restos) Se mk é um inteiro positivo e mdc(mi,mj) = 1 (i ≠ j)(números primos entre si) então o sistema de congruências lineares:
x ≡ a1 (mod.m1)
x ≡ a2 (mod.m2)
...
x ≡ an-1 (mod.mn-1)
x ≡ an (mod.mn)
Tem uma única solução: x ≡ X (mod.m) m=m1m2m3...mn-1 mn

Dúvida: é possível afirmar que existem k primos tais que

[latex]a^{29}\equiv1 \pmod {p_1} \newline a^{29}\equiv1 \pmod {p_2} \newline a^{29}\equiv1 \pmod {p_3} \newline ... \newline a^{29}\equiv1 \pmod {p_k} \newline[/latex]

? Em outras palavras, existem infinitos primos tais que [latex]ord_p(a)=29?[/latex]
Perceval
Perceval
Recebeu o sabre de luz
Recebeu o sabre de luz

Mensagens : 120
Data de inscrição : 03/01/2021

Ir para o topo Ir para baixo

Dúvida sobre o Teorema Chinês dos Restos Empty Re: Dúvida sobre o Teorema Chinês dos Restos

Mensagem por SilverBladeII Ter 12 Out 2021, 09:58

Não. Supondo |a| > 1, como os primos são infinitos, basta tomar p > |a^{29}|+1
Nesse caso, o menor resíduo positivo de a^{29} mod p é a^{29} ou p+a^{29}
como a > 1, então a^{29} > 1
e p+a^{29} > |a^{29}|+1+a^{29} > 1

Como o menor resíduo positivo de a^{29} não é 1, resta que [latex]\operatorname{ord}_p{a}\neq29[/latex]
SilverBladeII
SilverBladeII
Matador
Matador

Mensagens : 452
Data de inscrição : 04/09/2019
Idade : 20
Localização : Teresina, Piauí, Brasil

Ir para o topo Ir para baixo

Dúvida sobre o Teorema Chinês dos Restos Empty Re: Dúvida sobre o Teorema Chinês dos Restos

Mensagem por Perceval Ter 12 Out 2021, 18:20

@SilverBladeII escreveu:Não. Supondo |a| > 1, como os primos são infinitos, basta tomar p > |a^{29}|+1
Nesse caso, o menor resíduo positivo de a^{29} mod p é a^{29} ou p+a^{29}
como a > 1, então a^{29} > 1
e p+a^{29} > |a^{29}|+1+a^{29} > 1

Como o menor resíduo positivo de a^{29} não é 1, resta que [latex]\operatorname{ord}_p{a}\neq29[/latex]
Bem, de fato isso é verdade, kkkk... A pergunta que eu devia ter feito na verdade era essa: dados k primos (uma quantidade finita deles), existe algum natural [latex]a[/latex] tal que 
Dúvida sobre o Teorema Chinês dos Restos Png.latex?%5C%5Ca%5E%7B29%7D%5Cequiv1%20%5Cpmod%20%7Bp_1%7D%20%5Cnewline%20a%5E%7B29%7D%5Cequiv1%20%5Cpmod%20%7Bp_2%7D%20%5Cnewline%20a%5E%7B29%7D%5Cequiv1%20%5Cpmod%20%7Bp_3%7D%20%5Cnewline%20..

?
Perceval
Perceval
Recebeu o sabre de luz
Recebeu o sabre de luz

Mensagens : 120
Data de inscrição : 03/01/2021

Ir para o topo Ir para baixo

Dúvida sobre o Teorema Chinês dos Restos Empty Re: Dúvida sobre o Teorema Chinês dos Restos

Mensagem por SilverBladeII Ter 12 Out 2021, 21:58

Oloko, existem sim hauhuahuaha
Vc pode trocar 29 por qualquer numero, acho.
e vou supor que a gente quer encontrar um a que não seja congruente a 1 módulo todo mundo, pq seria sem graça.

O teorema de Dirichlet implica que existem infinitos primos na progressão aritmética 29n+1. 
Tome então k primos nessa progressão, [latex]p_1, p_2,\dots, p_k[/latex]
Para cada j, seja
[latex]m_j=\frac{1}{p_j}\prod_{i=1}^kp_i[/latex]

Observe que [latex](p_i, m_i)=1[/latex], portanto [latex]m_i^{p_i-1}\equiv 1 \pmod{p_i}[/latex], além disso, 
[latex]m_j^{p_j-1}\equiv 0\pmod{p_i}[/latex] 
quando [latex]i\neq j[/latex].

Por último, como [latex]29 | p_i-1[/latex], então existem ao menos [latex]\varphi(29)=28[/latex] inteiros incongruentes mod p_i satisfazendo 
[latex]x^{29}\equiv 1 \pmod{p_i}[/latex] (esse "ao menos" é para o caso de vc trocar 29 por algum numero composto). Particularmente, existe um inteiro [latex]t_i[/latex] tal que [latex]t_i \not\equiv 1 \pmod{p_i}[/latex] satisfazendo a congruencia anterior.
Mas então tome o número 
[latex]a=\sum_{i=1}^kt_im_i^{p_i-1}[/latex]
Então é claro que
[latex]a\equiv t_i \not\equiv 1 \pmod{p_i}[/latex]
e finalmente 
[latex]a^{29}\equiv \left(t_im_i^{p_i-1}\right)^{29}\equiv t_i^{29}\equiv 1 \pmod{p_i}[/latex]

se vc ver algum erro falae mano
SilverBladeII
SilverBladeII
Matador
Matador

Mensagens : 452
Data de inscrição : 04/09/2019
Idade : 20
Localização : Teresina, Piauí, Brasil

Ir para o topo Ir para baixo

Dúvida sobre o Teorema Chinês dos Restos Empty Re: Dúvida sobre o Teorema Chinês dos Restos

Mensagem por SilverBladeII Qua 13 Out 2021, 13:54

Ah, adicionando duas coisas:
O teorema que eu usei pra dizer que x^{29} congruente a 1 mod p tem solução é o seguinte:
* Se p é primo e d|p-1, então existem exatamente [latex]\varphi(d)[/latex] inteiros incongruentes mod p com ordem igual a d.

essse teorema anda de mãos dadas com esse outro:
* Se m tem raiz primitiva, então m tem [latex]\varphi(\varphi(m))[/latex] raizes primitivas.
Esse teorema n foi usado, entretanto.

E eu esqueci de responder tua pergunta, no final.

Existe a se e somente se [latex]p_i\equiv 1 \pmod{29}[/latex], para todo i.
a volta é minha resposta anterior. 
A ida, basta ver que, existindo tal a,
[latex]a^{29}\equiv 1 \pmod{p_i}[/latex]
implica que [latex]\operatorname{ord}_{p_i}(a)|29[/latex], de forma que [latex]29=\operatorname{ord}_{p_i}(a)[/latex] e portanto 
[latex]29|p_i-1[/latex], implicando que [latex]p_i=29k_i+1[/latex].
Perceba que a conclusão da ida só foi possivel porque 29 é primo.
SilverBladeII
SilverBladeII
Matador
Matador

Mensagens : 452
Data de inscrição : 04/09/2019
Idade : 20
Localização : Teresina, Piauí, Brasil

Ir para o topo Ir para baixo

Dúvida sobre o Teorema Chinês dos Restos Empty Re: Dúvida sobre o Teorema Chinês dos Restos

Mensagem por Perceval Qui 14 Out 2021, 21:44

@SilverBladeII escreveu:Ah, adicionando duas coisas:
O teorema que eu usei pra dizer que x^{29} congruente a 1 mod p tem solução é o seguinte:
* Se p é primo e d|p-1, então existem exatamente [latex]\varphi(d)[/latex] inteiros incongruentes mod p com ordem igual a d.

essse teorema anda de mãos dadas com esse outro:
* Se m tem raiz primitiva, então m tem [latex]\varphi(\varphi(m))[/latex] raizes primitivas.
Esse teorema n foi usado, entretanto.

E eu esqueci de responder tua pergunta, no final.

Existe a se e somente se [latex]p_i\equiv 1 \pmod{29}[/latex], para todo i.
a volta é minha resposta anterior. 
A ida, basta ver que, existindo tal a,
[latex]a^{29}\equiv 1 \pmod{p_i}[/latex]
implica que [latex]\operatorname{ord}_{p_i}(a)|29[/latex], de forma que [latex]29=\operatorname{ord}_{p_i}(a)[/latex] e portanto 
[latex]29|p_i-1[/latex], implicando que [latex]p_i=29k_i+1[/latex].
Perceba que a conclusão da ida só foi possivel porque 29 é primo.
Saquei, vlw! Eu estava com essa dúvida porque isso trivializa este problema (apesar de que talvez fatorar essa fração seja mais intuitivo kkk):
Dúvida sobre o Teorema Chinês dos Restos X+LOVTJMvdAWwAAAABJRU5ErkJggg==
e sim, de fato dá pra generalizar esse enunciado como: ''Mostre que existe um a natural tal que (a^b-1)/(a-1) tem pelo menos c fatores primos distintos''. Aí dá pra usar Dirichlet como tu fez ou ficar jogando no valor de a um d^{2t}, com 2t suficientemente grande, e cair numa ''cadeia'' parecida com aqueles problemas sobre descenso infinito de Fermat.
Perceval
Perceval
Recebeu o sabre de luz
Recebeu o sabre de luz

Mensagens : 120
Data de inscrição : 03/01/2021

Ir para o topo Ir para baixo

Dúvida sobre o Teorema Chinês dos Restos Empty Re: Dúvida sobre o Teorema Chinês dos Restos

Mensagem por SilverBladeII Sex 15 Out 2021, 21:19

é, nesse caso é realmente importante que a não seja congruente a 1 mod p_i.
esse d seria o que?
tipo, somar a+d^[2t]?
SilverBladeII
SilverBladeII
Matador
Matador

Mensagens : 452
Data de inscrição : 04/09/2019
Idade : 20
Localização : Teresina, Piauí, Brasil

Ir para o topo Ir para baixo

Dúvida sobre o Teorema Chinês dos Restos Empty Re: Dúvida sobre o Teorema Chinês dos Restos

Mensagem por Perceval Dom 17 Out 2021, 10:21

@SilverBladeII escreveu:é, nesse caso é realmente importante que a não seja congruente a 1 mod p_i.
esse d seria o que?
tipo, somar a+d^[2t]?
Não... Tipo, fazer a=d^{2t}, porque aí você pode fatorar aquilo com a^2-1=(a+1)(a-1) e ficaria
[latex]\frac{((d^{2t})^q-1)}{d^{2t}-1} = \frac{d^{tq}-1}{d^t-1} \cdot \frac{d^{tq}+1}{d^{t}+1}[/latex]
aí você pode concluir que [latex]\frac{((d^{2t})^q-1)}{d^{2t}-1}[/latex] tem mais fatores primos do que [latex]\frac{d^{tq}-1}{d^t-1}[/latex], e ambas são frações equivalentes à do enunciado, e aí você pode repetir esse argumento infinitamente
Perceval
Perceval
Recebeu o sabre de luz
Recebeu o sabre de luz

Mensagens : 120
Data de inscrição : 03/01/2021

Ir para o topo Ir para baixo

Dúvida sobre o Teorema Chinês dos Restos Empty Re: Dúvida sobre o Teorema Chinês dos Restos

Mensagem por Perceval Dom 17 Out 2021, 10:27

@SilverBladeII escreveu:é, nesse caso é realmente importante que a não seja congruente a 1 mod p_i.
esse d seria o que?
tipo, somar a+d^[2t]?
pq a não pode ser congruente a 1 mod p_i? A nossa meta aqui é que p_i divida aquela fração, então se a fosse congruente a 1 mod p isso seria verdade, ou não?
Perceval
Perceval
Recebeu o sabre de luz
Recebeu o sabre de luz

Mensagens : 120
Data de inscrição : 03/01/2021

Ir para o topo Ir para baixo

Dúvida sobre o Teorema Chinês dos Restos Empty Re: Dúvida sobre o Teorema Chinês dos Restos

Mensagem por SilverBladeII Dom 17 Out 2021, 12:59

@Perceval escreveu:
@SilverBladeII escreveu:é, nesse caso é realmente importante que a não seja congruente a 1 mod p_i.
esse d seria o que?
tipo, somar a+d^[2t]?
pq a não pode ser congruente a 1 mod p_i? A nossa meta aqui é que p_i divida aquela fração, então se a fosse congruente a 1 mod p isso seria verdade, ou não?
O problema é que ele divide a-1.
beleza, sabemos que a^{29}-1 é divisível por p, mas se a-1 tamém for divisivel por p então o que garante que
(a^{29}-1)/(a-1) é divisível por p?
por outro lado, se a-1 não for divisivel por p, ent (a-1, p)=1, então
[latex]a^{29}-1\equiv 0 \pmod{p} \implies \frac{a^{29}-1}{a-1}\equiv 0 \pmod{p}[/latex]

lembra que a gente n quer encontrar fatores primos de a^{29}-1, a gente quer encontrar fatores primos de (a^{29}-1)/(a-1)
SilverBladeII
SilverBladeII
Matador
Matador

Mensagens : 452
Data de inscrição : 04/09/2019
Idade : 20
Localização : Teresina, Piauí, Brasil

Ir para o topo Ir para baixo

Dúvida sobre o Teorema Chinês dos Restos Empty Re: Dúvida sobre o Teorema Chinês dos Restos

Mensagem por Conteúdo patrocinado


Conteúdo patrocinado


Ir para o topo Ir para baixo

Página 1 de 2 1, 2  Seguinte

Ir para o topo


 
Permissões neste fórum
Você não pode responder aos tópicos