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
    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?2012-10-28
  • 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
    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?2012-10-28
  • 0
    Yes, it would be the set of congruence classes $$\left\{r,\ r+3,\ r+6,\ \cdots,\ r+24\right\}$$2012-10-28
  • 0
    With X given is it possible to find which congruence class X % 27 will belong?2012-10-28
  • 0
    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\}$$2012-10-28
  • 0
    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$.2012-10-28
  • 0
    @robjohn You are of course right. I don't know what possessed me when I counted the congruences. Thank you.2012-10-28