Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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

3 Answers 3

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

share|improve this answer
    
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)$.

share|improve this answer
    
+1, since I'm a Darboux fan. –  Rick Decker Feb 1 '13 at 1:10
1  
@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
1  
@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}$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.