# Prove $2x \equiv 1 \pmod m$, $x \equiv 1 \pmod n$ has a solution

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.

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}$.

• 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? – Numbersandsoon Sep 23 '13 at 4:52
• 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. – André Nicolas Sep 23 '13 at 5:14