# Is there any polynomial function $f$ such that If $\gcd(p,q)=1$ then $\gcd(f(p),f(q))=1$ for all such $p,q$?

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

• At least $f(x) = x^2+x-1$ for $p=2$ and $q=3$, because $\gcd(5,11)=1$ – Eemil Wallin Jun 15 '15 at 9:57
• 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 – DanielV Jun 15 '15 at 10:18
• @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. – user230734 Jun 15 '15 at 10:45
• @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. – Rory Daulton Jun 15 '15 at 10:47
• @EstebanCrespi The question explicitly excludes $f(x) = x^n$ for any $n \geq 0$... – A.P. Jun 15 '15 at 14:00

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

• I believe he means $\forall p, q$ – DanielV Jun 15 '15 at 10:18
• 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$. – molarmass Jun 15 '15 at 10:28
• @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... – A.P. Jun 15 '15 at 10:50
• $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$. – molarmass Jun 15 '15 at 10:53
• @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$. – A.P. Jun 15 '15 at 11:05

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} 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$$.