Question

Show that if \(p\) is an odd prime and a is an integer not divisible by \(p\) then \(\left(\frac{a^{2}}{p}\right)=1\).

Short answer

Question: For an odd prime \(p\) and an integer \(a\) not divisible by \(p\), show that the Legendre symbol \(\left(\frac{a^{2}}{p}\right)=1\). Answer: We've shown that there exists an integer \(x\) such that \(x^2 \equiv a^2(\text{mod }p)\), meaning \(a^2\) is a quadratic residue modulo \(p\), which implies that the Legendre symbol \(\left(\frac{a^{2}}{p}\right)=1\).

Step-by-step solution

Analyze the properties of Legendre symbol

Given \(\left(\frac{a}{p}\right)\), if \(p\) divides \(a\), it equals to 0, otherwise it's either 1 or -1 depending on whether the equation \(x^2 \equiv a(\text{mod }p)\) has a solution or not. Now we are given that \(p\) doesn't divide \(a\), so our task is to show the existence of a solution for the equation \(x^2 \equiv a^2(\text{mod }p)\).

Use Fermat's Little Theorem

Fermat's Little Theorem states that \(a^{p-1} \equiv 1 (\text{mod } p)\) for any prime number \(p\) that does not divide \(a\). In our case, since \(p\) is an odd prime, \((p-1)/2\) is an integer. Let's raise both sides of \(x^2 \equiv a^2(\text{mod }p)\) to the power of \((p-1)/2\). Then we get: \((x^2)^\frac{p-1}{2} \equiv (a^2)^\frac{p-1}{2}(\text{mod }p)\). Applying Fermat's Little Theorem to both sides, we get: \(x^{p-1} \equiv a^{p-1}(\text{mod }p)\). Since the left side satisfies Fermat's Little Theorem, we have: \(1 \equiv 1(\text{mod }p)\).

Proving the existence of a solution for the equation

The equation that we want to solve is: \(x^{2} \equiv a^{2} (\text{mod } p)\). We have shown that this equation holds true when raised to the power of \((p-1)/2\). Thus, there must exist an integer \(x\) such that \(x^{2} \equiv a^{2} (\text{mod }p)\). Hence, \(a^2\) is a quadratic residue modulo \(p\).

Conclusion

Considering the properties of Legendre symbol and using Fermat's Little Theorem, we've shown that there exists an integer \(x\) such that \(x^2 \equiv a^2(\text{mod }p)\). Hence, we have proven that for an odd prime \(p\) and an integer \(a\) not divisible by \(p\), the Legendre symbol \(\left(\frac{a^{2}}{p}\right) = 1\).

Key concepts

Elementary Number Theory

Elementary number theory is a branch of mathematics focused on the study of integers and integer-valued functions. It's foundational to understanding concepts like prime numbers, divisibility, and the greatest common divisor (GCD). While it may seem abstract, this field has practical applications in computer science, cryptography, and even in solving puzzles.

In the context of the given exercise, we must consider prime numbers and their unique properties, like the fact that a prime number has exactly two distinct positive divisors: 1 and itself. This fact becomes essential when we delve into the Legendre symbol, a mathematical expression that tells us whether a given integer is a quadratic residue modulo a prime number. Understanding these elementary principles is crucial for demystifying the more complex topics, such as the Legendre symbol and its uses in higher-level number theory.

Fermat's Little Theorem

A cornerstone of number theory, Fermat's Little Theorem provides a fascinating property of integers in relation to prime numbers. The theorem states that if we take any integer a that is not divisible by a prime number p, then raising a to the power of p-1 and dividing by p leaves a remainder of 1. In mathematical terms, it's written as \(a^{p-1} \equiv 1 (\text{mod } p)\).

This theorem is profound because it's widely applicable, from simplifying calculations in modular arithmetic to forming the basis of algorithms in public-key cryptography. Its use in the exercise helps us transform and examine the equation at the heart of the problem, paving the way to show that \(a^2\) is indeed a quadratic residue modulo an odd prime p.

Quadratic Residues

The concept of quadratic residues is crucial when working with Legendre symbols. A quadratic residue modulo n is an integer r such that there exists another integer x with the property \(x^2 \equiv r (\text{mod } n)\). In other words, r is the square of some integer modulo n.

Quadratic residues are fascinating because not all integers will be residues for a given modulus n. This selectiveness of residues builds a bridge to the problem we're solving: showing that \(a^2\) is a quadratic residue involves using the properties and theorems at our disposal, such as Fermat's Little Theorem, to prove the existence of a corresponding x.

Modular Arithmetic

Often referred to as 'clock arithmetic,' modular arithmetic is a system of arithmetic for integers where numbers 'wrap around' after reaching a certain value, called the modulus. This concept is a key player in numerous mathematical areas, including in our exercise. When we say \(x^2 \equiv a^2 (\text{mod } p)\), we mean that when x is squared and divided by the prime p, it has the same remainder as a squared divided by p.

Understanding modular arithmetic also helps to grasp how equations can be manipulated under a modulus, and how the properties of operations under a modulus can be vastly different from standard arithmetic. For example, while Fermat's theorem might seem uncomplicated, applying it within the framework of modular arithmetic provides essential insights into the problem at hand.