1
$\begingroup$

Yesterday, I attempted to solve the general system of linear congruences (I'm not sure why I've never tried this before.) \begin{align*} x &\equiv a \pmod{A} \\ x &\equiv b \pmod{B}.\end{align*} I let $x = a + pA$ and $x = b + qB$ for some $p,q\in\mathbb{Z}$, and I got $$a + pA = b + qB \implies a \equiv b + qB \pmod{A} \implies q \equiv(a - b)B^{-1}_A \pmod{A}.$$ where $B^{-1}_A$ is the inverse of $B$ modulo $A$. Then $q = (a - b)\cdot B_A^{-1} + rA$ for some $r\in\mathbb{Z}$, so $$ x = b + (a - b)B_A^{-1} B + rAB\implies x\equiv b + (a - b)B^{-1}_AB \pmod{AB}. $$ However, note that by symmetry, we can also conclude that $$ x \equiv a + (b - a)A^{-1}_BA \pmod{AB}.$$ Thus, $$ a + (b-a)A^{-1}_BA \equiv b + (a - b)B^{-1}_AB \pmod{AB}.$$ If $\gcd(a - b, AB) =1$, then $$a - b = (a - b)(BB^{-1}_A + AA_B^{-1}) \pmod{AB} \implies BB^{-1}_A + AA_B^{-1}\equiv 1 \pmod{AB}.$$ Can this result be generalized to product rings? Also, if there is a generalization, does it have any uses?

$\endgroup$
1
$\begingroup$

I always use your method to solve these equations, but your result is just the standard formula for the Chinese remainder theorem.

If $\gcd(a-b,AB) = 1$:

  $\gcd(qB-pA,AB) = \gcd((x-pA)-(x-qB),AB) = 1$.

  Thus $\gcd(A,B) = 1$ and hence $A_B^{-1},B_A^{-1}$ exist [which you already assumed].

[Note that the converse is clearly not true! $A,B$ could be coprime while $a,b$ are both zero.]

If $\gcd(A,B) = 1$:

  Thus $A \mid AA_B^{-1} + BB_A^{-1} - 1$ and $B \mid AA_B^{-1} + BB_A^{-1} - 1$.

  Thus $AB \mid AA_B^{-1} + BB_A^{-1} - 1$ and hence $AA_B^{-1} + BB_A^{-1} \equiv 1 \pmod{AB}$.

[So the result you got holds under the usual more general condition that $A,B$ are coprime.]

The chinese remainder theorem also holds for principal ideal domains in the way you want, namely product rings, and generalizes to the product of any coprime quotient rings of a commutative rings. (You can take a look at the Wikipedia article.)

$\endgroup$
0
$\begingroup$

That is a simple form of CRT = Chinese Remainder Theorem that I call Easy CRT. Below is one simple way to present it. You can find many example applications in prior posts here.

Theorem $ $ (Easy CRT) $\rm\ \ $ If $\rm\ m,\:n\:$ are coprime integers then

$$\rm \begin{eqnarray}\rm x&\equiv&\rm a\,\ (mod\ m) \\ \rm x&\equiv&\rm b\,\ (mod\ n)\end{eqnarray} \ \iff\ \ x\, \equiv\, a + m\ \bigg[\frac{b-a}{\color{#c00}m}\ mod\ n\:\bigg]\ \ (mod\ m\:n)$$

Proof $\rm\,\ m,n\,$ coprime $\:\rm\Rightarrow\, \color{#c00}{{\large\frac{1}m} = m^{-1}}\!\pmod n\, $ exists, by Bezout or Euler's $\phi$ Theorem.

$\rm\ (\Leftarrow)\ \ \ mod\ m:\,\ x \equiv a + m\left[\cdots\right] \equiv a,\ $ and $\rm\ mod\ n\!\!:\ x \equiv a + m\,\color{#c00}{\large\frac{1}m}\,(b-a) \equiv b$

$\rm (\Rightarrow)\ \ $ The solution is unique $\rm\, (mod\ m\,n)\, $ since if $\rm\ x',\,x\ $ are solutions then $\rm\ x'\equiv x\ $ mod $\rm\:m,n\:$ hence $\rm\ m,n\mid x'-x\ \Rightarrow\ m\,n\mid x'-x\ $ since $\rm\ m,\,n\:$ coprime $\rm\:\Rightarrow\ lcm(m,n) = m\,n$.

$\endgroup$
  • $\begingroup$ This is clear enough, though actually it didn't answer the original question (about generalization). Personally I would never write $\frac1m$ when in a non-field, but that's just pedagogical preference. $\endgroup$ – user21820 Jun 28 '16 at 0:33
  • $\begingroup$ @user21820 Algebraists and number theorists frequently use fractions in rings that are not fields, e.g. look up "localization". You can find many examples in my posts. When I teach elementary number theory I strive to introduce these ideas very early since they can lead to great simplifications. $\endgroup$ – Bill Dubuque Jun 28 '16 at 0:40
  • $\begingroup$ Yes I can see the advantage of the fraction notation. It's simply that students who don't have a solid grasp of logic tend to write things that make no sense, and sometimes conventional notation is unhelpful. For example I never write $\sin^2(x)$ for $\sin(x)^2$ because there's also $\sin^{-1}$. It is just a personal preference to keep notation as uniform across all areas of mathematics as possible. (Of course, one needs to also be able to pick up on the fly notation that other people use.) $\endgroup$ – user21820 Jun 28 '16 at 0:55
  • $\begingroup$ @user21820 Yes, certainly it needs a careful exposition to help students avoid pitfalls. $\endgroup$ – Bill Dubuque Jun 28 '16 at 0:58

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.