system of congruences proof

Question

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.

Answer 1

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

Answer 2

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