# Congruences and Primes

Show that if p is an odd prime, with p = 3 (mod 4), then

$$(\mathbb{Z}_{p}^{*})^4 = (\mathbb{Z}_{p}^{*})^2$$

More generally, show that if n is an odd positive integer, where p = 3 (mod 4) for each prime p | n, then:

$$(\mathbb{Z}_{p}^{*})^4 = (\mathbb{Z}_{p}^{*})^2$$

I was thinking of using Fermats two squares theorem, but I dont really know how to approach the problem.

Any help would be great.

Thanks

-
what does this notation mean? –  user58512 Feb 14 '13 at 18:01

Although one can prove it directly as in mercio's answer, it is insightful to deduce it as follows. Lagrange proved (1769) that in a group of odd order $\rm\,2n+1,\:$ every element is a square, since

$$\begin{eqnarray}\rm\, 1 &=&\rm a^{2n+1}\quad\ \text{by Lagrange's Theorem}\\ \rm \Rightarrow\ a &=&\rm a^{2n+2} = (a^{n+1})^2\end{eqnarray}$$

In a field $\rm\,\Bbb F\,$ of order $\rm\, q = 4n+3,\,$ the subgroup $\rm\,S\,$ of squares has odd order $\rm\,(q\!-\!1)/2 = 2n + 1,\,$ hence every square is a square (of a square),  i.e. a fourth power;  i.e. $\rm\ t \in S\:\Rightarrow\: t = s^2,\,\ s\in S,\$ and, by definition, $\rm\:s \in S\:\Rightarrow\:s = a^2,\ a\in \Bbb F,\:$ hence $\rm\, t = s^2 = (a^2)^2 = a^4.$

Remark  Lagrange's result is a special case of a $\rm\, k$'th power criterion that frequently proves handy. This criterion has a simple conceptual proof (alas, often overlooked). Suppose that we know that $\rm\, g^n = 1,\,$ so exponents on $\rm\,g\,$ can be interpreted $\rm\,mod\ n\!:\, i \equiv m\:$ $\Rightarrow$ $\rm\,g^i = g^{m}.\$ We,  consequently, 
see clearly that $\rm\,g^i\,$ is a $\rm\,k$'th power if $\rm\ mod\ n\!:\, k\mid i,\:$ i.e. $\rm\ i\equiv jk,\,$ so $\rm\,g^i = g^{jk} = (g^j)^k.\,$ By $\rm\color{#C00}{Bezout}$

$$\rm k\,|\, i\:\ (mod\ n)\!\iff\! \exists\,j\!:\ jk\equiv i\:\ (mod\ n)\!\iff\! \exists\, j,m\!:\ jk \!+\! mn = i\color{#C00}{\!\iff\!} (k,n)\,|\, i$$

Hence we have conceptually derived a proof of the following

Theorem $\rm\ \ \ g^n = 1,\,\ (k,n)\mid i\:\Rightarrow\: g^i\,$ is a $\rm\,k$'th power $\ \$ [Easy $\rm\,k$'th Power Criterion]

Proof $\rm\ \ By\ Bezout,\,\ (k,n)\mid i\:\Rightarrow\:k\mid i\,\ (mod\ n) \Rightarrow\:i\equiv jk\,\ (mod\ n)\Rightarrow\: g^i = g^{jk} = (g^j)^k$

Note $\,\$ That $\rm\ \ k\,|\, i\:\ (mod\ n)\!\iff\! (k,n)\,|\, i\ \$ frequently proves conceptually handy,  e.g. see here. $\$ The reason behind this will become clearer when one studies cyclic groups and (principal) ideals.

-
Hint : By Fermat's little theorem, $x^{p-1} \equiv 1 \pmod p$. In particular, $x^2 \equiv x^{p+1} = \left(x^\frac{p+1}4\right)^4$