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?


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.