Proving $\sqrt{2}\in\mathbb{Q_7}$?

Why does Hensel's lemma imply that $\sqrt{2}\in\mathbb{Q_7}$?

I understand Hensel's lemma, namely:

Let $f(x)$ be a polynomial with integer coefficients, and let $m$, $k$ be positive integers such that $m \leq k$. If $r$ is an integer such that $f(r) \equiv 0 \pmod{p^k}$ and $f'(r) \not\equiv 0 \pmod{p}$ then there exists an integer $s$ such that $f(s) \equiv 0 \pmod{p^{k+m}}$ and $r \equiv s \pmod{p^{k}}$.

But I don't see how this has anything to do with $\sqrt{2}\in\mathbb{Q_7}$?

I know a $7$-adic number $\alpha$ is a $7$-adically Cauchy sequence $a_n$ of rational numbers. We write $\mathbb{Q}_7$ for the set of $7$-adic numbers.

A sequence $a_n$ of rational numbers is $p$-adically Cauchy if $|a_{m}-a_n|_p \to 0$ as $n \to \infty$.

How do we show $\sqrt{2}\in\mathbb{Q_7}$?

• Why do we at all need Hensel's lemma? As $(\pm3)^2=9\equiv2\pmod 7, \sqrt2$ is considered $\equiv \pm 3\pmod 7$ – lab bhattacharjee Apr 13 '13 at 11:17
• See [this answer], where I run a couple of iterations of Hensel's lemma while constructing a square root for $-1$ in $\mathbb{Q}_5$. Hensel's lemma is the tool that iteratively generates a Cauchy sequence converging to the desired square root. @lab: this is about $p$-adic numbers, not residue class rings. – Jyrki Lahtonen Apr 13 '13 at 11:31
• @JyrkiLahtonen there is no link to example? – Mathproof P. Apr 13 '13 at 11:34
• This answer – Jyrki Lahtonen Apr 13 '13 at 11:37
• Yup. Very often the result giving the entire Cauchy sequence is called Hensel's lemma. What you call Hensel lemma is just the inductive step. But that inductive step is the key idea (the rest is just applying the definitions), so both results are called Hensel's lemma. – Jyrki Lahtonen Apr 13 '13 at 12:04

Here's an easier way to understand Hensel's lemma: Let $f(X) \in \mathbb{Z}_p[X]$ be a primitive polynomial such that $\overline{f} = \overline{g} \cdot \overline{h}$ in $\mathbb{Z}/p\mathbb{Z}[X] \cong \mathbb{Z}_p / p\mathbb{Z}_p[X]$, and $\overline{g}$ and $\overline{h}$ are coprime.

Then $f$ splits as $f = g \cdot h$ in $\mathbb{Z}_p[X]$, where $\deg g = \deg \overline{g}$ or $\deg h = \deg \overline{h}$, and $g \equiv \overline{g}, \; h \equiv \overline{h}$ mod $p$.

Use this on $f(X) = X^2 - 2$. Since this splits in $\mathbb{Z}/7\mathbb{Z}$ as $(X-3)(X+3)$, it splits into linear factors in $\mathbb{Z}_7[X]$.

• what is $\mathbb{Z}_p[X]$? the set of polynomials with p-adic integer coefficients? And what exactly is a p-adic integer? what is $\overline{f}$? – Mathproof P. Apr 13 '13 at 11:32
• @MathproofP. Should specify: $\overline{f}$ is the reduction of $f$ mod $p$. A $p$-adic integer is an element of $\mathbb{Q}_p$ of norm $\le 1$. They form a subring of $\mathbb{Q}_p$. – Cocopuffs Apr 13 '13 at 11:41
• 1 reduction - does that mean you rearange to have f-pk=0 perhaps? 2 do you mean p-adic norm $\leq1$ 3 subring part is ok, but can you tell me, is $\mathbb{Q_p}$ the set of p-adic numbers? and is a p-adic number a sequence or the limit of the sequence? – Mathproof P. Apr 13 '13 at 12:08
• @MathproofP. 1. $\overline{f}$ means you take the coefficients of $f$ modulo $p$. 2. Yes, the $p$-adic norm on $\mathbb{Q}_p$. 3. $\mathbb{Q}_p$ is the set (field) of $p$-adic numbers. You can understand these as Cauchy sequences modulo null sequences or as limits of sequences, just like you do with $\mathbb{R}$. – Cocopuffs Apr 13 '13 at 12:13
• so is all I need to do, in order to answer my question - find a cauchy sequence that converges to root 2 , 7-adically? – Mathproof P. Apr 13 '13 at 13:07

