# system of congruences proof

I've checked a lot of the congruency posts and haven't seen this one yet, so I'm going to ask it. If there is a related one, I'd be happy to see it.

Let $x \equiv r\pmod{m}, x \equiv s\pmod{(m+1)}$. Prove $$x \equiv r(m+1)-sm \pmod{m(m+1)}$$ So with the given conditions, we know $$x=mk_1+r$$ Then $mk_1+r \equiv s\pmod{(m+1)} \Rightarrow mk_1 \equiv s-r\pmod{(m+1)}$

This is where I get stuck. I need to isolate the $k_1$ I think all the variables are messing with my mind. If I look at some numbers, say $r=1, m=6, s=2,$, then $$6k_1 \equiv 1\pmod{7}$$ Multiplying both sides by 6 (since $a\equiv b\pmod{n} \text{ implies } ac\equiv bc\pmod{n})$ i get $$36k_1 \equiv 6\pmod{7}$$ $$k_1 \equiv 6\pmod{7}$$ But how do I do this with $m$? I picked $6$ because I know $36=35+1=7\cdot5+1$ Does that mean that if I multiply both sides by $m$ $$m^2=(m^2-1)+1=(m+1)(m-1)+1$$ My other problem is the $r$ and $s$...so if I multiply by $m$ $$m^2=[m^2-(s-r)]+(s-r)$$ But this is not what I want, I need a factor to be $(m+1)$. Any help here would be appreciated.

• Do you know the Chinese Remainder Theorem? (I see it's in the tags but I'm not sure, since it's pretty straightforward if you know it.) Jan 8, 2014 at 3:01
• I'm currently learning it. I know that it tells us there is a unique solution since (m,m+1)=1 so my solution is modulo m(m+1). I just can't get passed isolating the $k_1$ and writing it in terms of another integer $k_2$... Jan 8, 2014 at 3:04
• Are you trying to verify said solution, or are you trying to discover that solution yourself? (with CRT or otherwise?) Jan 8, 2014 at 3:09
• verify...can't get passed the $mk_1=...$ step half way down the question. Jan 8, 2014 at 3:11
• Do it like this: mod $m\!:,\ m\equiv 0\,$ so $r(m+1)-sm \equiv r(0+1)-s(0) \equiv r$. Do the same mod $\,m+1\,$ using $\,m\equiv -1,.$ i.e. $\,r(m+1)-sm \equiv r(-1+1)-s(-1)\equiv s.$ Jan 8, 2014 at 3:17

## 2 Answers

EDIT: I assume that the problem is to check the solution, not discover it.

The CRT says that since $m$ and $m+1$ are relatively prime, the system $$\left\{\begin{array}{l} x \equiv r \pmod m \\ x \equiv s \pmod{m+1} \end{array}\right.$$ has a unique solution modulo $m(m+1)$. It is then easy to verify that $x \equiv r(m+1)-sm \pmod{m(m+1)}$ is such a solution, and since it is the only one, the given implication follows.

$r(m+1)-sm$ is obviously congruent to $r(m+1)$ mod $m$, and since of course $m+1$ is congruent to $1$, you obtain finally that $r(m+1)-sm \equiv r \pmod m$. Checking that $r(m+1)-sm \equiv s \pmod{m+1}$ is done similarly.

If you want to write $r(m+1)-sm = r+km$ explicitly, just expand: $$r(m+1)-sm = rm+r-sm = r+(r-s)m,$$ and likewise $$r(m+1)-sm = r(m+1)-s(m+1-1) = r(m+1)-s(m+1)+s = s+(r-s)(m+1).$$

• Nice. This was very helpful. I thought the "bulldoze through" technique would work, but finesse is better here. Thanks. Jan 8, 2014 at 3:24
• One problem you have is that you can't obtain the answer from $x \equiv r \pmod m$ alone, you need to take both hypotheses into account, and it gets very messy when you try to do it like that. Jan 8, 2014 at 3:27
• yeah, it seemed that way. I was using numerical examples as a guide as opposed to looking at what it means to be congruent modulo m, modulo m+1 with the given variables. Makes much more sense now. Jan 8, 2014 at 3:30

You seek to verify the claimed solution, but it is proving difficult because it seems that you may not yet have much practice with modular arithmetic calculation. Such calculations generally proceed using the congruence product and sum rules (below) to replace arguments of sums and products by smallest congruent numbers $\ge 0$, then computing the operation (sum or product), then reducing the result (replace with smallest congruent number $\ge 0).$ One performs this calculation and simplification process recursively on expressions composed of nested sum and product operations (in whatever order proves convenient). In the example at hand, this process amounts simply to replacing $\,m\,$ by $\:\color{#c00}0\:$ or $\,\color{#0a0}{-1}\,$ then simplifying the result, namely

$\quad{\rm mod}\,\ m\!:\,\quad\ \ \color{#c00}{m\ \equiv\, \ 0\ }\ \Rightarrow\ x = r(\color{#c00}m\!+\!1)-s\color{#c00}m \,\equiv\, r(\ \color{#c00}0\ +\ 1)\ -\ s( \color{#c00}0)\ \equiv\, r$

$\quad{\rm mod}\,\ m\!+\!1\!:\,\ \color{#0a0}{m\equiv -1}\ \Rightarrow\ x = r(\color{#0a0}m\!+\!1)-s\color{#0a0}m \,\equiv\, r(\color{#0a0}{-1}+1)-s(\color{#0a0}{-1})\equiv\, s$

Below are proofs of said congruence rules. They state, essentially, that the equivalence relation of congruence is compatible with the (ring) operations '$+$' and '$*$'), i.e. the result of the operation does not depend upon which equivalence class representatives one chooses for its arguments.

Congruence Sum Rule $\rm\qquad\quad A\equiv a,\quad B\equiv b\ \Rightarrow\ \color{#0a0}{A+B\,\equiv\, a+b}\ \ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a) + (B\!-\!b)\ =\ \color{#0a0}{A+B - (a+b)}$

Congruence Product Rule $\rm\quad\ A\equiv a,\ \ and \ \ B\equiv b\ \Rightarrow\ \color{#c00}{AB\equiv ab}\ \ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a)\ B + a\ (B\!-\!b)\ =\ \color{#c00}{AB - ab}$

Congruence Power Rule $\rm\quad\ A\equiv a\ \Rightarrow\ A^n\equiv a^n\ \ (mod\ m)$

Proof $\$ It is true for $\rm\,n=1\,$ and $\rm\,A\equiv a,\ A^n\equiv a^n \Rightarrow\, A^{n+1}\equiv a^{n+1},\,$ by the Product Rule, so the result follows by induction on $\,n.$

Beware  that such rules need not hold true for other operations, e.g. the exponential analog of above $\rm A^B\equiv a^b$ is not generally true (unless $\rm B = b,\,$ so it reduces to the Power Rule, so follows by inductively applying $\,\rm b\,$ times the Product Rule).