This problem was posted in 2010 here. Weird!

Let $f(x) = x^ng(x)$ where $gcd(g(x),x) = 1$. Since, $n \leq v_3(f(3)) \leq 2^3-2 = 6$, we have $n = 0,1$. By Dirchlet’s theorem, there exist primes $p,q,r$ such that $g(q) \equiv t (mod q)$ where $t \neq 0$ $$g(q) \equiv 0 (mod p)$$$$r \equiv p-2 (mod p-1)$$$$r \equiv 0 (mod p)$$So, by Fermat’s little theorem, $$f(r) \equiv 2^{r+1}-4 (mod p) \equiv -3 (mod p) \equiv 0 (mod p)$$. It is not difficult to see that $g \equiv \pm1,\pm2,\pm3,\pm6$ from here. So, $\boxed{f \equiv \pm 1, \pm 2, \pm 3, \pm 6, \pm x, \pm 2x}$ are the only solutions. It is easy to verify that they satisfy the given condition. @below: Thanks got it. @3below: Thanks, edited it.

instead of writing \pmx, \pm{2x}, you should write \pm x,\pm 2x

This problem is also in PfTB.

MathInfinite wrote: So, $\boxed{f \equiv \pm 1, \pm 2, \pm 3, \pm 6, \pm x, \pm 2x, \pm 3x, \pm 6x}$ are the only solutions. It is easy to verify that they satisfy the given condition. Naaaah, not really. $\boxed{f(x) \equiv \pm 3x, \pm 6x}$ do not work, since in these cases $f(3)$ does not divide $2^3-2=6$.

MathInfinite wrote: Let $f(x) = x^ng(x)$ where $gcd(g(x),x) = 1$. Since, $n \leq v_3(f(3)) \leq 2^3-2 = 6$, we have $n = 0,1$. By Dirchlet’s theorem, there exist primes $p,q,r$ such that $g(q) \equiv t (mod q)$ where $t \neq 0$ $$g(q) \equiv 0 (mod p)$$$$r \equiv p-2 (mod p-1)$$$$r \equiv 0 (mod p)$$So, by Fermat’s little theorem, $$f(r) \equiv 2^{r+1}-4 (mod p) \equiv -3 (mod p) \equiv 0 (mod p)$$. It is not difficult to see that $g \equiv \pm1,\pm2,\pm3,\pm6$ from here. So, $\boxed{f \equiv \pm 1, \pm 2, \pm 3, \pm 6, \pm x, \pm 2x}$ are the only solutions. It is easy to verify that they satisfy the given condition. @below: Thanks got it. @3below: Thanks, edited it. If $r$ and $p$ are primes, how can $r \equiv 0 \pmod{p}$ unless $r=p$ in which case the equivalence relation above $r \equiv p-2 \pmod{p-1}$ doesn't hold..?