There are so many different ways to see that $\sqrt2\in\mathbb Z_7\subset\mathbb Q_7$ that one can get dizzy at the vista. My favorite is the correct statement of Hensel given by @Cocopuffs, but you may like this better:

Show rather that $\sqrt{2/9}\in\mathbb Z_7$, by using the expansion of $(1+t)^{1/2}$ from the Binomial Theorem. Since $t=-7/9$ is $7$-adically small, its powers go to zero, and if the coefficients of the series are $7$-adically bounded, you automatically have a Cauchy series (series whose partial sums form a Cauchy sequence). But when you look at the series for $(1+t)^{1/2}$, you see that the only denominators are powers of $2$, in other words $|c_n|\le1$, for every coefficient $c_n$.

• looks like a nice method: (1): (1+x)^n=1 + nx + [n(n-1) x^2]/2! + [n(n-1)(n-2) x^3]/3! +.... so all the x terms will 7-adically converge to 0 because of our choice of x. but what do you mean by 7-adically bounded? – Mathproof P. Apr 13 '13 at 19:45
• When $n=1/2$, there are no $7$’s in the denominators. Ever, anywhere, even though $7!$ does show up formally, because a $7$ appeared earlier in the product. Of course this needs to be proved. But if a rational number $\alpha$ has no sevens in its denominator, then $|\alpha|_7\le1$. – Lubin Apr 14 '13 at 19:17

Asking whether $\sqrt{2}\in\mathbb{Q}_7$ is equivalent to asking whether $x^2 = 2$ has a solution in $\mathbb{Q}_7$.

Hensels lemma tells you that this is the case since it has solutions mod $7$ (all conditions of the theorem are easily checked).

• so this is analogous to asking if $\sqrt{2}\in\mathbb{R}$?but then don't we have to show that there is a cauchy sequence of real numbers with that limit? what have you chosen as the f(x), p, m in Hensel lemma? – Mathproof P. Apr 13 '13 at 11:27
• You can show that there is a real solution by looking at the graph (alternatively by numerical methods such as Newton-Raphson). Actually Hensel's lemma is often referred to as the "Netwon-Raphson of the p-adics". – fretty Apr 13 '13 at 11:37
• There are many ways to think about the field of $p$-adic numbers. One way to think about them is in a kind of "power series" way. A $p$-adic number looks like $a_{-n}p^{-n} + ... + a_0 + ... + a_m p^m + ...$ where all the $a_i$'s are integers mod $p$. – fretty Apr 13 '13 at 11:39
• It is basically like writing down a list of things in $\mathbb{Z}/p^k\mathbb{Z}$ for each $k$, making sure that reductions mod powers of $p$ match up. Hensel's lemma says that finding solutions to most integer polynomials in $\mathbb{Q}_p$ is equivalent to solving the polynomial mod $p$. – fretty Apr 13 '13 at 11:40
• ''Hensels lemma tells you that this is the case since it has solutions mod $7$'' is this because $\sqrt{2}\equiv3mod7$? could you elaborate a bit on how you have used hensel lemma specific. here – Mathproof P. Apr 13 '13 at 12:57

This is how I see it and, perhaps, it will help you: we can easily solve the polynomial equation

$$p(x)=x^2-2=0\pmod 7\;\;(\text{ i.e., in the ring (field)} \;\;\;\Bbb F_7:=\Bbb Z/7\Bbb Z)$$

and we know that there's a solution $\,w:=\sqrt 2=3\in \Bbb F_{7}\,$

