For integers $a$ and $b$ with $0 \leq a,b < {2010}^{18}$ let $S$ be the set of all polynomials in the form of $P(x)=ax^2+bx.$ For a polynomial $P$ in $S,$ if for all integers n with $0 \leq n <{2010}^{18}$ there exists a polynomial $Q$ in $S$ satisfying $Q(P(n)) \equiv n \pmod {2010^{18}},$ then we call $P$ as a good polynomial. Find the number of good polynomials.
Problem
Source:
Tags: algebra, polynomial, modular arithmetic, number theory proposed, number theory
31.12.2010 20:28
I give a hint: We can find such a polynom Q(x) if and only if for a polynom P(x)=ax^2+bx, a is divisible to (2010^9)/2 and (2010,b)=1 .
17.12.2020 11:16
Here is a solution by Burak Varıcı. We will prove iff $P(x)$ is good, then $2^8 \cdot 1005^9|a$ and $(2010, b)=1$. As a result the answer will be $$2\cdot{2010}^9\cdot{2010}^{18}\cdot \left(1-\dfrac{1}{2}\right)\left(1-\dfrac{1}{3}\right)\left(1-\dfrac{1}{5}\right)\left(1-\dfrac{1}{67}\right)=2^5\cdot 3 \cdot 11 \cdot {2010}^{26}$$ Let for every $n$ we have $Q(P(n)) \equiv n \pmod{2010^{18}}$ . It is not hard to see $P(n)$ is injective in $\pmod{2010^{18}}$. By CRT, for every $p = 2, 3, 5, 67$ we have $P(n)$ is injective in $\pmod{p^{18}}$. Take $p \in {2, 3, 5, 67}$. Assuming contrary, let $p|b$. Thus $P(p^{17}) \equiv P(0) \pmod{p^{18}}$. Contradiction. $(2010, b)=1$ If for some $p$ $p \nmid a$, we see $P(-a^{-1}b) \equiv P(0)$. Contradiction. Hence $2010|a$ $$Q(P(1)) \equiv 1 \Rightarrow c(a+b)^2+d(a+b) \equiv 1$$$$Q(P(-1)) \equiv -1 \Rightarrow c(a-b)^2+d(a-b) \equiv -1$$From these equalities, we conclude in $$2b\left(a^2-b^2\right)c\ \equiv 2a\ \pmod {2010^{18}}$$$$2b\left(a^2-b^2\right)d\ \equiv -2\left(a^2+b^2\right) \pmod {2010^{18}}$$We know ${\left(b\left(a^2-b^2\right)\right)}^{-1}\ \pmod {2010^{18}}$ exists. Thus $$c\equiv {\left(b\left(a^2-b^2\right)\right)}^{-1}a+\varepsilon \dfrac{{2010}^{18}}{2} \pmod{2010^{18}}$$$$d\equiv -{\left(b\left(a^2-b^2\right)\right)}^{-1}\left(a^2+b^2\right)+\varepsilon \dfrac{{2010}^{18}}{2} \pmod {2010^{28}}$$where $\varepsilon \in \{0, 1 \}$ $$Q\left(P\left(x\right)\right)-x\ \equiv \ -{\left(b\left(a^2-b^2\right)\right)}^{-1}a^2x\left(x-1\right)\left(x+1\right)\left(ax+2b\right)+\varepsilon \dfrac{{2010}^{18}}{2}x\left(x-1\right)\pmod {2010^{18}}$$Put $x=2$ which gives us $2010^{18} | 2^2 \cdot 3 \cdot a^2 \Rightarrow 2^8 \cdot 1005^9 |a$ From end to beginning we can define $c$ and $d$ according to $a$ and $b$.