# Problem of the Week #58 - May 6th, 2013

Status
Not open for further replies.

#### Chris L T521

##### Well-known member
Staff member
Thanks again to those who participated in last week's POTW! Here's this week's problem!

-----

Problem: Let $p$ be an odd prime and $a\in\mathbb{Z}$. Define the Legendre symbol
$\left(\frac{a}{p}\right)= \begin{cases}1 & \text{if x^2\equiv a\pmod{p} has an integer solution} \\ 0 & \text{if p\mid a}\\ -1 & \text{if x^2\equiv a\pmod{p} has no integer solution}\end{cases}$

If $p$ is an odd prime and $a,b$ are two integers such that $(p,ab)=1$, then prove that
$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right) \left(\frac{b}{p}\right).$

-----

Hint:
One way to prove the identity is to use Euler's Criterion, which says the following:

Let $p$ be an odd prime and $a$ an integer such that $(a,p)=1$. Then
$a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right)\pmod{p}.$

Remember to read the POTW submission guidelines to find out how to submit your answers!

#### Chris L T521

##### Well-known member
Staff member
This week's question was answered correctly by Sudharaka. You can find his solution below.

$(p,\,ab)=1\Rightarrow (p,\,a)=1\mbox{ and }(p,\,b)=1$

Using the Euler's Criterion we get,

$a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right)\pmod{p}~~~~~~~~~~~(1)$

$b^{\frac{p-1}{2}}\equiv \left(\frac{b}{p}\right)\pmod{p}~~~~~~~~~~~~(2)$

$ab^{\frac{p-1}{2}}\equiv \left(\frac{ab}{p}\right)\pmod{p}~~~~~~~~~~~(3)$

Multiplying (1) and (2);

$ab^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) \pmod{p}~~~~~~~~~~(4)$

By (3) and (4);

$\left(\frac{ab}{p}\right)\equiv \left(\frac{a}{p}\right) \left(\frac{b}{p}\right) \pmod{p}$

Note that since $$(p,\,ab)=1\Rightarrow \left(\frac{ab}{p}\right)=\pm 1$$. If $$\left(\frac{ab}{p}\right)=1\Rightarrow \left(\frac{a}{p}\right) \left(\frac{b}{p}\right)=1$$. If $$\left(\frac{ab}{p}\right)=-1\Rightarrow \left(\frac{a}{p}\right) \left(\frac{b}{p}\right)=-1$$.

$\therefore\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$

Q.E.D.

Status
Not open for further replies.