Member-only story
The Legendre symbol; explanation and usage
Let us think of the following problem. Suppose we have some a²≡b mod p. Can we find such an a? When is it possible? Certainly, when we have a² ≡ 2 mod 3, we cannot find such an a since 1² ≡ 2² ≡ 1 mod 3. In this article, we will cover exactly that with the power of the Legendre symbol. So let us begin.
Note that knowledge of modular arithmetic will be needed, which can also be found in a separate article here
Let us first introduce our Legendre symbol. Is a completely multiplicative function defined as:
Where p is a prime.
Let us explain what this means exactly. Firstly, a completely multiplicative function is a function on natural numbers such that f(ab) = f(a)f(b). So in this case, we have:
Next, what do we mean by a QR and NR? QR stands for quadratic residue. This just simply means that we are indeed able to find some x such that x²≡a mod p. Similarly, NR stands for non-residue. Which means that we are not able to find some x such that x² ≡ a mod p.
We can in fact verify that this is completely multiplicative, but we leave this to the reader as a trivial exercise to save time.
One thing we must…
