5
$\begingroup$

There exists a $x \in \mathbb{Z}$ satisfying system of equations: $$x=a_1 \pmod {n_1}$$ $$x=a_2 \pmod {n_2}$$ $$\ldots$$ $$x=a_k \pmod{n_k}$$ if and only if $a_i=a_j \pmod{\gcd(n_i,n_j)}$ for all $i,j=1,...,k$?

Can anyone give me a proof by induction?

$\endgroup$
  • $\begingroup$ @Mathmo123 I've tried proving the base case but I can't even do that $\endgroup$ – user108605 Aug 28 '14 at 10:31
  • $\begingroup$ What did you try to do? Can you do it if $n_1, n_2$ are coprime? $\endgroup$ – Mathmo123 Aug 28 '14 at 10:33
  • $\begingroup$ @Mathmo123 yes. Could you give me like half the proof? $\endgroup$ – user108605 Aug 28 '14 at 10:34
8
$\begingroup$

This is (almost) a duplicate of an already asked question. No matter, the proof I am going to give
is different from the one provided there.

In order to make this answer self-contained we restate the assertion to be proved: $\renewcommand{\mod}[1]{~(\text{mod $#1$})} $$\newcommand{\congr}{\equiv} $$\newcommand{\ncongr}{\not\equiv} $$\newcommand{\lcm}{\mathop{\smash{\mathrm{lcm}}}\nolimits} $

Let $k$ be a positive integer, let $a_1$, $\ldots$, $a_k$ be integers and $n_1$, $\ldots$, $n_k$ positive integers. Then the system of congruences $$ \begin{aligned} x ~&\congr a_1\mod{n_1}\,,\\ x ~&\congr a_2\mod{n_2}\,,\\ &\qquad\cdots\\ x ~&\congr a_k\mod{n_k} \end{aligned} \tag{1} $$ is solvable if and only if $$ a_i\congr a_j\mod{\gcd(n_i,n_j)} \qquad \text{for all $~i,\,j=1,\,2,\,\ldots,\,k$}\,.\tag{2} $$ If the system of congruences $(1)$ has a solution $x_0$, then an integer $x$ is a solution of $(1)$ if and only if $x\congr x_0\mod{\lcm(n_1,\ldots,n_k)}$.

Proof. $~$Throughout the proof, everything in sight is assumed to be an integer.

We prove the last statement of the assertion first. Set $n:=\lcm(n_1,\ldots,n_k)$. If $x_0$ and $x$ are solutions of $(1)$, then $x-x_0$ is divisible by every $n_i$, thus it is divisible by $n$. Conversely, if $x_0$ is
a solution and $x\congr x_0\mod{n}$, then $x\congr x_0\congr a_i\mod{n_i}$ for every $i$.
$\qquad$In other words, if the system of congruences $(1)$ possesses a particular solution $x_0$, then the whole system is equivalent to the single congruence $x\congr x_0\mod{n}$.

We shall prove that the conditions $(2)$ are necessary and sufficient for solvability of the system $(1)$.

Necessity. $~$If $(1)$ has a solution $x$, then $a_i\congr x\congr a_j\mod{\gcd(n_i,n_j)}$ for all $i$, $j$.

Sufficiency. $~$We start the induction by considering the case $k=2$. Let $d:=\gcd(n_1,n_2)$, suppose that $a_1\congr a_2\mod{d}$, and set $b:=(a_2-a_1)/d$. We seek a solution of the two congruences $x\congr a_1\mod{n_1}$, $x\congr a_2\mod{n_2}$ in the form $x=a_1+dy$, so we have to find a solution of the system of two congruences $dy\congr 0\mod{n_1}$, $dy\congr a_2-a_1\mod{n_2}$, which is equivalent to the system $y\congr0\mod{n_1/d}$, $y\congr b\mod{n_2/d}$; the latter system is solvable by the Chinese Remainder Theorem because $n_1/d$ and $n_2/d$ are coprime.
$\qquad$Now let $k>2$ and assume that we already have the sufficiency for $k-1$ under our belt. Since $a_1\congr a_2\mod{\gcd(n_1,n_2)}$, there exists an integer $c$ so that $c\congr a_1\mod{n_1}$, $c\congr a_2\mod{n_2}$. The subsystem consisting of the first two congruences is equivalent to the single congruence $x\congr c\mod{m}$, where $m=\lcm(n_1,n_2)$. We claim that $c\congr a_j\mod{\gcd(m,n_j)}$ for every $j$, $2<j\leq k$. Indeed, from $c\congr a_1\congr a_j\mod{\gcd(n_1,n_j)}$ and $c\congr a_2\congr a_j\mod{\gcd(n_2,n_j)}$
it follows that $c\congr a_j\mod{\lcm(\gcd(n_1,n_j),\gcd(n_2,n_j))}$; but $\gcd$ distributes over $\lcm$, so we have $\lcm(\gcd(n_1,n_j),\gcd(n_2,n_j))=\gcd(\lcm(n_1,n_2),n_j)=\gcd(m,n_j)$. The system consisting of the congruence $x\congr c\mod{m}$ and the $k-2$ congruences $x\congr a_j\mod{n_j}$, $2<j\leq k$,
is solvable by induction hypothesis, and it is equivalent to the system of congruences $(1)$;
it follows that the system $(1)$ is solvable.$~$ Done.

Remarks. $~$The proof uses only the Chinese Remainder Theorem for a system of two congruences with coprime moduli. Using it we have proved, in particular, the general Chinese Remainder Theorem for any number of congruences with the pairwise coprime moduli; this proof is different from the staple proof of the Chinese Remainder Theorem in (most) textbooks.

We have assumed that all moduli are positive integers. It is simple (though instructive) to verify that the assertion remains true if we allow zero moduli. Mark that the congruence modulo $0$ is the equality, that is, $x\congr y\mod{0}$ means the same as $x=y$.

Let's recall, for completeness' sake, how a system $x\congr a\mod{m}$, $x\congr b\mod{n}$ with coprime
$m$ and $n$ is solved. There exist integers $m'$ and $n'$ such that $m'm+n'n=1$. Then $$ \begin{gathered} n'n\congr 1\mod{m}~,\quad n'n\congr 0\mod{n}~,\\ m'm\congr 0\mod{m}~,\quad m'm\congr 1\mod{n}~, \end{gathered} $$ and it follows that $x:=n'na+m'mb=a+m'm(b-a)$ is a solution; it is the unique solution modulo $\lcm(m,n)=mn$.
$\qquad$Now consider the system $x\congr a\mod{m}$, $x\congr b\mod{n}$, where $m$ and $n$ are not necessarily coprime and where $a\congr b\mod{d}$ with $d:=\gcd(m,n)$. There exist integers $m'$ and $n'$ so that $m'm+n'n=d$, that is, $m'\frac{m}{d} +n'\frac{n}{d}=1$. A glance at the first part of our proof tells us that the unique solution modulo $\lcm(m,n)=\frac{m}{d}n$ is given by $x:=a+m'\frac{m}{d}(b-a)$.

Our proof provides the outline of an algorithm which, given a system of congruences $(1)$, either returns a pair $(x_0,n)$ where $n=\lcm(a_1,\ldots,a_k)$ and $x_0$ is a solution of $(1)$, or reports that there is no solution. We run the algorithm as follows.
$\qquad$We first check whether the conditions $a_i\congr a_j\mod{\gcd(n_i,n_j)}$ are satisfied, computing the $\gcd$'s using the Euclidean GCD algorithm. If we come across a condition that is not satisfied, we report failure. If all checks come up green, we proceed to find a solution, in $k-1$ steps. At each step we replace the subsystem consisting of the first two congruences of the current system with an equivalent single congruence. To do this we need the extended GCD algorithm which, given positive integers $m$ and $n$, returns not only $d:=\gcd(m,n)$ but also some integers $m'$ and $n'$ satisfying $m'm+n'n=d\,$ $($where $0\leq m'<\frac{n}{d}$, or perhaps $|m'|\leq\frac{1}{2}\frac{n}{d}$$)$; Mathematica, for example, has the function ExtendedGCD to do this. We compute the least common multiples of pairs of moduli as $\lcm(m,n)=mn/{\gcd(m,n)}$. After the last step of the algorithm we hold in our hands a single congruence $x\congr x_0\mod{n}$, and return the pair $(x_0,n)$.
$\qquad$Note that the algorithm does its job without ever needing to find the prime factorization of an integer (which can be time consuming).
$\qquad$Note also that we can omit the initial checking of conditions $(2)$ and instead do the checking on the fly. At each step we consider the subsistem consisting of the first two congruences of the current system, say $x\congr a\mod{m}$ and $x\congr b\mod{n}$; if $a\not\congr b\mod{\gcd(m,n)}$, we report that the system is unsolvable, otherwise we replace the two congruences with a single congruence $x\congr c\mod{\lcm(m,n)}$.

$\endgroup$
2
$\begingroup$

I'll give you some hints for the inductive step (note that the base case is actually when k=1 and is trivial).

Let $d= \operatorname{gcd}(n_1, n_2)$.


Note that if $$x\equiv a_1 \pmod {n_1}\\x\equiv a_2 \pmod {n_2}$$ has a solution, then in particular the solution must satisfy both of $$x \equiv a_1 \pmod d\\x \equiv a_2 \pmod d$$ Can you use this to get the required condition on $a_1$ and $a_2$ modulo $d$?


Now suppose $a_1 \equiv a_2 \pmod d$. Then $a_2 = a_1 + md$ for some $m \in \mathbb Z$. Let $y = x-a_1$. Then your equations are equivalent to $$y = 0 \pmod {n_1}\\ y = md \pmod{n_2}$$

Let $z = \frac yd$. Then these equations are equivalent to $$z \equiv 0 \pmod {\frac{n_1}d}\\z\equiv m \pmod {\frac{n_2}d}$$

Can you use this and the Chinese Remainder Theorem to get a solution for $x$?

$\endgroup$

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.