Given n=pq, where p and q are primes, P(x) is polynomial and z∈Zn.
I need to prove that:
P(z) ≡ 0 mod n iff P(z mod p) ≡ 0 mod p AND P(z mod q) ≡ 0 mod q.
If i could prove the more general case:
P(z) mod n ≡ P(z mod p) mod p
(q is the same) then i could also prove what i need of course.
from my understanding so far, the above is true, but i can't figure out a way to prove this.
Back to the original question, i tried to see why the fact that p divides P(z mod p) and q divides P(z mod q) implies that pq divides P(z) and vice versa, but i didn't have much success with this.
A hint is sufficient. thank you!