3
$\begingroup$

I want to establish an efficient method to solve linear congruences to prove the Chinese Remainder Theorem. I need a proper generalization/proof for the following ones to go to further developments.

  1. If $a$ and $b$ are integers, then $a \bmod b = {a, a-b, a+b, a-2b, a+ 2b,...}$

  2. Let $a_1, a_2, ... , a_n, b$ are integers, then $[a_1, a_2,...,a_n] \bmod b = (a_1 \bmod b) \cup (a_2 \bmod b ) \cup ... \cup (a_n \bmod b)$.

  3. Let $a$, $b$ and $c$ are integers with $c > 0$ then prove that $a \bmod b = [a, a+b,\dots, a+(c-1)b] \bmod cb$.

EDIT:

Generally, we can express 1 mod 2 in terms of modulo 8. From this we can make $1 \pmod 2 = [1, 3, 5, 7] \pmod 8$. I mean factor of 4. which is same as $[a, a+b, ..., a+ (c-1)b] \pmod{bc}$. Symbolically, $$a \pmod b = \cup_{k = 0}^{c-1} [(a -b) + kb] \pmod {bc}$$ Now the question is, in CRT (Chinese Reminder Theorem), $$x = a_1 \pmod{b_1},\, x = a_2 \pmod {b_2},\dots,\, x = a_n \pmod {b_n}$$ where $0 \le a_j \lt b_j$ and the $b_j$'s are pairwise relative primes. I think, we can rewrite the $j$th congruence by the factor $1/b_j \prod b_k = c_k$ (where the product is running from $k = 1$ to $n$). Then $b_j c_j = C = \prod b_k$ (where the product is running from $k = 1$ to $n$).

Finally we can see the $$x_j = \cup_{m = 1}^{c_j} [(a_j - b_j) + b_j m] \pmod C$$ Now I want to know the following How to prove the following by using the above information. The system of congruences (in CRT), has a solution set with $b_j$'s are relatively primes is: $$x = \cap_{j = 1}^n[\cup_{m =1}^{c_j} [(a_j -b_j) + b_j m)]\pmod C$$ where $c_j = C/b_j$ and $C = \prod_{k = 1}^n b_k$ and the intersection contains only one residue class.

$\endgroup$
4
  • $\begingroup$ I tried $\TeX$-ing up your question, but I'm not sure what those U's in 2. are... $\endgroup$ Aug 12, 2011 at 5:12
  • $\begingroup$ Hint: the remainder must be Chinese... $\endgroup$
    – gary
    Aug 12, 2011 at 5:32
  • 1
    $\begingroup$ @J.M.: Gandhi means to do set union on the elements of the equivalence classes, I think that's pretty clear. OP, did you know Wikipedia elaborates on a constructive algorithm for solving congruence systems? $\endgroup$
    – anon
    Aug 12, 2011 at 5:39
  • $\begingroup$ Thank you so much for editing in LATEX $\endgroup$
    – Gandhi
    Aug 15, 2011 at 8:34

1 Answer 1

1
$\begingroup$

Here's a start. I take it by "$a\mod b$" you mean the set of all integers $x$ such that $x\equiv a\pmod b$. By the definition of $x\equiv a\pmod b$, that's the set of all $x$ such that $x-a$ is a multiple of $b$. That is, the set of all $x$ such that $x-a$ is in $\lbrace\, 0,b,-b,2b,-2b,\dots\,\rbrace$. That is, the set of all $x$ in $\lbrace\, a,a+b,a-b,a+2b,a-2b,\dots\,\rbrace$, which is what you want (if I understand your rather non-standard notation).

EDIT: The trouble with the second question is that I don't know what you mean by $[a_1,a_2,\dots,a_n]$. For the 3rd question, I'll interpret it as asking for a proof that the class $a\pmod b$ is the union of the classes $a+tb\pmod{cb}$, $t=0,1,\dots,c-1$.

First note that if $x\equiv a+tb\pmod{cb}$ then $x-a-tb$ is a multiple of $cb$, so it's a multiple of $b$, so $x-a$ is a multiple of $b$ (since $tb$ is a multiple of $b$), so $x\equiv a\pmod b$. Thus we have proved that the union of the classes $a+tb\pmod{cb}$, $t=0,1,\dots,c-1$ is contained in the class $a\pmod b$.

Now suppose $x\equiv a\pmod b$. Then $x-a=bw$ for some integer $w$. We can divide $w$ by $c$; the division theorem says $w=cq+r$ for some integers $q$ and $r$ with $0\le r\lt c$. So $x-a=bw=b(cq+r)$, so $x-a-br=bcq$, so $x\equiv a+br\pmod{cb}$. So, everything in the class $a\pmod b$ is in one of the classes $a+tb\pmod{cb}$, and we're done.

$\endgroup$
11
  • $\begingroup$ You are very correct. But, I need the proof for part 2 and 3 of my questions. Then I will discuss the important facts. $\endgroup$
    – Gandhi
    Aug 13, 2011 at 4:42
  • $\begingroup$ I mean, more clearly I nedd proofs of my posted questions, which will helpful me to think/develop the facts (which I got). $\endgroup$
    – Gandhi
    Aug 13, 2011 at 5:06
  • $\begingroup$ Really good. can you see my recent post, which I add to my previous post by editing. $\endgroup$
    – Gandhi
    Aug 13, 2011 at 17:31
  • $\begingroup$ I am waiting for a proper proof from GERRY MYERSON $\endgroup$
    – Gandhi
    Aug 14, 2011 at 8:18
  • $\begingroup$ Instead of adding on to this question (when does that process stop?), why not start a new question? $\endgroup$ Aug 14, 2011 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.