1
$\begingroup$

Here is Prob. 15, Sec. 3, in the book Topics in Algebra by I.N. Herstein, 2nd edition:

If $(m, n) = 1$, given $a$ and $b$, prove that there exists an $x$ such that $x \equiv a \mod m$ and $x \equiv b \mod n$.

[ Here $(m, n)$ denotes the Greatest Common Divisor (GCD) of the positive integers $m$ and $n$. ]

My Attempt:

We note that there is an integer $x$ such that $x \equiv a \mod m$ and $x \equiv b \mod n$ if and only if we have $m | (x-a)$ and $n | (x-b)$, which is the case if and only if there are integers $p$ and $q$ such that $x-a = mp$ and $x-b =nq$, and hence $$ a + mp = b +nq, $$ which holds if and only if $$ mp - nq = b-a. \tag{1}$$

Now as $(m, n) = 1$, so by Lemma 1.3.1 in Herstein there exist integers $r$ and $s$ such that $$ mr + ns = 1, $$ and hence $$ mr(b-a) + ns(b-a) = b-a. \tag{2} $$

Comparing (1) and (2) above, we find that if we put $$ x \colon= a + mr(b-a) = b - ns(b-a), $$ then our desired conditions hold.

Is this proof correct? If so, is it rigorous enough for Herstein? If not, then where are the issues?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.