Problem 34 - An Introduction to Mathematical Cryptography

Question

This exercise begins the study of squares and square roots modulo \(p\). (a) Let \(p\) be an odd prime number and let \(b\) be an integer with \(p \nmid b\). Prove that either \(b\) has two square roots modulo \(p\) or else \(b\) has no square roots modulo \(p\). In other words, prove that the congruence $$ X^{2} \equiv b(\bmod p) $$ has either two solutions or no solutions in \(\mathbb{Z} / p \mathbb{Z}\). (What happens for \(p=2\) ? What happens if \(p \mid b ?)\) (b) For each of the following values of \(p\) and \(b\), find all of the square roots of \(b\) modulo \(p\). (i) \((p, b)=(7,2)\) (ii) \((p, b)=(11,5)\) (iii) \((p, b)=(11,7)\) (iv) \((p, b)=(37,3)\) (c) How many square roots does 29 have modulo \(35 ?\) Why doesn't this contradict the assertion in (a)? (d) Let \(p\) be an odd prime and let \(g\) be a primitive root modulo \(p\). Then any number \(a\) is equal to some power of \(g\) modulo \(p\), say \(a \equiv g^{k}(\bmod p)\). Prove that \(a\) has a square root modulo \(p\) if and only if \(k\) is even.

Step-by-Step Solution

Answer

A quadratic congruence modulo an odd prime \( p \) has either two or no solutions. The number of solutions for each given pair \( (p, b) \) can be deduced manually. Squares always exist when k is even.

Step 1: Understanding Quadratic Congruences

When working with the congruence \( X^2 \equiv b (\bmod p) \), where \( p \) is an odd prime, we want to know the conditions under which this congruence has solutions. Using properties of quadratic residues, we know that a number \( b \) is a quadratic residue modulo \( p \) if it has both a solution and its negative (which will also be a solution). Hence, if \( b \) is a quadratic residue, it has two distinct roots; otherwise, it has none.

Step 2: Proving Two or No Solutions for Odd Prime

For an odd prime \( p \) and \( p mid b \), Fermat's Little Theorem and properties of quadratic residues indicate the solutions to \( X^2 \equiv b (\bmod p) \) behave such that: either the congruence has two roots or none. For \( p=2 \), every integer is congruent mod 2 and doesn’t fit the two or no solution situation, while if \( p \mid b \), \( X = 0 \) mod \( p \) is the trivial solution.

Step 3: Example Calculations for Square Roots Modulo p

(i) For \( (p, b)=(7,2) \), check if \( 2 \) is a quadratic residue mod 7, explore potential roots 0 through 6 and determine values of \( X \) such that \( X^2 \equiv 2 (\bmod 7) \). Repeat method for (ii) \( (p, b)=(11,5) \), (iii) \( (11,7) \), (iv) \((37,3)\). Calculating manually for each potential \( X \).

Step 4: Square Roots Modulo Composite Number Calculation

For \( b = 29 \) mod 35, use the Chinese Remainder Theorem since 35 is composite \((5 \times 7)\). Find square roots of 29 modulo 5 and 7 separately, then use these to determine roots modulo 35.

Step 5: Address Part (d) Using Primitive Roots

For \( a \equiv g^k (\bmod p) \), recognize that a primitive root \( g \) satisfies the all nonzero residues are distinct powers of \( g \). A number has a square root iff \( k \equiv 0 \pmod{2} \) making all terms even and \( a \) a square, leveraging properties of congruence and residue classes.

Key Concepts

Quadratic Residues

In modular arithmetic, quadratic residues are fundamental when solving congruences involving squares. If you have an equation like \( X^{2} \equiv b \pmod{p} \), where \( p \) is an odd prime, **quadratic residues help identify whether \( b \) has solutions.**

• A number \( b \) is a quadratic residue mod \( p \) if there exists an integer \( x \) such that \( x^2 \equiv b \pmod{p} \).
• If \( b \) is a quadratic residue, it will have two solutions: \( x \) and \(-x\), both distinct under mod \( p \) arithmetic.
• If \( b \) is not a quadratic residue, no solutions exist.

For example, if \( b = 4 \) and \( p = 7 \), check whether there exists a square number mod 7 giving 4. Compute \( 0^2, 1^2, \dots, 6^2 \) modulo 7 to find that \( b \) is indeed a residue.This exploration frames how we approach the given exercise and understand which numbers can become square residues under different moduli.

Prime Numbers

The role of prime numbers is crucial when discussing modular arithmetic. Prime numbers are integers greater than 1 that have no positive divisors other than 1 and themselves. In the context of modular arithmetic, **prime numbers have unique properties that simplify calculations.**

• They ensure any non-zero number modulo a prime has a unique inverse.
• The structure of the arithmetic modulo a prime is straightforward, as each residue has a well-defined square root relationship.

Consider how prime numbers relate to finding square roots: if \( p \) is an odd prime, every number not divisible by \( p \) could have a special form in terms of square roots or lack thereof.With the Chinese Remainder Theorem, primes like 5 and 7 play roles in forming solutions for other congruences by breaking down composite numbers, offering us a strategic approach distinct from non-prime scenarios.

Fermat's Little Theorem

Fermat's Little Theorem is a cornerstone in number theory due to its applications in solving congruences. For any integer \( a \) not divisible by a prime \( p \), Fermat’s Little Theorem states:\[ a^{p-1} \equiv 1 \pmod{p} \]**This implies important properties about the divisibility of powers and roots.**

• It helps establish conditions for certain types of solutions to exist, or to prove a number is not a quadratic residue.
• Understanding this theorem lets us know when a number raised to a power becomes congruent to 1, pivotal in checking for quadratic residues and calculations.

For instance, if trying to find if \( b \) has square roots mod \( p \), Fermat’s theorem helps rearrange and simplify potential exponents involved.Using this theorem helps in proving results like either two solutions or none for the square congruences.

Primitive Roots

Primitive roots are the backbone of simplifying powers in modular systems. A primitive root of a prime \( p \) is any integer \( g \) such that for every non-zero integer \( a \) under \( p \), there exists an integer \( k \) for which \( a \equiv g^{k} \pmod{p} \). **This concept is vital in understanding the patterns of residues.**

• Primitive roots indicate the cyclic nature of residues under modulo \( p \).
• These roots simplify finding powers and their congruences due to their repetitive, full-period nature.

In the context of quadratic residues, \( a \) having a square root mod \( p \) is contingent on whether \( k \), representing the power in \( a \equiv g^k \), is even.Thus, primitive roots create a backdrop for not just square root conclusions but many properties of modular integers, effectively reducing complex calculations into easier equivalences.