Prove that there exists integers $r,s$ such that $r^k\equiv a \pmod{p_1}$ and $s^k \equiv a \pmod{p_2}$

Question

Given that $k$ is a positive integer and $p_1,p_2$ are co primes such that for some integers $q,a$ and $r,s$ $$q^k \equiv a \pmod{p_1p_2} \iff r^k \equiv a \pmod{p_1} \:\text{ and }\:s^k\equiv a \pmod{p_2}$$

My try: I tried to prove from right to left first.

$$r^k=mp_1+a$$ and $$s^k=np_2+a$$

Now by Euclid's algorithm we have $m=m'p_2+r_2$ and $n=n'p_1+r_1$

Thus we get $$r^k=m'p_1p_2+p_1r_2+a$$ and $$s^k=n'p_1p_2+r_1p_2+a$$

I got stuck here.

Answer 1

This is a special case $\,f(x) = x^k-a\, $ of the result below, which shows that if $\,m,n\in\Bbb Z\,$ are coprime and $\,f\in\Bbb Z[x]\,$ is a polynomial with integer coefs, then the roots of $\,f\bmod mn$ correspond to CRT-combining the roots of $f\bmod m\,$ and $\,f\bmod n.\,$ In particular this yields the sought existence claim:

$$ f\,\ \text{is solvable $\!\bmod mn\iff f\,$ is solvable $\!\bmod m\,$ & $\!\bmod n$}\qquad$$

---

Suppose that $\,f(x)\,$ is a polynomial with integer coefs and $\,m,n\,$ are coprime integers. By CRT, solving $\,f(x)\equiv 0\pmod{\!mn}\,$ is equivalent to solving $\,f(x)\equiv 0\,$ mod $\,m\,$ and mod $\,n,\,$ and each CRT combination of a root $\,r_i\,$ mod $\,m\,$ with a root $\,s_j\,$ mod $\,n\,$ corresponds to a unique root $\,t_{ij}\bmod mn\,$ i.e.

$$\begin{eqnarray} f(x)\equiv 0\!\!\!\pmod{\!mn}&\overset{\rm CRT}\iff& \begin{array}{}f(x)\equiv 0\pmod{\! m}\\f(x)\equiv 0\pmod{\! n}\end{array} \\ &\iff& \begin{array}{}x\equiv r_1,\ldots,r_k\pmod {\!m}\phantom{I^{I^{I^I}}}\\x\equiv s_1,\ldots,s_\ell\pmod{\! n}\end{array}\\ &\iff& \left\{ \begin{array}{}x\equiv r_i\pmod{\! m}\\x\equiv s_j\pmod {\!n}\end{array} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}^{\phantom{I^{I^{I^I}}}}\\ &\overset{\rm CRT}\iff& \left\{ x\equiv t_{i j}\!\!\pmod{\!mn} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}\\ \end{eqnarray}\qquad\qquad$$

---

You can find many concrete worked examples of this isomorpism in prior posts, e.g. below

• $\,f(x) = (x\!+\!2)(x\!+\!3)\,$ and $\,m,n = 11,17$

• $f(x) = x(x-1)\,\ $ [idempotents]

• $x^2=1 \pmod{\!7},\ x^3=1\pmod{\! 9},\,$ generalization where $f$ depends on the modulus.

Answer 2

For the right to left case, since $p_1$ and $p_2$ are relatively prime, as Bill Dubuque's comment indicates, you can just use the Chinese remainder theorem to confirm there's a solution for $q \equiv r \pmod{p_1}$ and $q \equiv s \pmod{p_2}$. Alternatively, Bézout's identity states there exist integers $x_1$ and $y_1$ such that

$$x_1 p_1 + y_1 p_2 = 1 \tag{1}\label{eq1A}$$

Multiply both sides by $r - s$ and, for simpler algebra, set $x_2 = x_1(r - s)$ and $y_2 = y_1(r - s)$. This gives

$$\begin{equation}\begin{aligned} x_2 p_1 + y_2 p_2 & = r - s \\ s + x_2 p_1 & = r - y_2 p_2 \end{aligned}\end{equation}\tag{2}\label{eq2A}$$

Let $q = s + x_2 p_1 = r - y_2 p_2$. Thus, $q \equiv s \pmod{p_1} \implies q^k \equiv s^k \equiv a \pmod{p_1}$ and $q \equiv r \pmod{p_2} \implies q^k \equiv r^k \equiv a \pmod{p_2}$. Since $p_1$ and $p_2$ are coprime, this means

$$q^k \equiv a \pmod{p_1p_2} \tag{3}\label{eq3A}$$

For the left to right case, just choose $r = s = q$.

Answer 3

We use Euler's critrion to find r and s:

If $a \equiv t^2 \mod(p_1)$ then:

$a^{\frac{p_1-1}2} \equiv 1 \mod (p_1)$

So : $a^{\frac{p_1-1}{2}+1} \equiv a\mod(p_1)$

Suppose:

$\frac{p_1-1}{2}+1=\alpha \cdot \beta$

then $r$ can be $a^{\alpha}$ and $k= \beta$ and we have:

$r^k \equiv a \mod p_1$

Similarly suppose:

$\frac{p_2-1}{2}+1=\gamma \cdot \beta$

and $s=a^{\gamma}$ then $k=\beta$ and we have:

$s^k \equiv a \mod p_2$

provided $a \equiv m^2 \mod(p_2)$