9
$\begingroup$

Is there a polynomial, $f(x)$, such that for all natural numbers $p$ and $q$, if $\gcd(p, q) = 1$ then $\gcd(f(p), f(q)) = 1$?

Note : Function $f(x)$ must be a polynomial in $x$, not depend on $p$ or $q$, and not be the trivial case of a polynomial with only $1$ term ($f(x) = c$ or $f(x) = x^p$).

$\endgroup$
  • $\begingroup$ At least $f(x) = x^2+x-1$ for $p=2$ and $q=3$, because $\gcd(5,11)=1$ $\endgroup$ – Eemil Wallin Jun 15 '15 at 9:57
  • $\begingroup$ It's not a polynomial, but if $F_n$ is the $n^{\text{th}}$ Fibonacci number, then $\gcd(p, q) = \gcd(F_p, F_q)$ : math.stackexchange.com/a/506108/97045 $\endgroup$ – DanielV Jun 15 '15 at 10:18
  • 2
    $\begingroup$ @RoryDaulton: OP said that $f(p)$ and $f(q)$ should be coprime for all such $p,q$. Though poorly stated, this means that it should do this for all coprime numbers. $\endgroup$ – user230734 Jun 15 '15 at 10:45
  • 2
    $\begingroup$ @BolzWeir: I agree that seems to be what the OP means, but if so the question should have the introductory "If $p,q$ are co-prime integers, then" removed. I would do that edit myself if the OP himself made his meaning clear. I hate to edit other people's questions unless the meaning is made perfectly clear. $\endgroup$ – Rory Daulton Jun 15 '15 at 10:47
  • 1
    $\begingroup$ @EstebanCrespi The question explicitly excludes $f(x) = x^n$ for any $n \geq 0$... $\endgroup$ – A.P. Jun 15 '15 at 14:00
1
$\begingroup$

How about $f(x)=(x-p)(x-q)+1$?

$\endgroup$
  • 2
    $\begingroup$ I believe he means $\forall p, q$ $\endgroup$ – DanielV Jun 15 '15 at 10:18
  • $\begingroup$ In this case, $\mathrm{gcd}(f(p),f(q)) = \mathrm{gcd}((p-p)(p-q)+1,\,(q-p)(q-q)+1) = \mathrm{gcd}(1,1) = 1$, so I believe it is true for all $p,q$. $\endgroup$ – molarmass Jun 15 '15 at 10:28
  • $\begingroup$ @molarmass Going from "$f(p)$ and $f(q)$ are coprime" to "$f(a)$ and $f(b)$ are coprime for every coprime pair $a,b$" is quite a big leap... $\endgroup$ – A.P. Jun 15 '15 at 10:50
  • $\begingroup$ $f(p)$ and $f(q)$ are coprime for all $p,q$, which implies $f(a)$ and $f(b)$ are coprime for every coprime pair $a,b$. $\endgroup$ – molarmass Jun 15 '15 at 10:53
  • 2
    $\begingroup$ @molarmass The definition of $f$ depends on $p$ and $q$. Thus you can't say "for all $p,q$" because those numbers are fixed as soon as you define $f$. $\endgroup$ – A.P. Jun 15 '15 at 11:05
1
$\begingroup$

Yeah, I realize I'm a bit late for this, but here goes:

We show that for any prime $p$, $P(p)$ is a (positive or negative) power of $p$. Assume for the sake of contradiction that some prime $q\neq p$ divides $P(p)$. Then

$$q|P(p)\implies q|P(p+q),$$

so $\gcd(P(p),P(p+q))\neq 1$, a contradiction. Now, as $-x^{d+1}<P(x)<x^{d+1}$ for all sufficiently large $x$ (if $d$ is the degree of $P$), we must have by the Pigeonhole principle that there exist some fixed $s\in\{-1,1\},k\in\mathbb{Z}_{\geq 0}$ so that $P(p)=sp^k$ for infinitely many primes $p$ (as the only possibilities for large enough $p$ are $\pm 1,\pm p,\cdots,\pm p^d$). But then

$$P(x)-sx^k$$

has infinitely many roots, and thus $P(x)$ is identically the polynomial $\pm x^k$.

$\endgroup$

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.