/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Problem 38 Consider the three prime numbers... [FREE SOLUTION] | 91影视

91影视

Log out

Learning Materials

Features

Discover

Chapter 9: Problem 38

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

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

Step by step solution

01

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.
02

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.
03

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.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with 91影视!

Key Concepts

These are the key concepts you need to understand to accurately answer the question.

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鈥檚 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.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Let \(R\) be a ring (commutative, with 1 , as usual). For \(k \in \mathbb{N}\), the \(k\) th Hasse-Teichm茂ller derivative \(f^{[k]}\) of a polynomial \(\sum_{0 \leq i \leq n} f_{i} x^{i} \in R[x]\) is defined as $$ f^{[k]}=\sum_{k \leq i \leq n} f_{i}\left(\begin{array}{c} i \\ k \end{array}\right) x^{i-k} \in R[x] $$ Let \(y\) be another indeterminate. Show that \(f\) has the Taylor expansion \(f(x)=\sum_{0 \leq i \leq n} f^{[i]}(y) \cdot(x-y)^{i}\) around \(y\).

Compute a cube root of 2 modulo 625 , that is, \(g \in\\{0, \ldots, 624\\}\) such that \(g^{3} \equiv 2\) mod 625 . How many such \(g\) are there?

In this exercise, we consider the linearly convergent Newton iteration. Let \(R\) be a ring (commutative, with 1), \(p \in R, \varphi \in R[y]\), and \(s, g \in \mathbb{R}\) such that \(\varphi(g) \equiv 0 \bmod p^{k}\) for some \(k \in \mathbb{N}\) and \(s \varphi^{\prime}(g) \equiv 1 \bmod p\). We define \(h \in R\) by the Newton formula $$ h \equiv g-s \cdot \varphi(g) \bmod p^{k+1} . $$ Prove that \(\varphi(h) \equiv 0 \bmod p^{k+1}, h \equiv g \bmod p^{k}\), and \(s \varphi^{\prime}(h) \equiv 1 \bmod p\). Derive a linearly convergent analog of Algorithm \(9.22\) from this, and show that when \(R=D[x]\) for a ring \(D\) and \(p=x\), it takes \(O\left(n l^{2}\right)\) operations in \(D\). This is slower than the quadratically convergent variant, but has the advantage that the inverse of the derivative need not be updated.

Let \(D\) be a ring (commutative, with 1 ) and \(f, g \in D[x]\) monic of degree \(n>0\). (i) Prove that rev \((f g)^{-1}\) rem \(x^{2 n}\) can be computed from rev \((f)^{-1} \operatorname{rem} x^{n}\), rev \((g)^{-1}\) rem \(x^{n}\), and \(f g\) using \(2 \mathrm{M}(n)+\mathrm{M}(2 n)+O(n)\) arithmetic operations in \(D\). (ii) Prove that rev \((f)^{-1}\) rem \(x^{n}\) can be computed from rev \((f g)^{-1}\) rem \(x^{2 n}\) using \(M(n)+O(n)\) operations in \(D\).

Let \(a \in \mathbb{N}_{>0}\) be of word length \(l\), such that \(a<2^{64 l}\). For \(n \in \mathbb{N}\), we denote by \(T(n)\) the number of word operations to compute \(a^{n}\) using repeated squaring. Prove that \(T(n) \leq T(\lfloor n / 2\rfloor)+O(\mathrm{M}(n l))\) if \(n>1\), and conclude that \(T(n) \in O(\mathrm{M}(n l))\). What is the corresponding result when \(a\) is a univariate polynomial over a (commutative) ring \(R\) ?
See all solutions

Recommended explanations on Computer Science Textbooks

Cloud Services

Read Explanation

Data Structures

Read Explanation

Algorithms in Computer Science

Read Explanation

Computer Programming

Read Explanation

Cybersecurity in Computer Science

Read Explanation

Big Data

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.