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

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.

• It's not clear which parts are given and what you are supposed to prove. Nov 26, 2020 at 18:40
• (Based on what I'm guessing about the question) You need to find $r, s$ for all $k$. There are some natural/obvious tries for them. Given $q$, what are some suitable candidates for $r, s$? Nov 26, 2020 at 18:44
• If there exists an integer $q$ such that $q^k\equiv a(mod \:\:p_1p_2)$, then we need to prove that we can always find some integers $r,s$ such that $r^k \equiv a(\mod\:\:p_1)$ and $s^k\equiv a(mod\:\:p_2)$. Given $p_1$ is coprime to $p_2$. Nov 26, 2020 at 18:46
• @EkaveeraKumarSharma Use \pmod{x} to generate $\pmod{x}$ (note the spacing). Nov 26, 2020 at 19:10

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

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

• Above simply solves the congruence system $\,q \equiv s\pmod{\!p_1},\ q \equiv r\pmod{\!p_2}$ by applying a standard CRT method: scale the Bezout equation for the moduli gcd to get the residue difference, then rearrange Nov 26, 2020 at 21:52
• This method of lifting the CRT isomorphism to roots of polynomials works for any polynomial with integer coefs - see my answer. Nov 27, 2020 at 1:49
• Do we proceed the same way from left to right ? Nov 27, 2020 at 9:35
• @EkaveeraKumarSharma If your comment is addressed to me rather than Bill, then as my answer stated, going from left to right, if you have $q^k \equiv a \pmod{p_1p_2}$, then $q^k \equiv a \pmod{p_1}$ and $q^k \equiv a \pmod{p_2}$, so you can just simply choose $r$ and $s$ to both be equal $q$. If it's something else you're unsure of, please let me know specifically what it is. Nov 27, 2020 at 10:00
• @Ekaveera The inference in the prior comment is a special case of the fundamental fact that congruences persist mod factors of the modulus. It is essential to know well these basic properties of congruences in order to master congruence arithmetic (continued below) Nov 27, 2020 at 13:52

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