Let $m\in\mathbb N$ be any natural number and $f(X)=aX^2+bX+c$ be a polynomial with coefficients $a,b,c\in\mathbb Z$ such that $gcd(a,b,c)=1$.

Is there an $R\in\mathbb Z$ so that $f(R)$ is prime to $m$?

Intuitively, the answer clearly seems yes. But I'm having a hard time proving it. Sure, if $gcd(c,m)=1$, we can simply put $R=0$. My idea would be looking into any prime factor $p^\alpha$ of $m$ and somehow produce simultaneous congruences such that $f(R)\equiv 1 \mod p^\alpha$. But that didn't work out.

  • $\begingroup$ Do you mean $gcd(c,m) = 1$ instead of $gcd(b,m)=1$? $\endgroup$ – packetpacket Jul 23 '18 at 17:01
  • $\begingroup$ Ah yes. Thanks for noting. $\endgroup$ – David Bernstein Jul 23 '18 at 17:06
  • $\begingroup$ What about $X^2+X$ and $m=2$? $\endgroup$ – Lord Shark the Unknown Jul 23 '18 at 17:14
  • $\begingroup$ $\mathbf {Bouniakowsky's Conjecture}$: If an irreducible polynomial $f(x)$ such that $f(n)$ is not constantly multiple of a number, then $f(n)$ represents infinitely many primes. This is a generalization of Dirichlet theorem on primes in an arithmetic progression in whose case we have obviously an irreducible polynomial of degree equal to $1$. Only some particular cases has been proved as far. $\endgroup$ – Piquito Jul 23 '18 at 17:27

As asnwered by Shark, it is not true in general. In fact in only has problems with the even numbers $m$.

What you need first is that for any prime $p$ dividing $m$, there exists some $x_p$ such that $f(x_p) \ne 0 \pmod{p}$. Then you just take $R$ such that $R \equiv x_p \pmod{p}$ for any $p$ dividing $m$.

The existence of such a $x_p$ is guaranteed if $p>2$, since a polynomial of degree $d\le 2$ has at most $d$ roots. But for $p=2 $ and $f(X)\equiv X^2+X \pmod{2}$, it does not exists.

  • $\begingroup$ If the primitive $f$ is not restricted to quadratic polynomials and $R$ and $m$ are given, then I would even say you can always find an $f$ for which $f(R)$ and $m$ are not coprime. $\endgroup$ – quantum Aug 4 '18 at 10:51

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.