Problem from Olympiads of mathematics about elementary number theory Can you please help me with this problem from the Italian selection of the Olympiads of mathematics?
Let $p(x)$ be a polynomial with integer coefficients and let $p(0)=6$.
Exactly $40$ $p(n)$ with $n$ integer and $1 \leq n \leq 60$ are multiples of $3$.
Exactly $30$ $p(n)$ with $n$ integer and $1\leq n \leq 60$ are multiples of $4$.
How many $p(n)$ with $n$ integer and $1\leq n \leq 60$ are multiples of $6$?
Thanks in advance. Keep in mind that I don't have the text in front of me and I am posting just what I remember, thus there could be errors (if you cannot find a solution odds are I did not notice an important information, but this should be enough). Also note that I am not an native English speaker so please forgive me if I made errors with grammar. Thanks for your attention and consideration.
 A: You want to think in terms of residue classes.  We are given that $p(n)\equiv 0 \pmod 3$ for two of the three residue classes.  As $p(0)=6 \equiv 0 \pmod 3$, we will have $p(n) \equiv 0$ for $n \equiv 0 \pmod 3$.  We must have one of the other residue classes yield $0$ and the other not.  Similarly working $\bmod 4$ we must have two of the four classes yield $0$.  The issue is whether the other two yield $2$ or something odd.  If it is $2$, we will have $40$ numbers that yield multiples of $6$.  If it is odd, we will only have $20$.  
One simple approach, if you trust the problem setter, is that all polynomials that meet the three conditions must yield the same answer.  $p(x)=8x^2+2x+6$ will do.  If $n \equiv 0,2 \pmod 3, p(n) \equiv 0 \pmod 3$.  If $n\equiv 1,3 \pmod 4, p(n) \equiv 0 \pmod 4$  This has $p(n)$ even for all $n$, so there are $40\ n$'s in range that have $p(n) \equiv 0 \pmod 6$  You might be expected to prove that all polynomials that have two residue classes that give $0 \bmod 4$ will have the others give $2 \bmod 4$, but I haven't done it.
A: I propose that take an example polynomial which satisfies your conditions and look at the result. $p(n)=(n-1)\cdot (n-6)$ is such a polynomial which gives you the answer $40$.
Note that this method assumes that question is well-posed and not constitutes a proof. However founding another polynomial which gives a different result makes the question wrong.
A: I think that i have a solution. Let's see
Let $p(x)=\sum_{i=0}^k a_ix^i$ the polynomial, where $a_i\in \mathbb{Z}$ and $a_0=6$.
We use the following lemma: If $p(x)$ is a polynomial whith integer coefficients, and $a,b\in \mathbb{Z}$, such that $a\equiv b\pmod{m}$ then: $$p(a)\equiv p(b) \pmod{m}.$$
Then all numbers $p(3),p(6),\ldots,p(60)$ are multiples of $3$, because $3k\equiv 0 \pmod{3}$ and by the lemma:$$p(3k)\equiv p(0)\equiv 6 \equiv  0\pmod{3}.$$
Also, $p(1),p(4),\ldots,p(58)$ have the same residue modulo $3$, analogy $p(2),p(5),\ldots,p(59)$ have the same residue modulo $3$. This means that the numbers $p(3k+1)$ or $p(3k+2)$ are multiples of $3$ separately ($0\leq k\le 19$).
By other hand:
$$p(4k)\equiv p(0) \equiv 6 \equiv 2 \pmod{4}$$
$$p(4k+1)\equiv p(1) \equiv \sum_{i=0}^ka_i \equiv r\pmod{4}$$
$$p(4k+2)\equiv p(2) \equiv \sum_{i=0}^k2^ia_i \equiv a_0+2a_1+\sum_{i=2}^k2^ia_i\equiv 2(1+a_1) \pmod{4}$$
$$p(4k+3)\equiv p(3) \equiv \sum_{i=0}^k3^ia_i \equiv \sum_{i=0}^k(-1)^ia_i\equiv s \pmod{4}$$
Then the numbers $p(4k)$ are not multiples of 4. This means that by Pigeonhole principle at less one number between $r$ and $s$ is $0$ modulo $4$. But
$$r+s\equiv \sum_{i=0}^ka_i+\sum_{i=0}^k(-1)^ia_i\equiv 2\sum_{i=0}^{k}a_{2i}\pmod{4}$$
And from this we can conclude that the numbers $p(4k),p(4k+1),p(4k+2),p(4k+3)$ are multiples of $2$ (because they have residue $0$ or $2$ module $4$).
Then $p(1),p(2),\ldots,p(60)$ are multiples of $2$. And as there only $40$ numbers multiples of $3$. There are $40$ numbers multiples of $6$.
Comment: Is not necessary work with the modulo $3$.
