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.

  • 0
    I tried $\TeX$-ing up your question, but I'm not sure what those U's in 2. are...2011-08-12
  • 0
    Hint: the remainder must be Chinese...2011-08-12
  • 1
    @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](http://en.wikipedia.org/wiki/Chinese_remainder_theorem#A_constructive_algorithm_to_find_the_solution) for solving congruence systems?2011-08-12
  • 0
    Thank you so much for editing in LATEX2011-08-15

1 Answers 1

1

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.

  • 0
    You are very correct. But, I need the proof for part 2 and 3 of my questions. Then I will discuss the important facts.2011-08-13
  • 0
    I mean, more clearly I nedd proofs of my posted questions, which will helpful me to think/develop the facts (which I got).2011-08-13
  • 0
    Really good. can you see my recent post, which I add to my previous post by editing.2011-08-13
  • 0
    I am waiting for a proper proof from GERRY MYERSON2011-08-14
  • 0
    Instead of adding on to this question (when does that process stop?), why not start a new question?2011-08-14
  • 0
    No Sir, your solution is really helpful to me for further developments. I hope, you can look once again for new post on the same question.2011-08-14
  • 0
    I looked, but didn't see any new post by you.2011-08-15
  • 0
    I have given more details under the bold letter EDIT. Also, there is a question under "Now I want the following". See my question under three questions and give me the proof for EDIT.2011-08-15
  • 0
    I want a proper proof for the new EDIT one. So that, I can discuss my new ideas in this part.2011-08-15
  • 0
    WHY DON'T YOU START A NEW QUESTION INSTEAD OF ADDING ON TO THIS QUESTION? m.se is not a place for discussing your new ideas, and even if it were you could do that just as well in a new question as in this one.2011-08-15
  • 0
    If this question is completely answered, I think I need not to ask the same question again on the next NEW QUESTION area.2011-08-15