Wednesday, August 22, 2018

elementary number theory - Generalization of a Result on Modular Inverses



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?



Answer



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



No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...