Thread: alpha is a square of an element in Fq star

1. alpha is a square of an element in Fq star

if q be a power of an odd prime. we need to prove that an element alpha belongs to the multiplicative group Fq star, is a square element of Fq star if and only if alpha ^(q-1)/2
=1 . in particular -1 belongs to Fq star square if and only if q is congreunt to 1 (mod4).
(Fq star is the multiplicative group that has size q-1).
Thanks

2. Originally Posted by Mike12
if q be a power of an odd prime. we need to prove that an element alpha belongs to the multiplicative group Fq star, is a square element of Fq star if and only if alpha ^(q-1)/2
=1 . in particular -1 belongs to Fq star square if and only if q is congreunt to 1 (mod4).
(Fq star is the multiplicative group that has size q-1).
Thanks

One direction is pretty easy: $\displaystyle{\alpha=x^2\!\!\pmod q\Longrightarrow \alpha^{\frac{q-1}{2}}=x^{q-1}=1\!\!\pmod q\,\,\forall x\in\mathbb{F}_q^*}$

Now the other one: you'll need the following facts

i) All the quadratic residues modulo q are $\displaystyle{1^2\,,\,2^2\,,\,\ldots,\,\left(\frac {q-1}{2}\right)^2}$ , and thus there are exactly

$\displaystyle{\frac{q-1}{2}}$ non-zero residues modulo q.

ii) The polynomial $\displaystyle{f(x):=x^{\frac{q-1}{2}}-1}$ has at most $\displaystyle{\frac{q-1}{2}}$ different solutions in $\mathbb{F}_q^*$

iii) Since all the quadratic residues modulo q are roots of $f(x)$ above, no

non-quadratic residue modulo q can be a root.

iv)... and Q.E.D.

Tonio

3. Thanks Tonio, can you please tell me what does Q.E.D mean

4. Q.E.D means quite elegantly done, that is to say, the solution ends here.

5. Originally Posted by Shanks
Q.E.D means quite elegantly done, that is to say, the solution ends here.
Actually: Q.E.D. - Wikipedia, the free encyclopedia.