# Chinese Remainder Theorem Modified

Suppose we have a set of n congruences of form $$X \equiv a1 \pmod p$$ $$X \equiv a2 \pmod q$$ $$X \equiv a3 \pmod r$$

where p, q, r are relatively prime. Let $$P = \Pi \hspace{5pt}p^aq^br^c$$

How can we calculate $$X \mod P$$

-

You can lift the original congruence into the form $$X \equiv a_1'\pmod {p^a}$$ where $a_1'$ belongs to the set of all residue classes such that $a_1' \equiv a_1 \pmod p$.

Do something similar for $q$ and $r$. Then applying the Chinese Remainder Theorem to $p^a,\ q^b$ and $r^c$ will give you the set of necessary results.

Note that there will be many solutions. In general we will have $p^{a-1}$ lifted congruence classes for the first congruence, $q^{b-1}$ for the second congruence and $r^{c-1}$ for the third. Each triplet will correspond to a unique solution giving a total of $p^{a-1}q^{b-1}r^{c-1}$ solutions modulo $P$.

-
Thanks for the help. Let's say we are given X % 3 = r(say) and I need to find X % 27. Is there any way to do it? – Aayush Bahuguna Oct 28 '12 at 8:20
Yes, it would be the set of congruence classes $$\left\{r,\ r+3,\ r+6,\ \cdots,\ r+24\right\}$$ – EuYu Oct 28 '12 at 8:22
With X given is it possible to find which congruence class X % 27 will belong? – Aayush Bahuguna Oct 28 '12 at 8:25
Like I said, the solution is not unique. Suppose $X \equiv 2 \pmod 3$ then we cannot uniquely specify $X \pmod{27}$. All we can say is that $X$ will belong to one of the congruence classes $$X\in\left\{2,\ 5,\ 8,\ \cdots,\ 23,\ 26\right\}$$ – EuYu Oct 28 '12 at 8:27
Wouldn't it be $p^{a-1}q^{b-1}r^{c-1}$ lifted congruences? For example, if we know $x\bmod{2}$ there are $2^{4-1}=8$ possible values of $y\bmod{2^4}$ so that $x\equiv y\pmod{2}$, not $2^{4-2}(2-1)+1=5$. – robjohn Oct 28 '12 at 8:51

I do not think we can if $a,b,c\ge 2$.

Suppose $X\equiv 1\pmod{4}$. Can we find $X\pmod{16}$?

-

If that is all you know, and $a>1$, $b>1$ or $c>1$, then you can't.

-
Thanks for the help. Suppose you are given X % p is there a way to calculate X % p^a? For e.g. suppose we are given X % 3 and I need to find X % 27. Is there any way to do it? – Aayush Bahuguna Oct 28 '12 at 8:04
Not uniquely: if x%3=0, then x%27 could be any of 0,3,6,...,24. – Douglas S. Stones Oct 28 '12 at 8:49