Since the roots $\,w\,$ is simple (i.e., $\,p'(w)\neq 0\,$) , Hensel's Lemma gives us lifts for the root, meaning: for any $\,k\ge 2\,$ , there exists an integers $\,w_k\,$ s.t.

$$(i)\;\;\;\;p(w_k)=0\pmod {7^k}\;\;\wedge\;\;w_k=w_{k-1}\pmod{p^{k-1}}$$

Now, if you know the inverse limit definition of the $\,p$-adic integers then we're done as the above shows the existence of $\,\sqrt 2\in\Bbb Q_p\,$ , otherwise you can go by some other definition (say, infinite sequences and etc.) and you get the same result.

• Thanks, I think I see your point since it'd not be obvious we're talking of integers. I shall edit. – DonAntonio Apr 13 '13 at 12:15
• 1 how do we know $\,w:=\sqrt 2=3\in \Bbb F_{7}\,$ - are you allowed to take square root of both sides on a congruence relation i.e. $3^2\equiv2(7)$. 2 so you used Hensel lemma with m=1 but then why did you show $p'(w)\not=0$ did you mean $p'(w)\not\equiv0(p)$? – Mathproof P. Apr 13 '13 at 12:25
• @MathproofP. : $$3^2=9=2\pmod 7$$ – DonAntonio Apr 13 '13 at 13:00
• 1 inverse limit definition of the p-adic integers? 2 what do I do with the lifts for the root? – Mathproof P. Apr 13 '13 at 13:10
• The first one's too involved to develop it here, but it is very,very interesting and fascinating. Google it (and google also profinite groups). You can check some very good books about it, like Gouvea's "p-adic Numbers" A. Robert's "A course in p-adic Analysis", Bachman's "Introduction to p-adic numbers and Valuation Theory", the books by Koblitz, by S. Katok, etc. The geometry here can be stunning: all triangles are isosceles (!) and if not equilateral the basis is always shorter than both equal sides, two closed (open) balls are either disjoint or one's contained in the other (!!), etc. – DonAntonio Apr 13 '13 at 16:01

Hensel's lemma allows you, for simple roots of polynomial equations, to get from an integer solution of the equation modulo $p^k$ do a solution modulo $p^{k+m}$, which is called a "lift" of the solution because reduction modulo $p^k$ will project back to the original solution. I don't know why the condition $m\leq k$ is given in the statement of the lemma in Wikipedia, since by simple iteration one can get this for $m$ as large as one likes. Then repeating this indefinitely, one gets the $p$-adic Cauchy sequence you want to have.

Concretely, if you start with the solution $n=3$ modulo $p^1=7$ to the equation $n^2=2$ defining $\sqrt2$, then you can find a unique solution $n'$ of that equation modulo $7^2=49$ that also "projects back" to $n$ modulo $7$, that is $n'\equiv 3\pmod 7$, by writing $n'=3+7k$ and then solving for $k$ in $(n')^2\equiv2\pmod{49}$. This becomes $3^2+2\times3\times7k+49k^2\equiv2\pmod{49}$ or $42k=-7\pmod{49}$, which after division by $7$ gives $6k\equiv-1\pmod7$, which has the solution $k=1$, unique modulo$~7$, and $n'\equiv3+7\times1=10$ satsifies both $(n')^2\equiv2\pmod{49}$ and $n'\equiv 3\pmod 7$.

Playing the game again posing $n''=n'+49l$ we get $(n'')^2=10^2+2\times10\times49l+10^2\times49^2l^2$, which we can compute modulo $49^2=7^4$ dropping the final term, and given that $10^2-2=98$ is divisible by $49$ (we ensured this above) one can divide the congruence $(n'')^2\equiv 2\pmod{7^4}$ by $49$ to get $20l\equiv-98/49=-2\pmod{7^2}$, and since $20$ is invertible modulo $49$, with inverse $125$, this has the solution $l\equiv =125\times-2=-250\equiv44\pmod{49}$, unique modulo $49$, giving $n''=2166$. This can be continued indefinitely (the explicit computations become harder to perform, but the reason they succeed remains the same), giving solutions modulo ever higher powers of $7$. Then $2,10,108,2166,\ldots$ gives a $7$-adic Cauchy sequence converging $7$-adically to a square root of $2$ (that is congruent to $3$ modulo $7$). Note that I've added the reduction $108$ of $2166$ modulo $7^3$, although its presence does not make the Cauchy sequence any better (nor of course does the presence of any particular term in the sequence) just to mark the fact that we've jumped over the step of solving modulo $7^3$; one could of course just retain in the Cauchy sequence the values that were actually computed.

• 1: ''because reduction modulo $p^k$ will project back to the original solution'' can you give me an example of this? 2: '' Then repeating this indefinitely, one gets the p-adic Cauchy sequence you want to have.'' - I'm not sure what this has to do with p-adic cauchy seq? – Mathproof P. Apr 13 '13 at 12:37
• I've extended the answer with a worked computation; I hope this helps. – Marc van Leeuwen Apr 13 '13 at 14:12
• thanks but this is a bit puzzling for me, I don't understand the notation ''$n=3$ modulo $p^1=7$ a soln. to the equation $n^2=2$?''. – Mathproof P. Apr 13 '13 at 21:44
• @MathproofP. What I mean is that the class of $3$ in $\Bbb Z/7\Bbb Z$ is a solution of the equation in that ring. But we continue to work with the number $n=3$ representing that class, adapting it to $n'=10$ which represents a solution not only in $\Bbb Z/7\Bbb Z$ but also in $\Bbb Z/49\Bbb Z$, and so we successively "improve" the solution so that it works in $\Bbb Z/7^k\Bbb Z$ for ever larger values$~k$. Such a sequence of ever better "approximations" is precisely what makes a $7$-adic Cauchy sequence. – Marc van Leeuwen Apr 13 '13 at 21:59