If you want only a solution, please download file Shortlist2005 on this site. Do you want an another solution?

I'm actually posting this for the sake of completeness, since I have noticed that it is not included in the ressources-page yet; and I also could not find it with the search function which made me assuming that it has not been posted yet (correct me, if I am mistaken).

It was posted before, but I'm unable to find it, too. I remember it was posted by some iranian member, possible with first letter "s" (if that helps anyone ). But lets just discuss here, I think there was no answer given.

http://www.mathlinks.ro/Forum/viewtopic.php?t=87836 but the formulation of the problem is too different to merge, in my opinion. darij

There has to be some mistake in this, but I am probably to tired to figure it out. Can't you just use big $m$ that is greater then $a_{0}$. Then $a_{0}|P(m!)$ as it divides all it's factors, and you can always pick such $m$ that $P(m!)>a_{0}$ (there are at most $n$ $m$'s such that $P(m!)=a_{0}$), so it's composite... Thanx in advance.

What if $a_{0}= \pm 1$ ¿

) Thanks!

Let $ n$ be the degree of $ P$. We begin with the observation that by Wilson's theorem, $ (q - 1)! \equiv - 1 \mod q$ for primes $ q$, so $ (q - k)! \equiv ( - 1)^{k} \cdot \frac {1}{(k - 1)!} \mod q$ for $ 1 \le k < q$. (We use the convention that fractions mod $ q$ are interpreted as division in the field.) It is then useful to consider the polynomial $ Q = x^n P(1/x)$, i.e. the polynomial with the coefficients of $ P$ "reversed." Set $ c_k = ( - 1)^k (k - 1)!$. We have $ P((q - k)!) \equiv P(1/c_k) \equiv Q(c_k) \cdot c_k^{ - n} \mod q$. This in particular means that $ Q(c_k) \equiv 0 \mod q \implies P((q - k)!) \equiv 0 \mod q$ as long as $ q > k-1$. For sufficiently large $ k$, $ Q(c_k)$ must have a prime divisor $ p > k - 1$, since $ \gcd(Q(c_k), c_k)$ divides the constant term of $ Q$. (Recall that $ c_k$ is just $ (k - 1)!$ up to a sign, so that $ Q(c_k)$ can not have only factors less than $ k$ when $ k$ is large.) We now define $ L(t)$ to be the least common multiple of $ 1, 2, \ldots, t$. If we set $ x - 1 = L(t) + 1$ with $ t$ sufficiently large, we know that $ x, x + 1, \ldots, x + t - 1$ are composite, so we have that $ Q(c_x)$ has a prime divisor $ p > x + t - 1$. Then, $ Q(c_x) \equiv 0 \mod p \implies P((p - x)!) \equiv 0 \mod p$, and $ (p - x)! \ge t! + 2p - 2t - 2x$ $ > 3L(t) + 2p - 2t - 2x$ $ > 2p$, where the inequalities may only hold for sufficiently large $ t$. Nonetheless, such a $ p$ exists for arbitrarily large $ x$, so that we may take $ p$ sufficiently large so as to make $ (p - x)!$ large and guarantee $ |P((p - x)!)| > p$. Combining with $ P((p - x)!) \equiv 0 \mod p$, this means that $ P((p - x)!)$ is composite, as desired.

Quote: For sufficiently large $ k$, $ Q(c_k)$ must have a prime divisor $ p>k-1$ , since $ \text{gcd}(Q(c_k),c_k)$ divides the constant term of $ Q$ . (Recall that $ c_k$ is just $ (k-1)!$ up to a sign, so that $ Q(c_k)$ can not have only factors less than $ k$ when $ k$ is large.) can someone explain more about this step? i can't understand why $ \text{gcd}(Q(c_k),c_k)$ divides the constant term of $ Q$ and $ Q(c_k)$ can not have only factors less than $ k$ when $ k$ is large. Thanks.

