a) This problem is trivialized by Lagrange Theorem, but here is a solution that does not use it. Lemma. For a prime number $p$ we have that $$1^k+2^k+3^k+\dots+(p-1)^k = \begin{cases} 0 \pmod p \;\; \text{if} \;\; p-1 \nmid k \\ -1 \;\; \text{otherwise} \end{cases}$$Proof. Trivial using primitive roots. Now, let $S=\{p_1,p_2, \dots p_m\}$, and it is very known that $P(x)=P(y) \pmod p$ if $x=y \pmod p$. Claim. There exists $t_i \in \{1,2,3,\dots,p_i-1\}$ such that $P(t_i) \neq 0 \pmod {p_i}$ Proof. Let $a_j$ be the coefficient with the least index such that $a_j \neq 0 \pmod {p_i}$ and $j\neq n$, such $a_j$ exists because all coefficients are not divisible by the same prime. So $P(x)=a_n x^n+\dots +a_j x^j \pmod{ p_i}$ , and assume that for each $x \in \{1,2,3,\dots,p_i-1\}$ we have $P(x)=0 \pmod {p_i}$, so we must have that $P(x)=a_n x^{n-j}+\dots+a_j=0 \pmod {p_i}$ for each $x \in \{1,2,3,\dots,p_i-1\}$. Adding all these we get that $$\sum_{i=1}^{p_i-1}P(i)=a_n (1^{n-j}+2^{n-j}+\dots +(p_i-1)^{n-j}) +\dots + (n-j)a_j = 0 \pmod {p_i}$$Using the first lemma,and since $p_i-1 \nmid n-j$ for size reasons, we must have $\sum_{i=1}^{p_i-1}P(i)=(n-j)a_j= 0 \pmod {p_i}$ wich is not true. $\blacksquare$ So for each $p_i$, there exists a $t_i$ such that $P(t_i) \neq 0 \pmod {p_i}$, now we take $t \equiv t_i \pmod {p_i}$ for each $i\leq m$, such $t$ exists by CRT, and satisfies the problem condition. $\blacksquare$

b) $P(x)=x(x+1)...(x+1396)$ works

XbenX wrote: a) This problem is trivialized by Lagrange Theorem, I don't understand your idea. How to apply Lagrange Theorem?

XbenX wrote: Now, let $S=\{p_1,p_2, \dots p_m\}$, and it is very known that $P(x)=P(y) \pmod p$ if $x=y \pmod p$. But $S$ is a infinite set

Taha1381 wrote: Call a polynomial $P(x)=a_nx^n+a_{n-1}x^{n-1}+\dots a_1x+a_0$ with integer coefficients primitive if and only if $\gcd(a_n,a_{n-1},\dots a_1,a_0) =1$. a)Let $P(x)$ be a primitive polynomial with degree less than $1398$ and $S$ be a set of primes greater than $1398$.Prove that there is a positive integer $n$ so that $P(n)$ is not divisible by any prime in $S$. b)Prove that there exist a primitive polynomial $P(x)$ with degree less than $1398$ so that for any set $S$ of primes less than $1398$ the polynomial $P(x)$ is always divisible by product of elements of $S$. in part $a$ , $S$ is a finite set otherwise it wouldn't work

The following solution assume that $S$ is a finite set a) Lemma (Lagrange Theorem): Let $p$ be a prime and let $P(x)=a_nx^n+a_{n-1}x^{n-1}+ \ldots + a_1x+ a_0$ be a polynomial degree $n$. Then the equation $$ P(x) \equiv 0 \pmod p $$has at most $n$ distinct roots modulo $p$. Also if $P(x)$ has more than $n$ distinct roots modulo $p$ then $a_n \equiv a_{n-1} \equiv \ldots \equiv a_1 \equiv a_0 \equiv 0 \pmod p$ Let $S=\{ p_1,p_2,p_3, \ldots , p_k \}$ . Then since $p_i >1398$ for all $i$, by applying the above lemma, if for all the numbers $x \equiv i \pmod p_i$ for $i=0,1,2 \ldots , p_i-1 $ are all the roots of $P(x) \pmod p$, then $p_i \mid gcd(a_n,a_{n-1},a_{n-2} , \ldots , a_1, a_0) =1 $ (A Contradiction) Thus for every $p_i$, there exists $a_i$ such that $P(a_i) \not \equiv 0 \pmod {p_i}$. Now by choosing $n$ satisfies $$ n \equiv a_i \pmod {p_i} \text{ for all } i=1,2,3, \ldots , k $$Which is true by CRT, we are done! b) Choosing $P(x)=x(x-1)(x-2) \ldots (x-1396) +1398!$ , then since $P(i) \equiv 0 \pmod {1398} $ for all $i=0,1,2,3, \ldots , 1397$, we conclude $P(n) \equiv 0 \pmod {1398} $ $\forall n$ and done (This comes from $ a - b \mid P(a) - P(b)$ )