Suppose $f$ works. We have the following main lemma. Lemma: Suppose we have some odd prime $p$. If $q$ is an odd prime such that $q\mid f(p)$, then $q\in\{3,p\}$. Proof: Suppose that $q\ne p$. Now, we have \[f(p)\equiv 0\pmod{q},\]so for all primes $p'\equiv p\pmod{q}$ (of which there are infinitely many by Dirichlet), we have \[f(p')\equiv 0\pmod{q}.\]Thus, $q\mid 2^{p'-1}-1$ for all $p'\equiv p\pmod{q}$. Let $r$ be the order of $2$ mod $q$. Then, $r\mid p'-1$ for all primes $p'\equiv 1\pmod{q}$. Now, by Dirichlet, there are infinitely many primes $p'$ such that $p'\equiv p\pmod{q}$ and $p'\equiv -1\pmod{r}$, so to comply with the above, we must have $1\equiv -1\pmod{r}$, so $r=2$. Thus, $2^2\equiv 1\pmod{q}$, so $q=3$, as desired. $\blacksquare$ Write $f(x)=x^mg(x)$ where $g(0)\ne 0$. Then $g$ also satisfies the problem condition, but $p\nmid g(p)$, so all the prime factors of $g(p)$ are $2$ or $3$. Indeed, $g(p)$ cannot be divisible by $4$, and $g(p)$ is constant modulo $2$, so we have either $g(p)=3^e$ for all primes $p$, or $g(p)=2\cdot 3^e$ for all primes $p$. Both of these are not possible due to size reasons, so we must have $g$ constant. But we have $3^2\nmid 2^3-2$, so $m\in\{0,1\}$. The only constants that divide $2^p-2$ for all primes $p$ are $\pm 1 ,\pm 2,\pm 3,\pm 6$. Thus, the solutions for $f$ are in the set $\{\pm 1 ,\pm 2,\pm 3,\pm 6,\pm x,\pm 2x,\pm 3x,\pm 6x\}$. It is easy to verify that the only ones that work are $\boxed{\{\pm 1 ,\pm 2,\pm 3,\pm 6,\pm x,\pm 2x\}}$.

Suppose a prime $q>3$ divides some $f(x)$ with $x\not\equiv 0\pmod{q}$. Pick a prime $p\equiv -1\pmod{q-1},p\equiv x\pmod{q}$ which we can do by Dirichlet's Theorem on Arithmetic Progressions. Then $q\nmid 2^p-2$, a contradiction. Thus for all primes $q>3$, $q\mid f(x)$ implies $q\mid x$. Let $f(x)=g(x)x^e$ with $g(0)\ne 0$. Then the statement that $q\mid f(x)$ for some $x$ implies $q\mid g(0)$. But by Schur's Theorem, this implies $g(0)$ is a constant $c$. Now, first note $e\le 1$ because $3$ divides $2^3-2$ exactly $1$ time. Note $g(0)\mid 6$. If $e=1$, then $f(x)\in\{-2x,-x,x,2x\}$. If $e=0$, then $f(x)\in\{-6,-3,-2,-1,1,2,3,6\}$, and each works because $2\mid 2^p-2,3\mid 2^p-2$ for odd primes $p$. Thus the set of working polynomials is \[\{-6,-3,-2,-1,1,2,3,6,-2x,-x,x,2x\}.\]

Solution from Twitch Solves ISL: The only answers are $\pm 1$, $\pm 2$, $\pm 3$, $\pm 6$, $\pm x$ and $\pm 2x$. These can be seen to work, so we prove they are the only ones. Claim: For every odd prime $p$, $f(p)$ only could have factors of $2$, $3$, or $p$. Proof. Suppose $q \mid f(p)$ where $q \ge 3$ is a prime other than $p$. Consider primes $\ell$ such that $\ell \equiv p \pmod q$ and $\ell \equiv q-2 \mod q-1$; such primes exist by Dirichlet. Then \[ q \mid f(\ell) \mid 2^\ell - 2 \equiv 2^{q-2} - 2 \equiv \frac{1}{2} - 2\pmod q \]and hence $q = 3$. $\blacksquare$ Claim: If $f(0) \neq 0$, then $f$ is constant and a divisor of $6$. Proof. Let $p \equiv 5 \pmod 6$ be a large prime not dividing $f(0)$. Then $f(p) \not\equiv 0 \pmod p$, so $f(p) \mid 2 \cdot 3^\infty$ by the previous claim. However, $2^p-2 \equiv 3 \pmod 9$ and $2^p-2 \equiv 2 \pmod 4$, so $f(p) \mid 6$. Since this relation holds for all sufficiently large primes $p \equiv 5 \pmod 6$, $f$ must be constant, and the conclusion follows. $\blacksquare$ On the other hand if $f(x)$ is divisible by $x$, redo problem with $f(x)/x$. We can repeat this until $f$ is constant. Hence the possible candidates are $f(x) = cx^e$ where $c \mid 6$. We can deduce $e=1$ by simply letting $p=5$, and the rule out $3x$ and $6x$ by letting $p=3$. So the problem is solved.

v_Enhance wrote: Solution from Twitch Solves ISL: The only answers are $\pm 1$, $\pm 2$, $\pm 3$, $\pm 6$, $\pm x$ and $\pm 2x$. These can be seen to work, so we prove they are the only ones. Claim: For every odd prime $p$, $f(p)$ only could have factors of $2$, $3$, or $p$. Proof. Suppose $q \mid f(p)$ where $q \ge 3$ is a prime other than $p$. Consider primes $\ell$ such that $\ell \equiv p \pmod q$ and $\ell \equiv q-2 \mod q-1$; such primes exist by Dirichlet. Then \[ q \mid f(\ell) \mid 2^\ell - 2 \equiv 2^{q-2} - 2 \equiv \frac{1}{2} - 2\pmod q \]and hence $q = 3$. $\blacksquare$ Claim: If $f(0) \neq 0$, then $f$ is constant and a divisor of $6$. Proof. Let $p \equiv 5 \pmod 6$ be a large prime not dividing $f(0)$. Then $f(p) \not\equiv 0 \pmod p$, so $f(p) \mid 2 \cdot 3^\infty$ by the previous claim. However, $2^p-2 \equiv 3 \pmod 9$ and $2^p-2 \equiv 2 \pmod 4$, so $f(p) \mid 6$. Since this relation holds for all sufficiently large primes $p \equiv 5 \pmod 6$, $f$ must be constant, and the conclusion follows. $\blacksquare$ On the other hand if $f(x)$ is divisible by $x$, redo problem with $f(x)/x$. We can repeat this until $f$ is constant. Hence the possible candidates are $f(x) = cx^e$ where $c \mid 6$. We can deduce $e=1$ by simply letting $p=5$, and the rule out $3x$ and $6x$ by letting $p=3$. So the problem is solved. I don't figure out why Dirichlet's Theorem helps point out the existence of such prime l .Could you explain?

By Chinese Remainder Theorem, there exists a solution to the system of congruences of the form $\ell\equiv N\pmod{q(q-1)}$, where $N$ is some integer; now apply Dirichlet to this congruence to obtain (infinitely many) prime solutions.

Solved with Jeffrey Chen. The answers are \(\pm1\), \(\pm2\), \(\pm3\), \(\pm6\), \(\pm n\), \(\pm2n\), which are clearly the only monomials that work. Now we show these are the only solutions. We may assume \(f(0)\ne0\); if \(f(n)=ng(n)\), then \(g\) satisfies the condition as well. We employ the following two results: Lemma 1: [Schur] If \(f\) is nonconstant, there are infinitely many primes that divide \(f(n)\) for some \(n\). Proof. If \(f(0)=0\), then done. Else if \(f(n)\equiv c+ng(n)\), then for large enough \(k\), note that \[|f(k!\cdot c^2)|>c,\]so it has a prime divisor greater than \(k\). \(\blacksquare\) Lemma 2: Let \(p_1<p_2<\cdots\) be the primes. For sufficiently large \(n\) we have \[p_n<\log_2(p_1p_2\cdots p_{n-1}).\] Proof. Take \(i\) minimal so that \(p_i>p_n^{1.2\ln2}\). Then \begin{align*} \log_2(p_1p_2\cdots p_{n-1}) &>(n-i)\log_2(p_i) >(n-i)\cdot1.2\ln2\cdot\log_2(p_n) =1.2(n-i)\ln(p_n)\\ &\sim1.2\ln(p_n)\left(\frac{p_n}{\ln p_n}-\frac{p_i}{\ln p_i}\right) \approx p_n+\left(0.2p_n-\frac{p_n^{1.2\ln2}}{\ln2}\right)>p_n \end{align*}for large enough \(n\). \(\blacksquare\) Assume \(f\) nonconstant and \(f(0)\ne0\). By Schur, consider a large prime \(q\nmid f(0)\) such that \(q\mid f(r)\) some \(r\), so \(\gcd(q,r)=1\). Claim: There is a prime \(s<\log_2(q)\) such that \(s\nmid q-1\). Proof. Otherwise let \(p_1<p_2<\cdots\) be the primes and suppose \(p_n<\log_2(q)<p_{n+1}\). Then if \(q\) is sufficiently large, Lemma 2 gives \[p_{n+1}<\log_2(p_1\cdots p_n)<\log_2(q),\]contradiction. \(\blacksquare\) Now a prime \(p\) by Dirichlet so that \[p\equiv r\pmod q\quad\text{and}\quad p\equiv s\pmod{q-1}.\]We have \[q\mid f(p)\mid2^{p-1}-1\equiv2^{s-1}-1<q,\]contradiction.

Lemma : if $P(x) \mid Q(x)$ for infinitely $x$ then $\exists R : Q(x) = P(x).R(X) $ Proof : let $Q(x)=P(X).R(x)+H(x)$ then exists infinitely $x$ such $H(x)=0$ so $\forall x : H(x)=x$ Claim: only prime factors of $f$ are $2,3, p$ Proof: let $q \neq 2, p$ be prime and $q \mid f(p)$ then by Dirichlet’s theorem exists $r$ prime such that: \[ r \equiv p \pmod q, r \equiv -1 \pmod {q-1} \]so $q \mid f(r) \mid 2^r - 2 \equiv 2^{-1}-2 \pmod q \Rightarrow -3 \equiv 0 \pmod q \Rightarrow q = 3$ Claim : $v_3(f(p)) = 1$ Proof : Let $9 \mid f(p)$ there are two cases : 1- $p = 3k+1$ then exists prime $q$ such that $q \equiv p \pmod 9, q \equiv 1 \pmod {6}$ and $gcd(6,9)|p-1$ so : $9\mid f(q) \mid 2^1-2 = 1 $ and it is not possible 2- $p = 3k+2$ then exists prime $q$ such that $q \equiv p \pmod 9, q \equiv 4 \pmod {6}$ and $gcd(6,9)|p-4$ so : $9\mid f(q) \mid 2^4-2 = 14 $ and it is not possible let $f(x) = x^\alpha.g(x), gdc(x,g(x))=1$ we know by lemma for $\exists N: \forall p > N : p \nmid g(p)$ and $v_2(g(p)),v_3(g(p))<2$ so $\forall p > N : g(p) = \pm1 , \pm2 , \pm3 , \pm6 $ and by pigeon nest one case happens for Infint $p$ so $g(x) = \pm1 , \pm2 , \pm3 , \pm6$ and $\alpha < 2$ we can show it when $p=5 \rightarrow : 5^\alpha \mid 2^5 - 2 = 30 \Rightarrow \alpha = 1$ $\bullet$ $f(x) = \pm 1$ is answer $\bullet$ $f(x) = \pm p$ is answer $\bullet$ $f(x) = \pm 2$ is answer $\bullet$ $f(x) = \pm 2p$ is answer $\bullet$ $f(x) = \pm 3$ is answer $\bullet$ $f(x) = \pm 3p$ is not answer when $p=3$ $\bullet$ $f(x) = \pm 6$ is answer $\bullet$ $f(x) = \pm 6p$ is not answer when $p=3$

mfw constant solutions exist The answer is $f(x)=\pm 1, \pm 2, \pm 3, \pm 6, \pm x, \pm 2x$ only. First off, the constant solutions given are the only ones, because if $f \equiv c$ then we need $c \mid 6$, and we always have $6 \mid 2^{\text{odd}}-2$. Thus suppose that $f$ is nonconstant, and write $f(x)=x^kg(x)$, where $x \nmid g(x)$, and $k \geq 0$. Suppose that $g$ is nonconstant, so by Schur's lemma there exist infinitely many primes dividing $g(n)$ for some $n$. Therefore, pick some large prime $p$ dividing $g(a)$ for some $p \nmid a$, but not $g(0) \neq 0$. By Dirichlet and CRT we can pick another large prime $q$ such that \begin{align*} q &\equiv a \pmod{p}\\ q &\equiv -1 \pmod{p-1}, \end{align*}whence $p \mid f(q) \mid 2^q-2$. On the other hand, we have $2^q-2 \equiv 2^{-1}-2 \equiv -\tfrac{3}{2} \pmod{p}$, hence $p \mid 3$, which contradicts the fact that $p$ is large. This implies that $g$ is constant, so $f(x)=cx^k$ and $k>0$ (else $f$ is constant). Then we have $c3^k \mid 6$, so $k=1$ and $c \mid 2$, from which we obtain the desired solutions. $\blacksquare$

We'll prove that $f(x) \mid 6x$, which is enough to conclude the problem. Let $p > 3$ be a prime. Consider the following claim: Claim: If $p \mid f(k)$ for some $k$, then $k \equiv 0 (p)$. Proof. Assume not. Then we can assume $0 < k < p$. Let $s = \text{orc}_p(2)$. Then since $p > 3$, so $s > 2$. Since $\gcd(s, p) = 1$, hence by Dirichlet's theorem, there exists infinitely many primes $q$ such that $q \equiv k (p)$ and $q \equiv s-1(s)$. Since $s > 2$, thus $s \nmid q-1$/ On the other hand, we have $0 \equiv f(k) \equiv f(q)$, so $p \mid f(q) \mid 2^q - 2 = 2(2^{q-1} - 1)$, therefore $p \mid 2^{q-1} - 1$, which forces $s \mid q-1$, a contradiction. $\blacksquare$ The above claim yields $f(x) = cx^k$ for some $c$ and $k$. If $k \ge 2$, then $25 \mid f(5) \mid 30$, a contradiction. Thus $k \le 1$ Note that the claim yields prime divisors of $c$ must be $2$ and $3$ and we can take prime $p$ such that $\nu_2(2^p - 2) = 1$ and $\nu_3(2^p - 2) = 1$, which means $c \mid 6$. Hence $f(x)$ divides $6x$, which means $f(x)$ equals $\{\pm 1, \pm 2, \pm 3, \pm 6, \pm x, \pm 2x\}$

The only solutions are $f(x) = n$ for a fixed integer $n$ dividing $6$ and all $x$, and also $f(x) = dx$ for a fixed integer $d$ dividing $2$ and all $x$, which work (due to FLT, $p$ divides $2^p - 2$, and since $p$ is odd, $2,3$ must divide $2^p - 2$ also). Now we prove they are the only solutions. Claim: Any polynomial $P(x)$ with $P(p) \mid 2^p - 2$ for all odd primes $p$ and $P(0) \ne 0$ must be constant. Proof: Suppose otherwise. Then by Schur, $P$ has infinitely many prime divisors. Let $q$ be an odd prime greater than $P(0)$ such that $P(q)$ has a prime divisor other than $2,3$. Let $r$ be this prime divisor. Since $P(q) \equiv P(0) \pmod q$, and $0< P(0) < q$, $q$ cannot divide $P(q)$, so $r \ne q$. Let $s$ be a prime number that is $q\pmod r, -1 \pmod{r-1}$. This is clearly possible by CRT and Dirichlet's. Since $q\equiv s\pmod r$ and $r$ divides $P(q)$, $r$ must also divide $P(s)$. Notice that $2^s - 2\equiv 2^{-1} - 2 = - \frac 32 \pmod s$, so it can't be $0\pmod r$, contradiction. $\square$ Notice that $f(3) \mid 6$, so $x^2$ cannot divide $f(x)$. Case 1: $f(0) \ne 0$. Then $f$ is constant. Since $f(3) \mid 6$, $f(x) = n$ for some integer $n\mid 6$. Case 2: $f(0) = 0$. Then notice that the polynomial $P(x) = \frac{f(x)}{x}$ must be constant as $x^2$ doesn't divide $f(x)$ and $P(p)$ also must divide $2^p - 2$ for each odd prime $p$. Now notice that $P(3) = \frac{f(3)}{3} = 2$, so $P(x) = n$ for some integer $n\mid 2$, so $f(x) = nx$, as desired.