Problem 9 - A Book of Abstract Algebra

Question

Which of the following congruences is solvable? (a) \(\mathrm{x}^{2} \equiv 30(\bmod 101)\) (b) \(x^{2} \equiv 6(\bmod 103)\) (c) \(2 x^{2} \equiv 70(\bmod 106)\) [NoTE: \(x^{2} \equiv a(\bmod p)\) is solvable iff \(a\) is a quadratic residue modulo \(p\) iff $$ \left.\left(\frac{a}{p}\right)=1 .\right] $$

Step-by-Step Solution

Answer

(a) is solvable if \(\left(\frac{30}{101}\right)=1\). (b) is solvable if \(\left(\frac{6}{103}\right)=1\). (c) is solvable if \(\left(\frac{35}{53}\right)=1\).

Step 1: Check Solvability for (a)

The first congruence is \(x^2 \equiv 30 \pmod{101}\). We need to check if 30 is a quadratic residue modulo 101. We use the Legendre symbol, \(\left(\frac{30}{101}\right)\). Compute \(30^{(101-1)/2} \mod 101\). After calculation, if the result is 1, then 30 is a quadratic residue, meaning the congruence is solvable.

Step 2: Check Solvability for (b)

The second congruence is \(x^2 \equiv 6 \pmod{103}\). Check if 6 is a quadratic residue modulo 103. This requires computing the Legendre symbol, \(\left(\frac{6}{103}\right)\), i.e., \(6^{51} \mod 103\). If the result is 1, then 6 is a quadratic residue, and the congruence is solvable.

Step 3: Check Solvability for (c)

The third congruence is \(2x^2 \equiv 70 \pmod{106}\). Since 106 is not prime, we first simplify the equation. Divide both sides by \(2\) to get \(x^2 \equiv 35 \pmod{53}\), because 53 is a divisor of 106. Now check if 35 is a quadratic residue modulo 53 using \(\left(\frac{35}{53}\right)\). Compute \(35^{26} \mod 53\) to determine if the congruence is solvable.

Step 4: Conclusion

After calculation: - For (a), if \(\left(\frac{30}{101}\right) = 1\), it is solvable.- For (b), if \(\left(\frac{6}{103}\right) = 1\), it is solvable.- For (c), if \(\left(\frac{35}{53}\right) = 1\), it is solvable.Evaluate each to find solvable congruences.

Key Concepts

Quadratic Residue

A quadratic residue is a concept in number theory that refers to numbers which have a solution when they fit a particular form, specifically when squared. To determine if a number, let's say "a," is a quadratic residue modulo "p" (where "p" is a prime number), we need to check if there's an integer "x" such that \(x^2 \equiv a \pmod{p}\). In simpler terms, you want to know if there's a number that can be squared to produce another number when divided by "p."

• If such an "x" exists, then "a" is said to be a quadratic residue.
• If no such "x" exists, "a" is called a non-quadratic residue.

The ability to identify quadratic residues is crucial for understanding which congruences have solutions.

Legendre Symbol

The Legendre symbol provides a convenient way to figure out whether a number is a quadratic residue modulo a prime number. It is denoted as \(\left(\frac{a}{p}\right)\), where "a" is any integer and "p" is a prime number.

• If \(\left(\frac{a}{p}\right) = 1\), then "a" is a quadratic residue modulo "p".
• If \(\left(\frac{a}{p}\right) = -1\), then "a" is not a quadratic residue.
• If \(\left(\frac{a}{p}\right) = 0\), then "a" is divisible by "p."

To compute the Legendre symbol, we can use properties of powers. Specifically, for odd primes, the symbol can be determined by evaluating \(a^{(p-1)/2} \mod p\). If this calculation results in 1, then "a" is a quadratic residue.

Modulo Arithmetic

Modulo arithmetic is a mathematical system that deals with congruences, which are equations describing the remainder after division by a number, known as the modulus. It is represented by expressions like \(x \equiv a \pmod{n}\), meaning "x minus a is divisible by n" or simply that "x" gives the same remainder as "a" when divided by "n."

• It simplifies calculations as numbers wrap around once they reach a certain value (the modulus).
• It is commonly used in day-to-day issues like clock arithmetic (e.g., 13 hours after 9 PM is exactly 10 AM).

In solving quadratic congruences, knowing how to manipulate these expressions through addition, subtraction, multiplication, and applying various theorems is crucial.

Prime Modulus

A prime modulus refers to using a prime number as the modulus in modulo arithmetic. Primes have unique properties that simplify several number theory calculations. Here’s why a prime modulus is significant:

• It ensures there is no absorption of numbers other than multiples of the prime itself.
• Primes help establish rules and theorems that make it easier to determine properties of numbers like quadratic residues.

In solving quadratic congruences, a prime modulus aids in evaluating the Legendre symbol and establishing whether a quadratic congruence is solvable. When the modulus is composite, as in the case of non-prime numbers, additional simplifications and factorizations might be required to solve the congruences.