# Polynomial has roots in any ring $\mathbb{Z}/n\mathbb{Z}$ but not in $\mathbb{Z}$

I have to prove that the polynomial $$(X^2-13)(X^2-17)(X^2-221)$$ has roots in all rings $\mathbb{Z}/n\mathbb{Z}$ for $n\in\mathbb{N}$ but not in $\mathbb{Z}$.

Since $221 = 13\cdot 17$, we can use the multiplicativity of the Legendre-symbol if $n$ is prime and see that $\left(\frac{13\cdot 17 }{n}\right), \left(\frac{13}{n}\right), \left(\frac{17}{n}\right)$ can't all be $-1$.

But for general $n$ I am stuck. If I use the Chinese remainder theorem, I still have to show that the polynomial has roots modulo a power of a prime number.

• What book has this problem? – Will Jagy Mar 22 '15 at 19:46

You need to know that, for $p$ an odd prime, if $x^2\equiv a\pmod p$ has a solution, with $(a,p)=1$, then $x^2\equiv a\pmod {p^k}$ has a solution for any $k$. This is shown via induction relatively easily for $p$ odd.

The case of powers of $2$ is a little harder. You actually need to start with $x^2\equiv a\pmod{8}$ before the induction works.

• This process is generally known, incidentally, as Hensel lifting and you should have luck searching under that name to see the details. – Steven Stadnicki Mar 22 '15 at 5:08
• I kind of deliberately left that name out because it is a good exercise to see how it works yourself. It is a fairly neat process. – Thomas Andrews Mar 22 '15 at 5:21
• No, it's really not power series. I've seen it described as Newton's formula (which is more accurate.) @მამუკაჯიბლაძე – Thomas Andrews Mar 22 '15 at 5:26
• That they are relatively prime. @user223635 Really just means, here, that $p$ does not divide $a$. – Thomas Andrews Mar 22 '15 at 5:28
• Yes, fpr $(x-a)(x-b)(x-ab)$ with $a,b$ relatively prime, you need $a$ a square modulo $b$, $b$ a square modulo $a$ and one of $a,b,ab\equiv 1\pmod 8$. @WillJagy – Thomas Andrews Mar 22 '15 at 20:46

First of all I definitely don't want to compete with the answer by Thomas Andrews, it is definitely the answer, I just want to try and see whether it can be also done using Taylor series.

As he points out, powers of 2 are trickier. For odd $p$, we can proceed as follows.

We are given integers $x$ and $c$ with $a=x^2+cp$ and we are looking for $y$ with $y^2\equiv a\pmod{p^k}$. Thus we need $$\sqrt a=\sqrt{x^2+cp}=x\sqrt{1+\frac{cp}{x^2}}$$ and my claim is that computing this analytically via power series expansion makes sense in $\mathbb Z/p^k$.

First, since $a$ is not divisible by $p$, neither is $x$, so $1/x$ (and then also $1/x^2$) "exists in $\mathbb Z/p^k$". More precisely, there is an integer $x'$ with $xx'\equiv1\pmod{p^k}$ and I will simply denote this $x'$ by $1/x$.

Let us now expand $x(1+\frac c{x^2}p)^{\frac12}$ into Taylor series treating $p$ as a variable: $$x(1+\frac c{x^2}p)^{\frac12}=x\sum_{n=0}^\infty\binom{\frac12}n\left(\frac c{x^2}p\right)^n=x+\frac c{2x}p-\frac{c^2}{8x^3}p^2+\frac{c^3}{16x^5}p^3-\frac{5c^4}{128x^7}p^4+...+(-1)^{n+1}\frac{\binom{2n}nx}{2n-1}\left(\frac c{4x^2}\right)^np^n+...$$ (see e. g. Wikipedia). Now in fact $\frac{\binom{2n}n}{2n-1}$ is an integer (it is twice the $n-1$st Catalan number), and also $1/4$ can be replaced by an integer -- let us just denote by $1/4$ some integer $d$ with $4d\equiv1\pmod{p^k}$. So this series makes sense and converges in $\mathbb Z/p^k$ to a certain value $y$. Actually we just throw out all powers of $p$ starting from $p^k$ and obtain an integer $y$ (rememeber $1/x$ is also a notation for a certain integer). Then by the very construction $y^2\equiv a\pmod{p^k}$.

I admit I am too lazy to work out details for $p=2$ but one thing I can say is that if given a solution of $x^2\equiv a\pmod2$ I can find a solution of $x^2\equiv a\pmod 8$ then the higher powers of 2 can be treated similarly to the above: if $a=x^2+8c$ then $\sqrt a=x\sqrt{1+\frac{4cp}{x^2}}$ where $p=2$, and we can give sense to the expansion of $\sqrt{1+\frac{4cp}{x^2}}$ in $\mathbb Z/2^k$ since the resulting series will only have odd denominators (well, no denominators at all actually, as $1/x$ just denotes some integer).

• @ThomasAndrews This is what I had in mind. – მამუკა ჯიბლაძე Mar 22 '15 at 8:18
• As an example: suppose we take $p=7, a=2$; then $x=3$, $c=-1$. $\frac{1}{2x}=\frac16\equiv41\equiv-8$, and so the relevant terms of the series give $x+\frac{c}{2x}p$=$3+(-1)(-8)7=59\equiv 10\pmod {49}$, and clearly $10^2=100=2\cdot98+2\equiv 2\pmod {49}$. – Steven Stadnicki Mar 22 '15 at 15:44
• One small catch with this approach, incidentally, is that while it computes the solution for any given $p^k$, it doesn't really transfer the solution from $p^k$ to $p^{k+1}$; many of the values to hand (and in particular, $\frac{c}{4x^2}$) must be recomputed for each stage of the process since they'll be different (though also 'lifted') $\mod p^{k+1}$ than they were $\mod p^k$. Also, this approach is really limited to roots, whereas the lifting version works for (almost) arbitrary polynomial equations (and also gives criteria for when and how it fails). – Steven Stadnicki Mar 22 '15 at 16:44
• That said, this is a great alternative perspective on the problem, and a well-deserved upvote from me. – Steven Stadnicki Mar 22 '15 at 16:45
• In order that you can do this, you really ought to be working in the $p$-adic numbers. Otherwise, the taylor series doesn't work. For example, what inverse of $x^2$ are you using? What ring are you computing this series in? In the end, this is about $p$-adics. – Thomas Andrews Mar 22 '15 at 20:57