2
$\begingroup$

Find all polynomials with integer coefficients $f$ such that $f(p) \mid (p-1)! + 1$ for all primes $p$.

Using Wilson’s theorem we find that $f(p)=p;-p$ satisfy the problem. I also thought about using the polynomial from Wilson’s theorem proof but I didn’t seem to work. I encountered difficulties in solving this problem. Any help in writing a complete solution is appreciated it.

$\endgroup$
6
  • 2
    $\begingroup$ Also $f(x) = 1$ or $-1$ works $\endgroup$
    – Exodd
    Commented Jun 9 at 21:09
  • 1
    $\begingroup$ Before writing a solution, you must have an idea for a solution. It is easy to list all constant and linear solutions essentially by observing that $f(2)\mid 2$ and $f(3)\mid 3$ and perhaps checking against a single addiftional data poit such as $f(5)\mid 25$. I suppose that you suspect that there is no higher degree polynomial; but do you have any idea why that shuold be true (and is it true?) $\endgroup$
    – Hagen von Eitzen
    Commented Jun 10 at 13:21
  • $\begingroup$ BTW, if this is contest-math, then what contest is it from?(Not an ongoing contest, I hope). $\endgroup$
    – Hagen von Eitzen
    Commented Jun 10 at 15:37
  • $\begingroup$ @HagenvonEitzen it’s a contest-type problem. Not from a contest. $\endgroup$
    – math.enthusiast9
    Commented Jun 10 at 18:25
  • 1
    $\begingroup$ Sketch: Suppose $p,q$ are distinct primes and $q\mid f(p)$. Conclude that $q\mid f(m)$ whenever $m\equiv p\pmod q$. Use Dirichlet's theorem to conclude that for every $p$, there is some $n=n(p)$ such that $f(p|=\pm p^n$. If $n>\deg(f)$ and $x\gg1$, then $x^n>|f(x)|$. Use pigeon-hole to conclude that for some $m$ with $m\le \deg(f)$ and $u\in\{-1,1\}$, there are inifnitely many primes $p$ such that $f(p)=u p^m$. Conclude that $f(X)=uX^n$. From $f(2)\mid2$, conclude that $m=0$ or $m=1$. $\endgroup$
    – Hagen von Eitzen
    Commented Jun 10 at 20:53

1 Answer 1

Reset to default
1
$\begingroup$

Here is an extended hint. $(p-1)! + 1$ is more or less constructed to have the property that it cannot be divisible by any primes less than $p$. So, you can try to show that aside from the constant and linear polynomials $f(p) = \pm 1, \pm p$, it is not possible for $f(p)$ to have the same property; it must eventually be divisible by some small prime. (You need a separate argument to handle the case $f(p) = \pm p^k$ but this is easy to deal with by plugging in $p = 2$.)

For example, suppose $f(p) = p^2 + 1$. Ignoring the fact that this can be ruled out by plugging in $p = 2$ (in general this style of argument doesn't generalize because we can use polynomial interpolation to arrange for the first few values of $f(p)$ to be equal to $\pm 1, \pm p$ if necessary), you can look at patterns in the prime factorizations of $f(p)$ for various primes $p$. We get that

$$f(3) = 2 \cdot 5$$ $$f(5) = 2 \cdot 13$$ $$f(7) = 2 \cdot 5^2$$ $$f(11) = 2 \cdot 61$$

and so on. In particular $f(p)$ is always even for $p > 2$, but $(p-1)! + 1$ is always odd for $p > 2$, so the former can't divide the latter. You can try to see if this observation generalizes by considering other possible choices for $f$ (for example you could try $f(p) = p^2 + 2$ or $p^3 + 1$) and writing down the prime factors of their values as above.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .