Prove that for any polynomial $P$ with integer coefficients and any natural number $k$ there exists a natural number $n$ such that $P(1) + P(2) + ...+ P(n)$ is divisible by $k$.

Determine all positive integers$ n$ such that $f_n(x,y,z) = x^{2n} + y^{2n} + z^{2n} - xy - yz - zx$ divides $g_n(x,y, z) = (x - y)^{5n} + (y -z)^{5n} + (z - x)^{5n}$, as polynomials in $x, y, z$ with integer coefficients.

Find all integers $n$ such that there exists a polynomial $P(x)$ with integer coefficients satisfying $$P(\sqrt[3]{n^2} + \sqrt[3]{ n}) = 2016n + 20\sqrt[3]{n^2} + 16\sqrt[3]{n}$$

Decide whether for every polynomial $P$ of degree at least $1$, there exist infinitely many primes that divide $P(n)$ for at least one positive integer $n$. [i](Walther Janous)[/i]

Find all positive integers $n$ such that there exist non-constant polynomials with integer coefficients $f_1(x),...,f_n(x)$ (not necessarily distinct) and $g(x)$ such that $$1 + \prod_{k=1}^{n}\left(f^2_k(x)-1\right)=(x^2+2013)^2g^2(x)$$

Prove that if $\frac{p}{q}$ is an irreducible rational number that serves as a root of the polynomial $f(x) = a_0x^n + a_1x^{n-1} + ... + a_n$ with integer coefficients, then $p - kq$ is a divisor of $f(k)$ for any integer $k$.

Find a polynomial $P$ of lowest possible degree such that (a) $P$ has integer coefficients, (b) all roots of $P$ are integers, (c) $P(0) = -1$, (d) $P(3) = 128$.

Let $P(x)$ be a polynomial with integer coefficients. It is known that the number $\sqrt2+\sqrt3$ is its root. Prove that the number $\sqrt2-\sqrt3$ is also its root.

Let $P(x)=x^{2016}+2x^{2015}+...+2017,Q(x)=1399x^{1398}+...+2x+1$. Prove that there are strictly increasing sequances $a_i,b_i, i=1,...$ of positive integers such that $gcd(a_i,a_{i+1})=1$ for each $i$. Moreover, for each even $i$, $P(b_i) \nmid a_i, Q(b_i) | a_i$ and for each odd $i$, $P(b_i)|a_i,Q(b_i) \nmid a_i$ Proposed by [i]Shayan Talaei[/i]

Prove that there does not exist a polynomial $P (x)$ with integer coefficients and a natural number $m$ such that $$x^m + x + 2 = P(P(x))$$ holds for all integers $x$.

Let $P(x)=x^{2000}-x^{1000}+1$. Do there exist distinct positive integers $a_1,\dots,a_{2001}$ such that $a_ia_j|P(a_i)P(a_j)$ for all $i\neq j$? [I]Proposed by A. Baranov[/i]

Decide whether for every polynomial $P$ of degree at least $1$, there exist infinitely many primes that divide $P(n)$ for at least one positive integer $n$. [i](Walther Janous)[/i]

Let $P_1(x) = x^2 + a_1x + b_1$ and $P_2(x) = x^2 + a_2x + b_2$ be two quadratic polynomials with integer coeffcients. Suppose $a_1 \ne a_2$ and there exist integers $m \ne n$ such that $P_1(m) = P_2(n), P_2(m) = P_1(n)$. Prove that $a_1 - a_2$ is even.

Let $P(x)$ be a polynomial with integer coefficients. Show that if $Q(x) = P(x) +12$ has at least six distinct integer roots, then $P(x)$ has no integer roots.

Let $P(x)$ be a polynomial whose coefficients are positive integers. If $P(n)$ divides $P(P(n)-2015)$ for every natural number $n$, prove that $P(-2015)=0$. [hide]One additional condition must be given that $P$ is non-constant, which even though is understood.[/hide]

Find all nonzero polynomials $P(x)$ with integers coefficients that satisfy the following property: whenever $a$ and $b$ are relatively prime integers, then $P(a)$ and $P(b)$ are relatively prime as well. Prove that your answer is correct. (Two integers are [b]relatively prime[/b] if they have no common prime factors. For example, $-70$ and $99$ are relatively prime, while $-70$ and $15$ are not relatively prime.)

Consider the trinomial $f(x) = x^2 + 2bx + c$ with integer coefficients $b$ and $c$. Prove that if $f(n) \ge 0$ for all integers $n$, then $f(x) \ge 0$ even for all rational numbers $x$.

Let $p$ be a prime number. Let $\mathbb F_p$ denote the integers modulo $p$, and let $\mathbb F_p[x]$ be the set of polynomials with coefficients in $\mathbb F_p$. Define $\Psi : \mathbb F_p[x] \to \mathbb F_p[x]$ by \[ \Psi\left( \sum_{i=0}^n a_i x^i \right) = \sum_{i=0}^n a_i x^{p^i}. \] Prove that for nonzero polynomials $F,G \in \mathbb F_p[x]$, \[ \Psi(\gcd(F,G)) = \gcd(\Psi(F), \Psi(G)). \] Here, a polynomial $Q$ divides $P$ if there exists $R \in \mathbb F_p[x]$ such that $P(x) - Q(x) R(x)$ is the polynomial with all coefficients $0$ (with all addition and multiplication in the coefficients taken modulo $p$), and the gcd of two polynomials is the highest degree polynomial with leading coefficient $1$ which divides both of them. A non-zero polynomial is a polynomial with not all coefficients $0$. As an example of multiplication, $(x+1)(x+2)(x+3) = x^3+x^2+x+1$ in $\mathbb F_5[x]$. [i]Proposed by Mark Sellke[/i]

Find the free coefficient of the polynomial $P(x)$ with integer coefficients, knowing that it is less than $1000$ in absolute value and that $P(19) = P(94) = 1994$.

Let $n$ be a given positive integer. Alice and Bob play a game. In the beginning, Alice determines an integer polynomial $P(x)$ with degree no more than $n$. Bob doesn’t know $P(x)$, and his goal is to determine whether there exists an integer $k$ such that no integer roots of $P(x) = k$ exist. In each round, Bob can choose a constant $c$. Alice will tell Bob an integer $k$, representing the number of integer $t$ such that $P(t) = c$. Bob needs to pay one dollar for each round. Find the minimum cost such that Bob can guarantee to reach his goal. [i]Proposed by ltf0501[/i]

Suppose a real number $a$ is a root of a polynomial with integer coefficients $P(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0$. Let $G=|a_n|+|a_{n-1}|+...+|a_1|+|a_0|$. We say that $G$ is a [i]gingado [/i] of $a$. For example, as $2$ is root of $P(x)=x^2-x-2$, $G=|1|+|-1|+|-2|=4$, we say that $4$ is a [i]gingado[/i] of $2$. What is the fourth largest real number $a$ such that $3$ is a [i]gingado [/i] of $a$?

Let $P(x) = x^4 + x^3 + x^2 + x + 1$. Show that there exist two non-constant polynomials $Q(y)$ and $R(y)$ with integer coefficients such that for all $Q(y) \cdot R(y)= P(5y^2)$ for all $y$ .

Find all pairs of polynomials $P(x),Q(x)$ with integer coefficients such that $P(Q(x)) = (x - 1)(x - 2)...(x - 9)$ for all real numbers $x$

Suppose $a_1,a_2,a_3,a_4$ are distinct integers and $P(x)$ is a polynomial with integer coefficients satisfying $P(a_1) = P(a_2) = P(a_3) = P(a_4) = 1$. (a) Prove that there is no integer $n$ such that $P(n) = 12$. (b) Do there exist such a polynomial and $a_n$ integer $n$ such that $P(n) = 1998$?

Determine all pairs $(P, d)$ of a polynomial $P$ with integer coefficients and an integer $d$ such that the equation $P(x) - P(y) = d$ has infinitely many solutions in integers $x$ and $y$ with $x \neq y$.