Question

Find all the quadratic residues of 13 .

Short answer

Answer: The quadratic residues of 13 are {1, 3, 4, 9, 10, 12}.

Step-by-step solution

Define the base set of numbers to find quadratic residues for

Since we are finding the quadratic residues of 13, we only need to consider numbers from 1 to (13-1)/2 = 6. This is because the results will start repeating after that point for bigger numbers. So, our base set of numbers is: {1, 2, 3, 4, 5, 6}.

Calculate the squares of the base set numbers modulo 13

Now, we will square each number from the base set and then take the result modulo 13. 1^2 ≡ 1 (mod 13) 2^2 ≡ 4 (mod 13) 3^2 ≡ 9 (mod 13) 4^2 ≡ 3 (mod 13) 5^2 ≡ 12 (mod 13) 6^2 ≡ 10 (mod 13)

Write down the unique quadratic residues

After calculating the squares of the base set numbers modulo 13, the next step is to list down these values and make sure not to count any duplicates. In this case, the unique quadratic residues are {1, 3, 4, 9, 10, 12}. So, the quadratic residues of 13 are {1, 3, 4, 9, 10, 12}.

Key concepts

Modular Arithmetic

Modular arithmetic is like regular arithmetic but with a twist. Instead of numbers continuing infinitely, they wrap around after reaching a certain value, called the modulus. This is similar to a clock, where time resets after 12 hours. In the case of finding quadratic residues, we often use modular arithmetic to see how numbers behave within a specific system. For example, if we are considering arithmetic modulo 13, once we reach 13 in our calculations, we wrap around back to 0.

Using modular arithmetic, we can simplify calculations and explore patterns more easily. It allows us to find equivalences by representing numbers as remainders rather than as whole or fractions, which is crucial when examining properties like those of quadratic residues. When we say a number is congruent to another number modulo 13, we mean that these two have the same remainder when divided by 13. For instance, 27 is congruent to 1 modulo 13, because both leave a remainder of 1 when divided by 13.

Elementary Number Theory

Elementary number theory is the branch of mathematics that deals with the properties of integers. It focuses on topics such as divisibility, prime numbers, greatest common divisors, and modular arithmetic. This field lays the foundation for understanding more complex topics in number theory.

In this particular exercise, elementary number theory provides us the tools to find quadratic residues, which are simply the unique results of squaring numbers under a specified modulus. Using concepts from elementary number theory, we can identify which numbers squared give a particular remainder, helping us in applications such as cryptography and algorithms design. Additionally, it offers insights into the structure and relationships between numbers and their powers.

• Understanding integers and their properties
• Exploring congruences and modular arithmetic
• Solving problems related with divisibility and residuosity
• Learning about prime and composite numbers

These fundamentals provide the basis for tackling problems like finding quadratic residues.

Quadratic Congruence

Quadratic congruence is a logical progression in our exploration of modular arithmetic and elementary number theory. It involves solving equations of the form \( x^2 \equiv a \pmod{n} \), where we want to find integer solutions for **x**. Finding quadratic residues, the solutions to such equations, is a typical problem involving quadratic congruence.

In the context of modular arithmetic and quadratic residues, we try to find numbers whose squares leave a specific remainder when divided by a given modulus. This exercise, where we square numbers and simplify them modulo 13, is a direct application of solving quadratic congruences.

One key aspect of quadratic congruences is that not all numbers have solutions. For instance, certain integers will never appear as quadratic residues for specific moduli. Thus, solving quadratic congruences also sometimes involves proving no solutions exist or finding specific patterns or sets of solutions.