Question

Consider the three prime numbers \(p=5,7\), and 17 . We want to calculate \(p\)-adic approximations to \(\sqrt{2}\). (i) For which of the three \(p\) does 2 have a square root modulo arbitrary powers of \(p\) ? (ii) For those \(p\) where possible, compute all square roots of 2 modulo \(p^{6}\).

Short answer

2 has square roots for p = 5 and 17. Solutions are found using Hensel's lemma.

Step-by-step solution

Determine which primes allow square roots mod powers of p

The Legendre symbol \( \left( \frac{a}{p} \right) \) tells us if \( a \) is a quadratic residue modulo \( p \). For an odd prime \( p \), if \( \left( \frac{2}{p} \right) = 1 \), then 2 is a quadratic residue modulo \( p \). We calculate \( \left( \frac{2}{p} \right) \) for each prime using quadratic reciprocity.1. For \( p = 5 \), \( \left( \frac{2}{5} \right) = (-1)^{((2-1)/2)((5-1)/2)} = (-1)^{1 \cdot 2} = 1 \). So, 2 is a residue mod 5.2. For \( p = 7 \), \( \left( \frac{2}{7} \right) = (-1)^{((2-1)/2)((7-1)/2)} = (-1)^{1 \cdot 3} = -1 \). Hence, 2 is not a residue mod 7.3. For \( p = 17 \), \( \left( \frac{2}{17} \right) = (-1)^{((2-1)/2)((17-1)/2)} = (-1)^{1 \cdot 8} = 1 \). So, 2 is a residue mod 17.Thus, 2 has square roots modulo arbitrary powers of 5 and 17.

Calculate square roots of 2 modulo 5^6

Since 2 is a quadratic residue modulo 5, we want to find \( x \) such that \( x^2 \equiv 2 \mod 5^6 \).1. Start with modulo 5: Trial, \( 3^2 \equiv 9 \equiv 4 \mod 5 \). Thus, \( x \equiv 3 \mod 5 \) since \( 4 + 1 \equiv 5 \equiv 0 \mod 5 \).2. Use Hensel's lemma to lift the solution: - Assume \( x_k^2 \equiv 2 \mod 5^k \) with \( x_k = 3 \), and find \( x_{k+1} = x_k + 5^k c \) such that \( (x_k + 5^k c)^2 \equiv 2 \mod 5^{k+1} \). - Expand and solve for \( c \) in \( 2x_k5^kc \equiv 2 - x_k^2 \equiv 2 - 9 \equiv -7 \equiv 3 \mod 5 \). - Solving \( 6c \equiv 3 \mod 5 \), \( c \equiv 3 \cdot 6^{-1} \equiv 3 \cdot 4 \equiv 12 \equiv 2 \mod 5 \). Lift solution \( x_2 = 3 + 5 \times 2 = 13 \), and repeat the process.3. Continue lifting with Hensel's to find final solution modulo \( 5^6 \).Using Hensel's lemma repeatedly, we determine all potential squares modulo 5^6.

Calculate square roots of 2 modulo 17^6

Perform similar procedures as Step 2 given that 2 is a quadratic residue modulo 17.1. Start modulo 17: Trial and error, \( 6^2 = 36 \equiv 2 \mod 17 \) which means \( 6 \) is a root modulo 17.2. Use Hensel's lemma for lifting: - Assume \( x_k^2 \equiv 2 \mod 17^k \) with \( x_k = 6 \), compute \( x_{k+1} = x_k + 17^k c \). - Expand and solve similar linear congruence with \( 12c \equiv 2 - 36 \equiv -34 \equiv -17 \equiv 0 \mod 17 \), readily satisfied, so \( c = 0 \).3. Repeat process incrementally to lift the solution modulo \( 17^6 \).This gives the two roots, \( x \equiv 6 \mod 17 \^6 \) and \( x \equiv 11 \mod 17 \^6 \). Report all solutions from the lifting.

Key concepts

Legendre Symbol

The Legendre symbol, denoted as \( \left( \frac{a}{p} \right) \), plays a crucial role in determining whether a number \( a \) is a quadratic residue modulo a prime \( p \). It provides a simple algebraic test: if the symbol evaluates to 1, then \( a \) is a quadratic residue, meaning there exists some integer \( x \) such that \( x^2 \equiv a \mod p \). Conversely, if the symbol is -1, \( a \) is not a residue.

To use the Legendre symbol, several properties and rules can be applied:

• For any non-zero integer \( a \), \( \left( \frac{a}{p} \right) = 0 \) if \( a \equiv 0 \mod p \).
• Quadratic Reciprocity helps in computing \( \left( \frac{a}{p} \right) \) for \( a = 2 \). Specifically, \( \left( \frac{2}{p} \right) = (-1)^{(p^2-1)/8} \) for odd primes \( p \).
• The symbol is multiplicative: \( \left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right) \).

Applying these principles, you can quickly ascertain if \( a \) has any square roots modulo a given prime, as shown in the exercise where \( p = 5 \) and \( p = 17 \) yield positive results for \( a = 2 \).

Hensel's Lemma

Hensel's lemma is a brilliant tool used in number theory to "lift" solutions of congruences to higher powers of a prime \( p \). In the context of finding square roots, it allows us to extend a solution to \( x^2 \equiv a \mod p^k \) and find a corresponding solution \( x' \equiv x \mod p^k \) such that \( x'^2 \equiv a \mod p^{k+1} \).

Here's how the lemma is typically applied:

• Begin with a known solution \( x_k \) satisfying \( x_k^2 \equiv a \mod p^k \). Initially found through trial and error or some other method.
• Assume \( x_{k+1} = x_k + p^k c \) where \( c \) is an integer you need to determine.
• Substitute this into \( (x_k + p^k c)^2 \equiv a \mod p^{k+1} \), expanding and simplifying to solve for \( c \).
• Solve the resulting linear congruence to get \( c \), then calculate \( x_{k+1} \).

This process is repeated for increasing powers of \( p \) until the desired precision is achieved, like reaching \( p^6 \) in the original problem. Hensel’s lemma streamlines the solution finding process and is essential for working with \( p \)-adic numbers.

Quadratic Residue

A quadratic residue modulo \( n \) is a number that can be expressed as the square of some integer under modulo \( n \). In simpler terms, if \( b \equiv x^2 \mod n \), then \( b \) is a quadratic residue modulo \( n \). Understanding quadratic residues is fundamental when examining the solvability of equations like \( x^2 \equiv a \mod p \).

Some key points about quadratic residues:

• For a prime \( p \), exactly half of the non-zero numbers in the set \( \{1, 2, \ldots, p-1\} \) are quadratic residues.
• The concept is closely tied to the Legendre symbol. If \( \left( \frac{a}{p} \right) = 1 \), then \( a \) has a square root and is a quadratic residue modulo \( p \).
• However, if \( \left( \frac{a}{p} \right) = -1 \), no integer \( x \) exists such that \( x^2 \equiv a \mod p \).

In the exercise, we computed which numbers are quadratic residues to determine the feasibility of finding square roots of 2 using quadratic residues and progressed with solutions for different primes using these insights. This allows us to systematically approach finding square roots in modular arithmetic scenarios, especially as seen with primes such as 5 and 17.