[Teoria dos números] Divisibilidade

TN - 

Prove que se p é um primo da forma 4^n + 1, então p~|~3^{\frac{p-1}{2}} + 1

Algum avanço?

Há alguma restrição para o valor de n ?

gabrieldpb escreveu:Algum avanço?

Tem um caminho não muito dificil, usando congruência e lei da reciprocidade quadrática.

Se p | a,  a^[(p - 1)/2] _= 0 (mod p)

Se p não divide a e a é reisuo quadrático mod p -> a^[(p - 1)/2] _= 1 (mod p)

Se p não divide a e a não é residuo quadrático mod p -> a^[(p - 1)/2] _= - 1 (mod p)

Existem esses 3 casos. A ideia então seria provar que 3 não é residuo quadrático mod p da forma 4^n + 1. Porém, acredito que há um caminho mais simples, sem a necessidade de usar a lei de reciprocidade quadrática.

Estou tentando provar indo pelo seguinte caminho:

Como p não divide 3, pelo teorema de Fermat 3^(p - 1) _= 1 (mod p) 

p | 3^(p - 1) - 1 = (3^[(p - 1)/2] - 1)(3^[(p - 1)/2 + 1]

O mdc daqueles dois fatores é 2, logo p divide um dos dois. Basta provar então que 3 não divide:

3^[(p - 1)/2] - 1

superaks escreveu:

gabrieldpb escreveu:Algum avanço?

Tem um caminho não muito dificil, usando congruência e lei da reciprocidade quadrática.

Se p | a,  a^[(p - 1)/2] _= 0 (mod p)

Se p não divide a e a é reisuo quadrático mod p -> a^[(p - 1)/2] _= 1 (mod p)

Se p não divide a e a não é residuo quadrático mod p -> a^[(p - 1)/2] _= - 1 (mod p)

Existem esses 3 casos. A ideia então seria provar que 3 não é residuo quadrático mod p da forma 4^n + 1. Porém, acredito que há um caminho mais simples, sem a necessidade de usar a lei de reciprocidade quadrática.

Estou tentando provar indo pelo seguinte caminho:

Como p não divide 3, pelo teorema de Fermat 3^(p - 1) _= 1 (mod p) 

p | 3^(p - 1) - 1 = (3^[(p - 1)/2] - 1)(3^[(p - 1)/2 + 1]

O mdc daqueles dois fatores é 2, logo p divide um dos dois. Basta provar então que 3 não divide:

3^[(p - 1)/2] - 1

Não tinha pensado nesse primeiro caminho. Fiquei atolado usando o pequeno teorema de fermat e não sai dessa última linha. 
Da pra fatorar esse termo em mais dois, pelo fato de  p-1=4^n, logo da pra dividir duas vezes por 2. O ruim é que não consigo enxergar muito além disso.

p=4^n+1,n\geq 1
Como p não pode ser 3, mdc(p,3)=1, logo pelo Pequeno Teorema de Fermat, sabemos que:
3^{p-1}\equiv 1 \mod (p)
3^{p-1}-1\equiv 0 \mod (p)
Como p é da forma 4^n+1, sabemos que p-1 é par, portanto temos uma diferença de quadrados:
(3^{\frac{p-1}{2}}-1)(3^{\frac{p-1}{2}}+1)\equiv 0 \mod (p)
Chegamos ao fato de que p\mid(3^{\frac{p-1}{2}}-1)(3^{\frac{p-1}{2}}+1). Observe que p divide somente um dos fatores, pois caso contrário, teríamos:
3^{\frac{p-1}{2}}-1=pk_1 e 3^{\frac{p-1}{2}}+1=pk_2.
Logo, 2=p(k_2-k_1), o que faria p ser igual a 1 ou 2, o que é igualmente impossível, logo p divide somente uma das expressões.
Então temos duas opções: 3^{\frac{p-1}{2}}-1=pk_1 ou 3^{\frac{p-1}{2}}+1=pk_2.
A partir daí que complica.

Consultando alguns conhecidos e vendo algumas coisas na Wikipedia, a gente chega a um censo:
Sendo p da forma 4^n+1, ele é primo com 3.
Veja que p=4^n+1\equiv (1)^n+1\equiv 2 \mod (3)
Ou seja, p não é resíduo quadrático mod 3. Como p pertence a progressão 4k+1 e não é resíduo quadrático mod (3), pela Lei da Reciprocidade Quadrática, 3 também não será resíduo quadrático mod (p).
Dado esse resultado, pelo Critério de Euler, se 3 não é resíduo quadrático mod(p), então 3^{(\frac{p-1}{2})}\equiv -1 \mod(p)

Logo 3^{(\frac{p-1}{2})}+1\equiv 0 \mod(p)

Ou seja, p \mid 3^{(\frac{p-1}{2})}+1

Para ver a demonstração do Critério de Euler e os outros artigos:
https://es.wikipedia.org/wiki/Criterio_de_Euler
https://pt.wikipedia.org/wiki/Lei_da_reciprocidade_quadr%C3%A1tica
https://pt.wikipedia.org/wiki/S%C3%ADmbolo_de_Legendre

Foi o que eu mensionei antes. Que da pra provar usando a lei de reciprocidade quadrática. Mas meu interesse seria achar um caminho sem a necessidade de usa-lo.

Valeu pela resposta Gabriel

gabrieldpb escreveu:p=4^n+1,n\geq 1
Como p não pode ser 3, mdc(p,3)=1, logo pelo Pequeno Teorema de Fermat, sabemos que:
3^{p-1}\equiv 1 \mod (p)
3^{p-1}-1\equiv 0 \mod (p)
Como p é da forma 4^n+1, sabemos que p-1 é par, portanto temos uma diferença de quadrados:
(3^{\frac{p-1}{2}}-1)(3^{\frac{p-1}{2}}+1)\equiv 0 \mod (p)
Chegamos ao fato de que p\mid(3^{\frac{p-1}{2}}-1)(3^{\frac{p-1}{2}}+1). Observe que p divide somente um dos fatores, pois caso contrário, teríamos:
...

É bem difícil pelo outro caminho..
Suponha que p\mid 3^{\frac{p-1}{2}}-1, então 3^{\frac{p-1}{2}}\equiv 1 \mod (p)
Se conseguíssemos provar que 3 é raiz primitiva de p, a afirmação da linha de cima seria falsa, já que ord_p 3=p-1. Daí, como ord_3 p\mid \frac{p-1}{2}, chegaríamos a um absurdo, já que p-1>(p-1)/2, logo p\mid 3^{\frac{p-1}{2}}+1.