# Legendre symbol, what is it?

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$$

• @ThomasAndrews tnx, first covered. – Ilya Gazman Feb 1 '16 at 15:07
• It's the usual definition of exponentiation; $\frac{p-1}{2}$ will always be an integer because $p$ is odd. – DylanSp Feb 1 '16 at 15:07
• 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? – Thomas Andrews Feb 1 '16 at 15:08
• @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. – Ilya Gazman Feb 1 '16 at 15:12

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.

• 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 – Ilya Gazman Feb 1 '16 at 15:43
• 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.) – Martin Sleziak Feb 1 '16 at 15:44
• Yeah, how do you make the calculation of the big power easier. – Ilya Gazman Feb 1 '16 at 15:45
• @Ilya_Gazman I have tried to add some explanation and also a link to other post(s) which might help you with this. – Martin Sleziak Feb 1 '16 at 15:54
• Big big big tnx I am reading it now. – Ilya Gazman Feb 1 '16 at 16:01