bolpoin wrote: Quote: For sufficiently large $ k$, $ Q(c_k)$ must have a prime divisor $ p>k-1$ , since $ \text{gcd}(Q(c_k),c_k)$ divides the constant term of $ Q$ . (Recall that $ c_k$ is just $ (k-1)!$ up to a sign, so that $ Q(c_k)$ can not have only factors less than $ k$ when $ k$ is large.) can someone explain more about this step? i can't understand why $ \text{gcd}(Q(c_k),c_k)$ divides the constant term of $ Q$ and $ Q(c_k)$ can not have only factors less than $ k$ when $ k$ is large. Thanks. Me,too. But, I think that the proposition "For sufficiently large $k$, $Q(c_k)$ must have a prime divisor $ p>k-1$" is true. So I think that probability1.01's answer is correct. I will post this proposition's proof. Proof:Since $k$ is sufficiently large, specially $k>2a_{n}$, We have $c_k = (-1)^{k} \cdot (k-1)! \equiv 0 \pmod{a_{n}^{2}}$. Therefore $Q(c_k) \equiv a_{n} \pmod{a_{n}^{2}}$, or there exists a positive integer $s$ such that $Q(c_k) = s\cdot a_{n}^{2}+a_{n} = a_{n}(s\cdot a_{n}+1) $. Since $|Q(c_k)|$ is sufficiently larger than $a_{n}$, $|s\cdot a_{n}+1|$ is larger than 1. Therefore, $s\cdot a_{n}+1$ must have a prime divisor. Let $p$ be a prime divisor of $s\cdot a_{n}+1$, $p$ must be strictly more than $k-1$. Otherwise, $p \le k-1$ or $c_k = (-1)^{k} \cdot (k-1)! \equiv 0 \pmod{p}$. Therefore $Q(c_k) \equiv a_{n} \equiv 0 \pmod{p}$, or $0 \equiv s\cdot a_{n}+1 \equiv 1 \pmod{p}$. This is a contradiction.

Yimin Ge wrote: Let $P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots+a_{0}$, where $a_{0},\ldots,a_{n}$ are integers, $a_{n}>0$, $n\geq 2$. Prove that there exists a positive integer $m$ such that $P(m!)$ is a composite number. The main idea is to note $(p-k)!(k-1)! \equiv (-1)^k \pmod{p}$. Indeed, $(p-1)! \equiv -1 \pmod{p}$ by Wilson's Theorem and $$(p-(k-1)) \cdot \dots \cdot (p-1) \equiv (-1)^{k+1}(k-1)! \pmod{p}.$$Now define $Q(x)=x^nP(1/x)$. Define $x_k=(-1)^k(k-1)!$ and for $k$ large enough, we'll pick a prime $p_k \mid Q(x_k)$. Clearly, we see $p_k \mid P((p_k-k)!)$. Now we claim that for some large $k$, we have $(p_k-k)!-p_k>M$ for any fixed $M>0$. Let $m$ be a large number with $m \equiv 1 \pmod{6}$. Observe that $m!+j$ has no prime factor exceeding $m!+1$ for any $2 \le j \le m+3$. Hence any prime $p \mid m!+j$ will satisfy $p \mid (m!+1)!$. For $k=m!+2$ if $p_k \mid m!+j$ for any $2 \le j \le m+3$ then $p_k \mid x_k$ hence $p_k \mid Q(0)$ (also leading coefficient of $P(x)$), false for $k$ large since $p>(k-1)$. Hence $p_k>k+(m+1)$. Hence $(p_k-k)!-p_k>M$ for any fixed $M>0$ by taking $k$ large. Finally, $P((p_k-k)!)=p_k$ but $P((p_k-k)!)>(p_k-k)!+P(0)$ so we get the desired contradiction! $\blacksquare$ Note. The mod $6$ restriction is only to ensure $m+1, m+2, m+3$ do not have a prime among them. EDIT. So I forgot to add $p_k>(k-1)$, indeed $\gcd(Q(x_k), x_k)=Q(0)$ for $k$ large. EDIT. So to make clear why $(p_k-k)!-p_k>M$, note that $$(p_k-k)!-p_k=(p_k-k)((p_k-k-1)!-1)-k>(m+1)(m!-1)-(m!+2)$$and we are good to go.

