6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What book has this problem? $\endgroup$ – Will Jagy Mar 22 '15 at 19:46
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This process is generally known, incidentally, as Hensel lifting and you should have luck searching under that name to see the details. $\endgroup$ – Steven Stadnicki Mar 22 '15 at 5:08
  • 1
    $\begingroup$ 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. $\endgroup$ – Thomas Andrews Mar 22 '15 at 5:21
  • 1
    $\begingroup$ No, it's really not power series. I've seen it described as Newton's formula (which is more accurate.) @მამუკაჯიბლაძე $\endgroup$ – Thomas Andrews Mar 22 '15 at 5:26
  • 1
    $\begingroup$ That they are relatively prime. @user223635 Really just means, here, that $p$ does not divide $a$. $\endgroup$ – Thomas Andrews Mar 22 '15 at 5:28
  • 2
    $\begingroup$ 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 $\endgroup$ – Thomas Andrews Mar 22 '15 at 20:46
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @ThomasAndrews This is what I had in mind. $\endgroup$ – მამუკა ჯიბლაძე Mar 22 '15 at 8:18
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Steven Stadnicki Mar 22 '15 at 15:44
  • $\begingroup$ 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). $\endgroup$ – Steven Stadnicki Mar 22 '15 at 16:44
  • $\begingroup$ That said, this is a great alternative perspective on the problem, and a well-deserved upvote from me. $\endgroup$ – Steven Stadnicki Mar 22 '15 at 16:45
  • 2
    $\begingroup$ 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. $\endgroup$ – Thomas Andrews Mar 22 '15 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.