1
$\begingroup$

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} ?$

$\endgroup$
  • $\begingroup$ 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 :-) $\endgroup$ – Jyrki Lahtonen Dec 29 '18 at 10:26
  • $\begingroup$ @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! $\endgroup$ – dan Dec 29 '18 at 10:50
  • $\begingroup$ Yes, it was not difficult to guess. Sorry about being a bit cranky. $\endgroup$ – Jyrki Lahtonen Dec 29 '18 at 10:54
1
$\begingroup$

$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)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.