2
$\begingroup$

I am reading wiki article about Legendre symbol and I don't understand the power meaning. Can you please explain the next expression.

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

$\endgroup$
  • $\begingroup$ @ThomasAndrews tnx, first covered. $\endgroup$ – Ilya Gazman Feb 1 '16 at 15:07
  • 1
    $\begingroup$ It's the usual definition of exponentiation; $\frac{p-1}{2}$ will always be an integer because $p$ is odd. $\endgroup$ – DylanSp Feb 1 '16 at 15:07
  • 2
    $\begingroup$ It would really help if you were specific about what you are asking. Do you know what $a\equiv b\pmod p$ means, for example? What is confusing you? Are you really asking us to explain what the expression means, or are you asking us to explain why the expression is true? $\endgroup$ – Thomas Andrews Feb 1 '16 at 15:08
  • $\begingroup$ @ThomasAndrews I am asking what the expression means. This is a definition of new symbols and I am just trying to make sure that I am reading it right and it's the same power that I know and not new definition with the new Legendre symbol. I just trying to understand what is Legendre symbol and how to use it. Sorry if my question may sims to trivial. $\endgroup$ – Ilya Gazman Feb 1 '16 at 15:12
5
$\begingroup$

Since you say you have read about Legendre symbol on Wikipedia, you should already know that $\left(\frac{a}{p}\right)$ is defined as $0$ if $p\mid a$ and as $\pm1$ for $p\nmid a$, depending on whether $a$ is a quadratic residue modulo $p$ or not.

According to Euler's criterion, the congruence $$\left(\frac{a}{p}\right) \equiv a^{(p-1)/2}$$ holds for any odd prime $p$.

There is nothing mysterious about the expression $a^{(p-1)/2}$, it is just a usual exponentiation. (It is useful to notice that $(p-1)/2$ is a positive integer if $p$ is an odd prime.)

Let us have a look on specific examples. For $p=5$ we have $(p-1)/2=2$ and we get $$\begin{array}{|c|c|c|} \hline a & a^2 & \left(\frac{a}{5}\right) \\\hline 0 & 0 & 0 \\\hline 1 & 1 & 1 \\\hline 2 & 4 &-1 \\\hline 3 & 9 &-1 \\\hline 4 &16 & 1 \\\hline \end{array} $$ If you look at the second and third column, they are indeed congruent modulo $5$.

For $p=7$ we get the following table: $$\begin{array}{|c|c|c|} \hline a & a^3 & \left(\frac{a}{7}\right) \\\hline 0 & 0 & 0 \\\hline 1 & 1 & 1 \\\hline 2 & 8 & 1 \\\hline 3 &27 &-1 \\\hline 4 &64 & 1 \\\hline 5 &125&-1 \\\hline 6 &216&-1 \\\hline \end{array} $$ (We know that quadratic residues modulo $7$ are $(\pm1)^2\equiv1\pmod 7$, $(\pm2)^2\equiv4\pmod 7$ and $(\pm3)^2\equiv2\pmod 7$.)

You may notice that instead of calculating $a^3$ we might calculate $a^3\bmod 7$, which would is a bit easier. For example $5^3=5^2\cdot 5 \equiv 25 \cdot 5 \equiv 4\cdot 5 \equiv 20 \equiv -1 \pmod 7$.


This is more about the the basic properties of congruences rather than about the Legendre symbol, but I will try to explain the previous computation, per request in a comment by the OP.

The only thing we are using here is the fact that if $a_1\equiv b_1\pmod n$ and $a_2\equiv b_2\pmod n$, then also $a_1b_1\equiv a_2b_2\pmod n$.

Using this rule we know that $$25\cdot 5\equiv 4\cdot 5\pmod 7$$ since $25\equiv 4\pmod 7$.

In fact, we have even easier way to calculate $5^3 \bmod 7$. If we notice that $5\equiv -2 \pmod 7$ then $$5^3 \equiv (-2)^3 \equiv -8 \equiv -1 \pmod 7.$$

For more about similar computations, have a look at How do I compute $a^b\,\bmod c$ by hand? and other related posts.

$\endgroup$
  • $\begingroup$ I don't understand the last part of your answer. And this actually what I been searching at the first place. I asked about it here $\endgroup$ – Ilya Gazman Feb 1 '16 at 15:43
  • $\begingroup$ By the last part, you mean the one starting: "You may notice that instead..."? (BTW I think that if, for some reason, the answer is not sufficient for you, you probably should not have accepted it. The green tick sends a message to other potential answerers: "The OP is already satisfied with the existing answers." There is no reason to be hasty with accepting one of the answers.) $\endgroup$ – Martin Sleziak Feb 1 '16 at 15:44
  • $\begingroup$ Yeah, how do you make the calculation of the big power easier. $\endgroup$ – Ilya Gazman Feb 1 '16 at 15:45
  • $\begingroup$ @Ilya_Gazman I have tried to add some explanation and also a link to other post(s) which might help you with this. $\endgroup$ – Martin Sleziak Feb 1 '16 at 15:54
  • $\begingroup$ Big big big tnx I am reading it now. $\endgroup$ – Ilya Gazman Feb 1 '16 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.