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

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Tue, Oct 19, 2004 at 10:36:04AM -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.
> > 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?

Isto segue de mdc ou do teorema chinês dos restos.
Tire "logaritmos" e transforme (Z/(p))^* em Z/(2^n):
o 3, não sendo quadrado, é levado num inteiro ímpar b.
Assim b e 2^n são primos entre si donde existem a e c com
1 = a*b + c*2^n. Isto significa que 3^a é o gerador
com relação ao qual tiramos logaritmos.

Outro ponto de vista é considerar conhecido o seguinte resultado:

 No grupo multiplicativo cíclico G de ordem m, um elemento x é um gerador
 se e somente se ele *não* pode ser escrito da forma x = y^p onde p é
 um fator primo de m. 

A demonstração não é difícil, é análoga ao que eu acabei de fazer.
Aliás acho que o que você fez acima para o caso m = 2^n também
pode ser convertido em uma demonstração geral.

[]s, N.
=========================================================================
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
=========================================================================