Find x, where $x^\text{n}\equiv\text{m}\space\left(\text{mod}\space\text{p}_1\cdot\text{p}_2\right)$

Question

Well, I have the following equation:

$$x^\text{n}\equiv\text{m}\space\left(\text{mod}\space\text{p}_1\cdot\text{p}_2\right)\space\Longleftrightarrow\space x=\dots\tag1$$

Where $\text{n}\in\mathbb{N}^+$, $\text{m}\in\mathbb{N}^+$ and $\text{p}_1\space\wedge\space\text{p}_2\in\mathbb{P}$.

How can I solve this in general for $x$?

---

I solved by hand, that:

$$x^3\equiv7\space\left(\text{mod}\space5\cdot11\right)\space\Longleftrightarrow\space x=55\text{k}+28\tag2$$

Where $\text{k}\in\mathbb{Z}$.

But I want to do it for a general case.

Answer 1

For any two distinct primes $p_1,p_2$, there are always integers $a,b$ such that $$ap_1+bp_2=1.$$

Then, if $x_1^n\equiv m\space\left(\text{mod}\space p_1\right)$ and $x_2^n\equiv m\space\left(\text{mod}\space p_2\right)$, a solution of $x^n\equiv m\space\left(\text{mod}\space p_1\cdot p_2\right)$ is given by $x=bp_2x_1+ap_1x_2$.

In general, solving an equation such as $x_1^n\equiv m\space\left(\text{mod}\space p_1\right)$ is not straightforward. If you only consider powers $n$ which are coprime to $p_1-1$ and $p_2-1$, then things are simplified slightly. (This was true for your example.)

In that case you only need to find a single solution to each of $x_1^n\equiv m\space\left(\text{mod}\space p_1\right)$ and $x_2^n\equiv m\space\left(\text{mod}\space p_2\right)$ and obtain $x$ as shown above. Then the general solution is given by $kp_1p_2+x.$

The example

First note $1\text x 11-2\text x5=1$.

$3^3\equiv 7\space\left(\text{mod}\space 5\right)$ and $6^3\equiv 7\space\left(\text{mod}\space 11\right).$

Then $x=-10x_1+11x_2=-27$. Therefore the general solution is $$55k-27$$ which is equivalent to your solution.

Answer 2

First question if $(n,(p_1-1)(p_2 -1)) = 1$ if that is the case then the answer is trivially true: for take $m'$ to be the residue of $m$ between $0$ and $p_1p_2$

It is easy to check that for all $n$ relatively prime to $(p_1 - 1)(p_2 - 1)$ there is an $x \in Z$ such that $x^n \equiv m'$ ( mod $p_1 p_2$ )

If n isnt such a number then I am sure there are m that exist such that this equivalence is not solvable.