0
$\begingroup$

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$

3 Answers 3

0

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

  • 0
    Not uniquely: if x%3=0, then x%27 could be any of 0,3,6,...,24.2012-10-28
1

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

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

1

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

  • 0
    @robjohn You are of course right. I don't know what possessed me when I counted the congruences. Thank you.2012-10-28