Question

Let \(a\) and \(b\) be integers not divisible by \(p\). Show that either one or all three of the integers \(a, b\) and \(a b\) are quadratic residues of \(p\).

Short answer

Question: Prove that if a and b are integers not divisible by an odd prime number p, then either one or all three of the integers a, b, and ab are quadratic residues of p. Answer: We showed that in the case when both \((a | p)\) and \((b | p)\) are equal to 1, all three integers a, b, and ab are quadratic residues of p. In the case when both \((a | p)\) and \((b | p)\) are equal to -1, only ab is a quadratic residue of p. Therefore, either one or all three of the integers a, b, and ab are quadratic residues of p.

Step-by-step solution

Check the cases of a and b when Legendre symbol is equal to 1

If \((a | p) = 1\) and \((b | p) = 1\), then both a and b are quadratic residues modulo p. In this case, we want to check if ab is also a quadratic residue. We know that if a and b are quadratic residues, then there exist integers x and y such that \(a \equiv x^2 \pmod p\) and \(b \equiv y^2 \pmod p\). Therefore, ab can be written as \(ab \equiv x^2 y^2 \pmod p\). Since \(x^2y^2\) is a perfect square, ab is a quadratic residue as well. So, all three integers a, b, and ab are quadratic residues of p in this case.

Check the cases of a and b when Legendre symbol is equal to -1

If \((a | p) = -1\) and \((b | p) = -1\), then both a and b are not quadratic residues modulo p. In this case, we want to check if ab is a quadratic residue. Recall that the product of Legendre symbols satisfies \((a | p)(b | p) = (ab | p)\). Therefore, \((-1)(-1) = (ab | p)\). So, \((ab | p) = 1\) which means that ab is a quadratic residue modulo p. Thus, in this case, only ab is a quadratic residue of p.

Conclusion

We showed that if both \((a | p)\) and \((b | p)\) are equal to 1 or -1, then either one or all three of a, b, and ab are quadratic residues of p. Since we demonstrated this for both cases, we can conclude that either one or all three of the integers a, b, and ab are quadratic residues of p.

Key concepts

Legendre Symbol

The Legendre symbol is a mathematical notation that encapsulates important information about quadratic residues in number theory. It serves as a quick reference for determining whether an integer is a quadratic residue modulo a prime number. The symbol is defined as \[\left(\frac{a}{p}\right)\textrm{,}\] where \(a\) is an integer, and \(p\) is an odd prime. The value of the Legendre symbol can be either \(1\), \(0\), or \(-1\), representing whether \(a\) is a quadratic residue, divisible by \(p\), or a non-residue, respectively.

In the context of the exercise, the Legendre symbol helps determine if \(a\) and \(b\) are quadratic residues modulo \(p\). When \((a | p) = 1\), it suggests that \(a\) has a corresponding square root modulo \(p\), or rather, there exists some integer \(x\) such that \(x^2 \textrm{mod} p = a\). The same applies to \(b\). The beauty of the Legendre symbol is that it simplifies the often challenging process of checking quadratic residues, especially when dealing with large numbers and complicated calculations.

To further assist students, understanding how to efficiently calculate the Legendre symbol using Euler's criterion and the Law of Quadratic Reciprocity could significantly augment their problem-solving toolkit in number theory.

Number Theory

Number theory is a fascinating branch of mathematics, often designated as the queen of mathematics due to its foundational and pure nature. It primarily deals with the properties and relationships of numbers, particularly integers. Quadratic residues, like the ones mentioned in the exercise, are integral to this field, offering insights into the solutions of quadratic equations under modular conditions.

Understanding concepts such as prime numbers, divisibility rules, congruences, and especially the notion of quadratic residues and non-residues are crucial. The investigation of quadratic residues, for instance, reveals whether an integer can be expressed as the square of another integer modulo some number, often a prime. This concept plays a central role in algorithms essential for computer science fields like cryptography.

Number theory also introduces various tools to solve problems, with the Legendre symbol and modular arithmetic being just two of many. Simplifying complex relationships between numbers is one of the great strengths of number theory, and it's critical for students to comprehend these relationships to fully appreciate the subject's depth.

Modular Arithmetic

Modular arithmetic, often referred to as 'clock' arithmetic, is a system of arithmetic for integers, where numbers 'wrap around' after they reach a certain value—the modulus. This concept is a cornerstone of number theory and plays a vital role in topics like cryptography and computer science algorithms.

The basic arithmetic operations—addition, subtraction, multiplication, and division—have analogs in modular arithmetic. For our exercises, understanding how multiplication functions under modular arithmetic is essential. When we say \(a \equiv b \pmod n\), we mean that \(a\) and \(b\) leave the same remainder when divided by \(n\). In the context of quadratic residues, modular arithmetic helps us understand under what conditions a product of two numbers, such as \(ab\), can be considered a quadratic residue modulo \(p\), a prime number.

For instance, if \(a\) is congruent to \(x^2\) and \(b\) to \(y^2\) modulo \(p\), their product \(ab\) will be congruent to \(x^2y^2\) modulo \(p\), as seen in the solution steps. This demonstrates that the product of two quadratic residues is also a quadratic residue. Introducing students to the concept of modular arithmetic not only enhances their understanding of quadratic residues but also equips them with a method of reasoning that's beneficial across numerous mathematical disciplines.