Suppose $\deg P = d$. For now, we will assume $P$ has positive leading coefficient (if its negative just do $P\to -P$). Let $Q(x)=x^dQ(1/x)$. Note that essentially by Wilson's theorem, we have $(p-k-1)!\equiv 1/k!\pmod{p}$ for odd $k$ (for even $k$ we have the opposite sign relation, but we won't be using that) and any prime $p$. Thus, for $k$ even, we have \[Q(k!)\equiv P((p-k-1)!)\pmod{p}\]for any prime $p$. Let $f(M):=\mathrm{lcm}(1,2,\ldots,M+1)+1$. Pick $M$ sufficiently large, and choose it so that $M+1$ is not prime. Then we have (for large enough $M$) that $Q(0)^2\mid f(M)!$, so $Q(f(M)!)/Q(0)$ has all its prime factors larger than $f(M)$. But since $f(M)+1,\ldots,f(M)+M$ are all composite, we must have that any prime factor $p$ of $Q(f(M)!)/Q(0)$ is at least $f(M)+M+1$. Suppose $p=f(M)+M+r$ for $r\ge 1$. By construction, $Q(f(M)!)\equiv 0\pmod{p}$, and since $f(M)$ is even, we have $p\mid P((p-f(M)-1)!)$. It now suffices to show $P((p-f(M)-1)!)>p$. We see that for large enough $x$, we have $P(x)>x+P(0)$. Note that $(p-f(M)-1)!=(M+r-1)!$. We claim $(M+r-1)!>f(M)+M+r$. We have that $f(M)=\mathrm{lcm}(1,2,\ldots,M)+1$ since $M+1$ not prime, so $f(M)<M!/2$ for large enough $M$. Thus, \[p=f(M)+M+r<M!/2+M+r<(M+r-1)!,\]so $(p-f(M)-1)!>1.1p$ for large enough $M$. Also eventually $P$ is increasing, so we have then that $P((p-f(M)-1)!)>P(p)>1.1p+P(0)>p$ for large enough $M$. But we also $p\mid P((p-f(M)-1)!)$, so $P((p-f(M)-1)!)$ is not prime, as desired.

I will show that in fact there are infinitely many integers. Suppose there exists an $N$ such that $f(n!)$ is not composite for $n \geq N$. Key Step: Note that $$f((p-k)!) \equiv 0 \pmod p \iff f((k-1)!) \equiv 0 \pmod p.$$Set $$x_k = a_0(k-1)^d + a_1(k-1)^{d-1} (-1)^k + \cdots + a_d(-1)^{kd}.$$Pick a large $k$ such that $a_d^2 \mid (k-1)!$, and set $p_k \mid x_k / a_d$. Note that $p_k^2 \nmid x_k / a_d$, and also $p_k \geq k$. Now fix $k = a(N+1)! + 2$ for some $a \geq 1$. Relaying $p_k$ from earlier, note that as $p_k \mid f((p_k - k)!)$ and $p_k - k \geq N$, we have $f((p_k-k)!) = p_k$. At this point we're basically done: there exists a sequence $\{x_a\} = \{p_k - k\}$ with $f(x_a!) = x_a + a(N+1)! + 2$. This creates size issues as $f((x_a+1)!) - f(x_a!) \leq (N+1)! + 1$, but $f$ is increasing for sufficiently large $N$.

By Wilson's theorem and induction on $k$, we find that $(p-1-i)! \equiv \frac{(-1)^{i+1}}{i!} \pmod{p}$ for $1 \leq i \leq p$. Pick $q$ to be a massive prime and the difference between $q$ and the gap between $q$ and the prime greater than it is large as well. Now consider the "reverse polynomial" $Q(x)=x^nP(1/x)$. If $q$ is taken to be very large, we can force $\nu_p(a_n)<\nu_p(q!)$ for all primes $p$, since the LHS is fixed while the RHS is unbounded. Then consider the quantity $Q(q!)/a_n$, which must be an integer and is coprime to $q!$. If $q$ is made large, this quantity must be large as well, hence it should be divisible by some prime $p>q$ (so $p$ obviously divides $Q(q!)$ too). Then $$P\left(\frac{(-1)^{q+1}}{q!}\right)\equiv P\left(\frac{1}{q!}\right)\equiv \frac{Q(q!)}{(q!)^n} \equiv 0 \pmod{p} \implies P((p-q-1)!) \equiv 0 \pmod{p},$$but since we selected $q$ such that any primes after it are much larger, $p-q-1$ can be made to be unbounded, hence at some point $P((p-q-1)!)$ must obviously exceed $p$, hence we find that $P((p-q-1)!)$ is composite. $\blacksquare$ EDIT: Actually we need $p-q-1$ to grow quickly enough, not just for it to be unbounded. Since the $n$-th prime is asymptotic to $n \log n$, we can pick $q$ such that no primes lie in $[q,q+2\log q]$, hence $p-q-1 \geq \log p$. Then $(\log p)!=\Omega((\log p)^{\log p})$ by Stirling's which dominates by $p$ by taking logs.

