# $\gcd(m,n) = 1$ and $\gcd (mn,a)=1$ implies $a \cong 1 \pmod{ mn}$

I have $m$ and $n$ which are relatively prime to one another and $a$ is relatively prime to $mn$ and after alot of tinkering with my problem i came to this equality: $a \cong 1 \pmod m \cong 1 \pmod n$ why is it safe to say that $a \cong 1 \pmod {mn}$?..

-
fyi: having a good title makes things more easily searchable in the future. Doing this lets us minimize duplicate efforts. why not alter the title to something more appropriate such as $\gcd(m,n) = 1$ and $\gcd (mn,a)=1$ implies $a \cong 1 (mod mn)$ –  MSEoris Jan 31 '13 at 23:26
To add to what @MSEoris said, your title is a false statement, but the body of your post is true. –  Rick Decker Feb 1 '13 at 1:13
A useful reference, with a wider scope, is en.wikipedia.org/wiki/Chinese_remainder_theorem –  Andreas Caranti Feb 1 '13 at 7:30

It looks as if you are asking the following. Suppose that $m$ and $n$ are relatively prime. Show that if $a\equiv 1\pmod{m}$ and $a\equiv 1\pmod{n}$, then $a\equiv 1\pmod{mn}$.

So we know that $m$ divides $a-1$, and that $n$ divides $a-1$. We want to show that $mn$ divides $a-1$.

Let $a-1=mk$. Since $n$ divides $a-1$, it follows that $n$ divides $mk$. But $m$ and $n$ are relatively prime, and therefore $n$ divides $k$. so $k=nl$ for some $l$, and therefore $a-1=mnl$.

Remark: $1.$ There are many ways to show that if $m$ and $n$ are relatively prime, and $n$ divides $mk$, then $n$ divides $k$.

One of them is to use Bezout's Theorem: If $m$ and $n$ are relatively prime, there exist integers $x$ and $y$ such that $mx+ny=1$.

Multiply through by $k$. We get $mkx+nky=k$. By assumption, $n$ divides $mk$, so $n$ divides $mkx$. Clearly, $n$ divides $nky$. So $n$ divides $mkx+nky$, that is, $n$ divides $k$.

$2.$ Note that there was nothing special about $1$. Let $m$ and $n$ be relatively prime. If $a\equiv c\pmod{m}$ and $a\equiv c\pmod{n}$, then $a\equiv c\pmod{mn}$.

-
so easy! thanks I'm just really tired..keep on the good work! –  Rachel Bernoulli Jan 31 '13 at 23:31

$\gcd(m,n)=1$ implies there is an $x$ and $y$ so that $$mx+ny=1\tag{1}$$ $a\equiv1\pmod{m}$ and $a\equiv1\pmod{n}$ imply there is a $j$ and $k$ so that $$a-1=jm=kn\tag{2}$$ multiplying $(1)$ by $j$ and using $(2)$ $$nkx+jny=j\tag{3}$$ Plugging $(3)$ back into $(2)$ yields $$a-1=jm=n(kx+jy)m\tag{4}$$ which implies that $a\equiv1\pmod{mn}$.

Idea of the Preceding Argument

The idea of $(3)$ is to show that since $\gcd(m,n)=1$, by $(1)$, and $jm$ is a multiple of $n$, by $(2)$, we have that $j$ is a multiple of $n$. Thus, $a-1=jm$ is a multiple of $mn$, by $(4)$.

-
+1, since I'm a Darboux fan. –  Rick Decker Feb 1 '13 at 1:10
@Rick Probably you mean Bezout, not Darboux. In any case, you can see clearly the relation between the Bezout and gcd proofs in my answer. –  Math Gems Feb 1 '13 at 1:52
@MathGems. Gaah! Of course you're right. Bezout $\ne$ Darboux. (slinks away in embarassment) –  Rick Decker Feb 1 '13 at 1:54
@RickDecker: they both have 'b' and 'oo' sounds :-) –  robjohn Feb 1 '13 at 2:49
@Rob Darn Bezoukas! –  Math Gems Feb 1 '13 at 3:14

Hint $\rm\,\ \ m,n\,|\,a\!-\!1\!\iff\! lcm(m,n)\,|\,a\!-\!1\ \$ [proof below]

And, further, recall that $\rm\,\ lcm(m,n) = \dfrac{mn}{gcd(m,n)}\ [= mn\ \ if\ \ gcd(m,n)=1]$

Here's a proof of $\rm\ m,n\,|\,b\:\Rightarrow\:mn\,|\,bd,\ \ d = gcd(m,n) [= mx+ny\$ by Bezout]

$\rm\begin{eqnarray} \rm\quad m,n\,|\,b\:\Rightarrow\:mn\,|\,bm,bn &\Rightarrow&\,\rm mn\ |\ \,bmx\, +\, bny \ =\ b(mx\!+\!ny)\, = bd\quad [Bezout\ form] \\ \rm\quad\ \ m,n\,|\,b\:\Rightarrow\:mn\,|\,bm,bn &\Rightarrow&\,\rm mn\ |\ \gcd(bm, bn)\, =\: b \gcd(m,n) = bd\quad [GCD\ form] \\ \end{eqnarray}$

-