Re: [obm-l] Somas de Quadrados e Raizes Primitivas

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 19.10.04 09:18, Nicolau C. Saldanha at nicolau@mat.puc-rio.br wrote:

> On Mon, Oct 18, 2004 at 10:55:52AM -0200, Claudio Buffara wrote:
>> 2. Suponha que p = 2^n + 1 seja um primo maior do que 3. Prove que 3 eh uma
>> raiz primitiva mod p.
> 
> Sabemos que n deve ser par. Observe que 3 não é um quadrado módulo p pois
> Lagrange(3/p) = (-1)^((3-1)(p-1)/4) Lagrange(p/3) = Lagrange(2/3) = -1.
>
Ateh aqui tah tudo OK.
n par ==> n = 2m ==> 2^n + 1 = 4^m + 1 == 2 (mod 3) ==> Lag(p/3) = Lag(2/3).

> O grupo multiplicativo (Z/(p))^* é cíclico com 2^n elementos
> assim neste grupo todo elemento que não é um quadrado é um gerador.
>
O numero de geradores eh Phi(Phi(p)) = Phi(2^n) = 2^(n-1).
Se a eh quadrado, entao a = b^2, para algum b em Z/(p).
Se a eh gerador, entao deve haver um inteiro k tal que a^k = b ==>
a^(2k) = b^2 = a ==> a^(2k-1) = 1 ==> contradicao, pois a tem ordem 2^n.
Logo, nenhum quadrado eh gerador. Como existem 2^(n-1) nao-quadrados, todos
devem ser geradores.

Ou seja, o "assim" na sua ultima frase nao me parece tao obvio. Existe
alguma forma mais direta de se concluir que todos os nao-quadrados (e apenas
eles) sao geradores?
  
[]s,
Claudio.



=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================