# exist $x$ such that $x^k \equiv m$ mod $(p_1\cdot p_2) \Leftrightarrow$ exists $x_1,x_2$ : $x_1^k\equiv m(p_1)$ and $x_2^k\equiv m(p_2)$

Let $$p_1,p_2$$ prime numbers, I wish to show that: exist $$x$$ such that $$x^k \equiv m$$ mod $$(p_1\cdot p_2) \Leftrightarrow$$ exists $$x_1,x_2$$ : $$x_1^k\equiv m(p_1)$$ and $$x_2^k\equiv m(p_2)$$

A first approach I took, was to use $$y\equiv m(p_1) , y\equiv m(p_2) \Leftrightarrow y\equiv m(p_1\cdot p_2)$$, then by assigning $$x^k=y$$ the problem comes to find whether $$y$$ has a $$k$$-order root in $$U(\mathbb{Z}_{p_1\cdot p_2})$$. How ever it doesn't seem to simplify the problem.

A second approach I took was to use the fact which derived from CRT , that $$U(\mathbb{Z}_{p_1 \cdot p_2}) \cong U(\mathbb{Z}_{p_1}) \times U(\mathbb{Z}_{p_2})$$, In $$U(z_{p_i})$$ which are cyclic groups, there is a solution for $$x^k \equiv m(p_i) \Leftrightarrow m^{\frac{p_1-1}{gcd(k,p_1)}}=1 (p_i)$$. So assuming $$gcd(k,p_1) = 1$$ there are solutions for the equations $$x_1,x_2$$. But I am struggling to show that $$\pi^{-1}(x_1,x_2)$$ (when $$\pi$$ is the isomorphism from CRT), is a solution for $$x^k \equiv m (p_1p_2)$$.

So in case my second approach is correct, I would be glad for some help with showing $$\pi^{-1}(x_1,x_2)$$ is a solution, and also in case $$x$$ is a solution mod $$(p_1p_2)$$ then $$\pi_1(x) ,\pi_2(x)$$ are solutions mod $$p_1$$, $$p_2$$ respectively.

Also other approaches or ideas would be appreciated.

related question:

If $$x \equiv a \pmod {p_1}$$ and $$x\equiv a \pmod{p_2}$$, then is it true that $$x\equiv a \pmod{p_1p_2} ?$$

• Please, tell us more about the numbers $p_1$ and $p_2$! Are they coprime? Are they prime numbers? Can they be equal? We can guess (probably correctly given all the context), but it would look cleaner, if you volunteered such bits :-) Dec 29, 2018 at 10:26
• @JyrkiLahtonen Sorry! I was thinking it is obvious I am talking about prime numbers cause I related to CRT. I'll edit! Thanks for your correction! Dec 29, 2018 at 10:50
• Yes, it was not difficult to guess. Sorry about being a bit cranky. Dec 29, 2018 at 10:54

$$x ≡a\mod (p_1)$$ , if $$x=(kp_2)p_1+a$$

$$x ≡a\mod (p_2)$$ , if $$x=(lp_1)p_2+a$$

Then:

$$2x=(k+l)p_1p_2+2a$$

If $$2|k+l$$, then:

$$x=(\frac{k+l}{2})p_1p_2+a$$

Or; $$x ≡a\mod (p_1)(p_2)$$

Example:

$$72=2.5.7+2 ≡2\mod 5 ≡2\mod 7 ≡2\mod 35$$

We may assume $$kp_1=x_1$$ and $$lp_2=x_2$$ and we have:

$$x_1^t=k^t.p_1^t$$

$$x_2^t=l^t.p_2^t$$

If $$l^t.p_2^{t-1}=k^t.p_1^{t-1}=m$$, then:

$$x_1 ≡m\mod (p_1)$$

$$x_2 ≡m\mod (p_2)$$