Does there exist a polynomial $f \in \Bbb Z[X]$ such that $f$ does not have any integer root but $f$ has at least one root in $\Bbb Z_n$ , $\forall n \in \Bbb Z$ ( while considering $f$ as a polynomial over $\Bbb Z_n$ ) ?

If there exists such a polynomial then we need to Construct it, otherwise a general proof will suffice.

I am trying to work it out with the amount of Ring theory I know but so far haven't been able to do anything!

  • 5
    $\begingroup$ Since at least one of $2,3,6$ must always be a square $\pmod p$ for any prime $p$ the polynomial $(x^2-2)(x^2-3)(x^2-6)$ will always have a root $\pmod p$. A little more effort shows that in fact it has a root $\pmod n$ for all $n\in \mathbb N$. $\endgroup$ – lulu Aug 13 '18 at 14:37
  • $\begingroup$ Possible duplicate of math.stackexchange.com/questions/2863816/… $\endgroup$ – Daniel Schepler Aug 14 '18 at 0:55

$f(x)=(x^2-13)(x^2-17)(x^2-221)$ works. First note that $17*13=221$. Therefore, for prime $n$, one has $$\left ( \dfrac{221}{n} \right )=\left ( \dfrac{13}{n} \right ) * \left ( \dfrac{17}{n} \right ).$$ In particular, not all three numbers 13, 17, and 221 can be quadratic non-residues modulo $n$ at the same time. So $f(x)$ has a root modulo every prime $n$.

For composite $n$, suppose on the contrary, that $f(x)=0$ has no roots modulo $n$ and we derive a contradiction. In other words, suppose 13, 17, and 221 are quadratic non-residues modulo $n$. It follows that a prime power factor of $n$ exists, such as $p^k$ such that 13, 17, and 221 are quadratic non-residues modulo $p^k$. If $p$ is odd, a number is a quadratic residue modulo $p$ if and only if it is a quadratic residue modulo every power of $p$, so we are done in this case. If $p=2$, then 17 is a quadratic residue modulo $2^k$, a contradiction.

  • 1
    $\begingroup$ rather than giving links to some paper, consider typing answers and please explain how the polynomial is constructed instead of giving some ad hoc example! $\endgroup$ – reflexive Aug 13 '18 at 14:38
  • 2
    $\begingroup$ 13*17=221 so not all three numbers 13, 17, 221 can't be quadratic non-residues mod a given number. $\endgroup$ – Marco Aug 13 '18 at 14:40
  • 1
    $\begingroup$ @Marco It would help to add this into your answer, rather than as a comment. The paper is much less relevant to your answer than your comment is. (And there are more things to handle: your argument only immediately applies to prime moduli) $\endgroup$ – Milo Brandt Aug 13 '18 at 15:13
  • $\begingroup$ In the 2nd last sentence you should say "quadratic residue" (twice), not "residue"......+1 $\endgroup$ – DanielWainfleet Aug 13 '18 at 18:31
  • 1
    $\begingroup$ It might also be worth giving special attention to the cases $p=13$, $p=17$ - and fleshing out the argument for $p=2$ (e.g. if $n$ is a root of $n^2 + n - 4$ in $\mathbb{Z}_{2^k}$ then $2n+1$ is a square root of 17 in $\mathbb{Z}_{2^k}$ and Hensel's lemma applies to the polynomial $n^2 + n - 4$ - but not to the polynomial $m^2 - 17$ which is why we use the other one.) $\endgroup$ – Daniel Schepler Aug 14 '18 at 1:02

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.