Question

Evaluate the Legendre symbol \(\left(\frac{7}{11}\right)\) by using Euler's criterion.

Short answer

Question: Determine the Legendre symbol for \((\frac{7}{11})\) using Euler's criterion. Answer: The Legendre symbol for \((\frac{7}{11})\) is 1, meaning that 7 is a quadratic residue modulo 11.

Step-by-step solution

State Euler's criterion

Euler's criterion states that for any odd prime p and an integer a that is not divisible by p, the Legendre symbol has the following relationship with modular exponentiation: $$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p$$ In this exercise, we want to find the Legendre symbol for \((\frac{7}{11})\), so we have \(a = 7\) and \(p = 11\).

Compute the exponent

Using Euler's criterion, let's compute the exponent for the modular exponentiation relationship: $$\frac{p-1}{2} = \frac{11-1}{2} = \frac{10}{2} = 5$$

Apply the modular exponentiation

Now that we have the exponent, we can compute the modular exponentiation of 7 to the power of 5 mod 11: $$7^5 \pmod{11}$$

Simplify the modular exponentiation

Calculating the modular exponentiation, we get the following result: $$7^5 \pmod{11} = 16807 \pmod{11} = 1$$

Apply Euler's criterion

Using the result from the modular exponentiation, we conclude with the value of the Legendre symbol: $$\left(\frac{7}{11}\right) \equiv 1 \pmod{11}$$

Interpret the result

Since the Legendre symbol has a value of 1, this means that 7 is a quadratic residue modulo 11. In other words, there exists an integer x such that: $$x^2 \equiv 7 \pmod{11}$$

Key concepts

Euler's criterion

Euler's criterion is an important result in number theory that helps determine whether an integer is a quadratic residue modulo a prime number. It provides a way to evaluate the Legendre symbol \(\left(\frac{a}{p}\right)\), where \(p\) is an odd prime and \(a\) is an integer not divisible by \(p\). The criterion states:

• If \(a^{\frac{p-1}{2}} \equiv 1 \pmod{p}\), then \(a\) is a quadratic residue modulo \(p\), and the Legendre symbol \(\left(\frac{a}{p}\right) = 1\).
• If \(a^{\frac{p-1}{2}} \equiv -1 \pmod{p}\), then \(a\) is not a quadratic residue modulo \(p\), and the Legendre symbol \(\left(\frac{a}{p}\right) = -1\).

In simple terms, Euler's criterion connects residue status, Legendre symbols, and modular arithmetic in a quick and calculable way. For instance, if you need to find whether 7 is a quadratic residue modulo 11, you follow these steps of Euler's criterion by computing \(7^\frac{10}{2} \pmod{11}\) and observe if the result is 1 or -1.

Quadratic residues

Quadratic residues are numbers that can be expressed as the square of some integer within a given modulus. That is, a number \(a\) is a quadratic residue modulo \(n\) if there exists an integer \(x\) such that:\[x^2 \equiv a \pmod{n}\]Quadratic residues are an important concept as they help understand which numbers can "inherit" the squaring operation within a particular modular system. In the context of the Legendre symbol, only quadratic residues return a value of 1 when evaluated using Euler's criterion. For example, if \(7\) is a quadratic residue modulo \(11\), there is some integer \(x\) such that \(x^2 \equiv 7 \pmod{11}\). Determining quadratic residues is foundational for solving equations in modular arithmetic, especially in more complex number theory problems.

Modular arithmetic

Modular arithmetic is a method of arithmetic for integers, where numbers "wrap around" upon reaching a certain value called the modulus. It is similar to how hours wrap around on a clock. In modular arithmetic, the expression \(a \equiv b \pmod{n}\) signifies that \(a\) and \(b\) have the same remainder when divided by \(n\). This property is particularly useful for simplifying calculations and for devising equations that respect a cyclical structure.In number theory, modular arithmetic is crucial for solving problems involving periodicity, such as finding quadratic residues. The process of elevating numbers to various powers, like in Euler's criterion, hinges on reducing the size of numbers through modulus operations. For instance, in calculating \(7^5 \pmod{11}\), breaking it down using intermediate steps within modular arithmetic simplifies a potentially unwieldy calculation by maintaining smaller numbers under 11 at each step.

Prime numbers

Prime numbers are the building blocks of the number system, serving as the basic elements in arithmetic. A prime number is a number that has no divisors other than 1 and itself, making it an essential foundation for many areas of mathematics, particularly number theory. For instance, numbers like 2, 3, 5, 7, and 11 are all prime. Their unique properties distinguish them in modular arithmetic, where primes help establish uniform conditions under which residues, such as quadratic residues, can be explored. Euler's criterion, for example, applies specifically to odd prime numbers to evaluate Legendre symbols. Understanding prime numbers is key to grasping deeper number theory concepts, as they directly influence the structure and patterns recognized in equations and modular systems.