Welcome to our community

Be a part of something great, join today!

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

Status
Not open for further replies.
  • Thread starter
  • Moderator
  • #1

Chris L T521

Well-known member
Staff member
Jan 26, 2012
995
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!
 
  • Thread starter
  • Moderator
  • #2

Chris L T521

Well-known member
Staff member
Jan 26, 2012
995
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.