2
$\begingroup$

I'm looking at the following problem:

Suppose $m$ and $n$ are coprime, odd positive integers. Prove that the system of congruences $$2x \equiv 1 \pmod m\\ 4x \equiv 1 \pmod n$$ has a solution.

I feel like I should be able to use the Chinese Remainder Theorem here somehow, but how do I bring the equations to a form $x \equiv b_1 \pmod {m_1}$ without knowing the multiplicative inverses of $2$ and $4$ modulo $n$?

Hope you can help.

$\endgroup$
1
$\begingroup$

The numbers $2$ and $4$ have inverses modulo $m$ and $n$ respectively, since $m$ and $n$ are odd.

If $a$ is the inverse of $2$ modulo $m$, and $b$ the inverse of $4$ modulo $n$, then our congruences are equivalent to $x\equiv a\pmod{m}$, $x\equiv b\pmod{n}$. Now we can use the CRT.

Remark: We do not have to know the inverses to show that they exist. However, the inverses are not hard to compute.

Since $m$ is odd, we have $m=2k+1$ for some $k$. Then $1\equiv 2k+2\pmod m$, and therefore $x\equiv k+1\pmod{m}$.

The situation for $4$ is somewhat more complicated. If $n$ is of the shape $4k+3$, then $1\equiv 4k+4\pmod{n}$, and therefore $x\equiv k+1\pmod{n}$.

If $n$ is of the shape $4k+1$, then $1\equiv -4k\pmod{n}$, and thefore $x\equiv -k\pmod{n}$.

$\endgroup$
  • $\begingroup$ Nice! Wonderful explanation. So using the CRT: Let $M=mn$, $M_m = n, M_n=m$. Then we need to solve the equations $M_i x_i \equiv 1$ mod $m_i$ for $i=m,n$. We get the two equations $$n x_m \equiv 1 \, \text{mod m}\\ m x_n \equiv 1 \, \text{mod n}.$$ Since $(m,n)=1$ each of these equations have exactly one incongruent solution modulo $m$ and modulo $n$ respectively. Let these solutions be $p$ and $q$. Then $x=anp+bmq$, correct? $\endgroup$ – Numbersandsoon Sep 23 '13 at 4:52
  • 1
    $\begingroup$ Yes, but you have essentially written out the full proof of CRT for the case of two congruences. In order to show there is a solution, which is all the problem asks for, all you need to do is to write something more or less equivalent to what I wrote in my answer (before the remark part). If you had been asked to give a good algorithm for producing a solution $x$, you would need to go into the kind of detail there is in your comment. But for existence of a solution, that is not necessary. $\endgroup$ – André Nicolas Sep 23 '13 at 5:14

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.