Let $P(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_1x+a_0$ and $Q(x)=x^nP\left(\frac1x\right)=a_0x^n+a_1x^{n-1}+\dots+a_{n-1}x+a_n$. Let $r(x)=\prod_{p\mid x}{p}$ and let $N$ be a positive integer such that $a_n\cdot r(N!)\mid N!$. Since $\nu_p\left(\tfrac{N!}{r(n!)}\right)$ is non-decreasing, for all $k\ge N$, $a_n\cdot r(k!)\mid k!$. We have \[\frac{Q(k!)}{a_n}=a_0\left(\frac{k!^n}{a_n}\right)+a_1\left(\frac{(k)!^{n-1}}{a_n}\right)+\dots + a_{n-1}\left(\frac{k!}{a_n}\right)+1\]Note that everything except the $1$ must be divisible by $r(k!)$, so $k!$ is coprime with $Q(k!)$. Now, let $p_k\mid Q(k!)$ for some $p_k>k$. Then, $p_k\mid P\left(\tfrac{1}{k!}\right)$. By Wilson's, we have \[\frac{(-1)^{k-1}}{k!}\equiv (p_k-k-1)!\pmod p_k\]so for odd $k$, $p_k\mid P((p_k-k-1)!)$, so $P((p_k-k-1)!)=p_k$. Now, by Chinese Remainder Theorem, there exists unboundedly large sequences of consecutive composite numbers, so $p_k-k-1$ can be made to be infinitely large, and thus $P((p_k-k-1)!)$ will far exceed $O(x)$, so it cannot be equal to $p_k$.

Let $P(x)=a_kx^k+\dots + a_0$. Let $P_1$ denote the reverse of $P$, so $P(1/x)=\frac{P_1(x)}{x^k}$. Note that by Wilson, $P((p-(2n+1))!)\equiv P\left(\frac{1}{(2n+1)!}\right) = \frac{P_1((2n+1)!)}{(2n+1)!^k} \pmod p$. We thus look at prime divisors of $P_1((2n+1)!)$. Claim: The set of primes that divide $P_1((2n+1)!)$ for some $n$ is infinite. Also, sufficiently large $n$ have primes greater than $2n+1$ dividing $P_1((2n+1)!)$. Proof. Suppose it had a finite number of prime divisors, say $p_1, p_2, \dots, p_j$. Take $n=(2(1434\max(p_i)+1434a_k+C)+1)!$ for sufficiently large $C$. The only prime divisors that $P_1(n)$ can have are those in $p_i$ that also divide $a_k$. However, as $a_k^2$ divides $n$ we have $P_1(n)/a_k=1+a_{k-1}\cdot \frac{n}{a_k} + \dots \equiv 1 \pmod p_i$ so $v_{p_i}(P_1(n))=v_{p_i}(a_k)$ which is a size contradiction. If all divisors of $P_1((2n+1)!)$ are less than $2n+1$ they must also divide $a_k$ which isn’t possible for sufficiently large $n$ as shown. $\blacksquare$ Now, if $p$ divides $P_1((2n+1)!)$ and $P_1((2m+1)!)$ we have $p$ dividing both $P((p-(2n+1))!)$ and $P((p-(2m+1))!)$ which is only possible finitely many times as past a certain point $P$ is increasing (ie, this can only be true for finitely many primes, but these don’t divide large values of $P_1$ of factorials which is this). Thus for sufficiently large $n$, $P_1(2n+1)$ has a prime divisor $q$ above $n$ that doesn’t divide $P_1((2m+1)!)$ for any $m$. By prime number theorem, we thus get that $q/(2n+1)$ is unbounded, so $P((q-(2n+1))!)\geq P(q/2)>q$, a contradiction as $q \mid P((q-(2n+1))!)$.

Polynomial questions are most of the times a cook, and this is no exception. From Wilson's Theorem recall that for an odd prime $q$ we have $(q-i)! \equiv \frac{(-1)^{i}}{(i-1)!} \pmod q$. And also consider the polynomial of flipped coefficients i.e. $Q(x)=x^n P \left(\frac{1}{x} \right)$, let $(-1)^{i}(i-1)!=f_i$ then we would like to have $Q(f_i) \equiv 0 \pmod p_i$ for a suitable pick of a prime $p_i$. But first notice that $\gcd(Q(f_i), f_i)=Q(0)$ for large enough $i$ as by euclidean alg we have its just $\gcd(Q(0),f_i)$ and for large enough $i$ we get that eventually $Q(0) \mid f_i$ must happen which then shows us that a $p_i \ge i$ does exists because if it didn't then from the gcd observation we made if for large $i$ we had that $Q(f_i)$ only admitted prime divisors below $i$ then each prime power could divide $Q(0)$ and for even larger $i$ this would not be possible as one side $\nu_r$ for some $r$ prime below $i$ would be too big for $Q(0)$ to handle. Now notice that we would have $P((p_i-i)!) \equiv 0 \pmod{p_i}$ so all we need to prove that is that as we make $i$ larger and larger we can eventually have $(p_i-i)!-p_i>N$ for some large number $N$ of our choice. Indeed to do this consider an $i=\ell !+2$ for an $\ell$ prime number which satisfies (can be seen to exist using some basic PNT tech) that the gap between this prime and the very next one is larger than $M+1$, and now notice that for any of the numbers $\ell !+\kappa$ for $2 \le \kappa \le \ell+M+1$ cannot have a prime divisors $p$ above $\ell !+1$ which means that each such $p$ satisfies $p \mid (\ell !+1)!$ and that means $p \mid (i-1)!$ but also back to our $p_i$ notice that if we had that it divides one of such $\ell !+\kappa$ numbers from above then $p_i \mid f_i$ which would imply that $p_i \mid Q(0)$ which is false for large $i$ as $p_i \ge i$ is trivial, therefore we can make this stronger and get $p_i \ge i+\ell+M$ which now finishes as this means that $(p_i-i)!-p_i \ge (p_i-i)((\ell+M-1)!-1)+i$ and notice that the pick of $\ell$ can be arbitrarily large as well (just like the size of $M$, thanks to PNT) we clearly have this thing is unbounded so by size we cannot have that $P((p_i-i)!)=p_i$ therefore $P((p_i-i)!)$ is composite thus we are done .

Let $P(x)=a_dx^d+\dots+a_0$ and assume $a_d>0$ and for now $d \geq 2$. Also obviously $a_0 \neq 0$. Recall that strong Wilson's theorem states \[(p-k)! \equiv \frac{(-1)^k}{(k-1)!} \pmod p \]Now see that \[P \left( \frac{(-1)^{n+1}}{n!} \right)=\frac{a_d(-1)^{(n+1)d}+n!a_{d-1}(-1)^{(n+1)(d-1)}+\dots+a_0 (n!)^d}{(n!)^d}\]And hence for convenience define $Q(x) \coloneqq a_0x^d+\dots+a_d$. Claim: For large enough odd $n$, we have $\text{rad}(Q(n!)) \nmid n!$. Proof: Take $n$ large and say $q \mid Q(n!)$ and assume $q \leq n$ for all such $q$ (this implies that we must have $q \mid a_d$). Assume $\nu_q(n!)>\nu_q(a_d)$ for all those $q$. Hence $\nu_q(Q(n!))=\nu_q(a_d)$ and hence $|Q(n!)| \leq a_d$, which is a size contradiction for large $n$. $\square$ So say $n$ is large odd number and $p>n$ divides $Q(n!)$. And hence \[0 \equiv Q(n!) \equiv \frac{Q(n!)}{(n!)^d}=P \left(\frac1{n!} \right) \equiv P((p-n-1)!) \pmod p \implies |P((p-n-1)!)|=p\]But now let $n=N!+1$ where $N$ is very large. And hence $p \geq N!+N+1$. And so $(p-n-1)! \geq (N-1)!$ and assume at this point (and afterwards) we have $P$ is strictly increasing and positive. And hence \[p=P((p-n-1)!) \geq P((N-1)!) \gg N!+1=n\]And hence repeat the process \[p=P((p-n-1)!) \geq P((P(N!-1)-n-1)!) \gg P((N-1)!)\]This is due to the fact we assumed $d \geq 2$. And if we keep on doing this we get that $p-n-1$ keeps getting bigger and bigger (in say terms of $n$), which means $p$ is unbounded, which is a contradiction. For $d=1$, see that $a_0=\pm 1$ and using a similar method as above we can prove $a_1=1$. And see that $4!+1$ and $5!-1$ are composite numbers.