# $f(x)\equiv_n 0$ has a solution iff $f(x)\equiv_{p_i ^{a_i}} 0$ has a solution

Let $f(x)\in \mathbb Z [x]$ and $n=p_1 ^{a_1}\cdot...\cdot p_t ^{a_t}$ prime factorization. show that $f(x)\equiv_n 0$ has a solution iff $f(x)\equiv_{p_i ^{a_i}} 0$ has a solution for each $i=1,2,...,t$

this question appeard in "classical introduction to modern number theory".
proving $(\Rightarrow)$ is trivial, yet I couldn't find a way to prove the second part.

• Hello! Please, consider the idea of editing your question with the attempts you've made so far, and be more clear about things you got more stuck into. This way, users can provide answers at a higher-quality rate. :-) – Filippo De Bortoli Nov 24 '14 at 18:03

I think I managed to find a proof:
Let $x_i$ be a solution for $f(x)\equiv _{p_i ^{a_i}}0$ for each $i=1,...,t$
from the Chinese reminder theorem we can find $x_0$ such that $x_0 \equiv _{p_i ^{a_i}} x_i$ for every $i=1,...,t$. then for every $i=1,...,t$ $f(x_0)\equiv _{p_i ^{a_i}}0$ which means that $p_i ^{a_i}\mid f(x_0)$ so because for every $i\not =j$ $GCD(p_i ,p_j)=1$ it follows that $n=\prod p_i^{a_i}\mid f(x_0)$ and that's it.

• I'll add details to my answer, if you don't mind. :-) – Filippo De Bortoli Nov 24 '14 at 18:16
• ok no problem :) – Nathan Sikora Nov 24 '14 at 18:17

Let's take this by one step at a time.

Let $\alpha_1, \dots, \alpha_t$ be the solution is a solution of $f(x) \equiv_{p_i^{a_i}} 0$. Iterating the usage of the Chinese remainder theorem, it is possible to find $y$ such that $\forall_{i \in 1..t} f(x) \equiv_{p_i^{a_i}} 0$. Thus, we can say that $$f(x) \equiv_{p_i^{a_i}} 0 \iff p_i^{a_i} \mid f(x) \iff \exists k_i \in \mathbb{Z}[x]. f(x) = p_i^{a_i} \cdot k_i$$ where $$k_i = q \prod_{j=1}^{i-1}p_{j}^{a_j}, q \in \mathbb{Z}[x]$$ knowing that $\forall_{i \neq j} \gcd(p_i, p_j) = 1$, we conclude: $$f(y) = q \prod_{j=1}^{t}p_{j}^{a_j} \implies p_{1}^{a_1}\cdots p_{t}^{a_t} = n \mid f(y) \implies f(y) \equiv_{n} 0.$$

• $x$ is not necessarily the same for each $i$. – Nathan Sikora Nov 24 '14 at 18:07
• Good observation. Your proof is correct, it's somehow richer than mine (I didn't properly use the Chinese remainder theorem, even though I wrote thinking about that). – Filippo De Bortoli Nov 24 '14 at 18:16