Dúvida sobre o Teorema Chinês dos Restos

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 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 


?

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

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 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):

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.

é, 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 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

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 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)