Modular arithmetic with polynomialGiven n = p q where p &amp; q , p ≠ q are primes, P(x) is polynomial and z ∈ Z n I need to prove that: p ( z ) ≡ 0 ( mod n ) ⟺ p ( z ( mod p ) ) ≡ 0 ( mod p ) ∧ 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.

Question

Modular arithmetic with polynomialGiven   n  =  p  q where   p    &amp;amp;    q  ,  p  ≠  q are primes, P(x) is polynomial and   z  ∈            Z              n      I need to prove that:  p  (  z  )  ≡  0    (  mod    n  )    ⟺    p  (  z    (  mod    p  )  )  ≡  0    (  mod    p  )    ∧  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&#039;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&#039;t have much success with this.

Hailee West · Accepted Answer

Step 11. Chinese remainder theorem, to go from p,q to n.Step 22. Expand the polynomial P, to see that   P  (  z    mod      m  )  ≡  P  (  z  )    (  mod    m  ).

jorgejasso85xvx · Accepted Answer

Step 1First, generally        p  ,  q  ∣  n    ⟺        l    c    m    (  p  q  )  ∣  n  .   But          l    c    m    (  p  ,  q  )  =  p  q   when p,q are coprime.Second        p  ∣  P  (  n  )    ⟺    p  ∣  P  (  n         m    o    d       p  )    holds true because               m    o    d       p    :     A  ≡  a     ⇒     P  (  A  )  ≡  P  (  a  )  ,  , for any polynomial P with integer coefficients. This is true because polynomials are composed of Sums and Products, and these operations respect congruences, i.e. the rules below hold trueCongruence Sum Rule       A  ≡  a  ,    B  ≡  b     ⇒         A    +    B        ≡        a    +    b             (  m  o  d     m  )Proof         m        |      A    −    a  ,     B    −    b     ⇒     m         |       (  A    −    a  )  +  (  B    −    b  )     =         A    +    B    −    (    a    +    b    )  Congruence Product Rule        A  ≡  a  ,        a  n  d        B  ≡  b     ⇒         A    B    ≡    a    b             (  m  o  d     m  )Proof         m        |      A    −    a  ,     B    −    b     ⇒     m         |       (  A    −    a  )     B  +  a     (  B    −    b  )     =         A    B    −    a    b  Step 2Beware that such rules need not hold true for other operations, e.g. the exponential analog of above       A    B    ≡      a    b   is not generally true (unless   B  =  b  ,   so it follows by applying b times the Product Rule).

Given n=pq where p and q, p ne q are primes, P(x) is polynomial and z in Z_n

Answered question

Answer & Explanation

New Questions in Algebra II