Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If $\gcd(a,b) = 1$, $x \equiv 0 \pmod{a}$, $x \equiv 0 \pmod{b}$ then prove that $x \equiv 0 \pmod{ab}$.

My attempt at answering the question:

\begin{align*} x &\equiv 0 \pmod{a}\\ &\Longrightarrow x\text{ is divisible by $a$}\\ &\Longrightarrow x = ma\text{ for some integer $m$}\\ \ \\ x &\equiv 0 \pmod{b}\\ &\Longrightarrow x\text{ is divisible by $b$}\\ &\Longrightarrow x = mb\text{ for some integer $m$}\\ \ \\ x^2 &= (ma)(mb)\\ x^2 &= (m^2)(ab)\\ x &= \sqrt{m^2ab}\\ x &= m\sqrt{a}\sqrt{b} \end{align*} Let $m$ be $k\sqrt{a}\sqrt{b}$. Then \begin{align*} x &= kab\\ &\Longrightarrow x \equiv 0 \pmod{ab} \end{align*}

Is this correct, if not can someone point me in the right direction?

share|cite|improve this question
You know that $x=ma$ for some $m$; and you know that $x=kb$ for some $k$. You do not know that $m=k$. So you cannot conclude that $x^2=m^2ab$ (which would imply that $ab$ is a square). – Arturo Magidin Dec 3 '10 at 15:50
up vote 7 down vote accepted

You are given that $a$ divides $x$. Therefore, you can write $x = ma$ where m is an integer. You are also given that $b$ divides $x$. This implies that $b$ divides $ma$. But $b$ and $a$ are coprime. Therefore $b$ must divide $m$. So you can write $m = kb$ where $k$ is another integer. Therfore, you have $x = kab$.

share|cite|improve this answer
Thanks a lot for your help, I can't believe I missed such a simple substitution for x, I was assuming the proof to be more complicated than it actually was. – fmunshi Oct 29 '10 at 5:06

gcd(a,b)=1 so there are integers s and t such that sa+tb=1, whence sax+tbx=x. But a divides x so x=ax' for some integer x'. As b divides x, x=bx" for some integer x". Substituting on the left-hand side of the preceding equation yields sabx"+tabx'=x. Factor out the commn ab on the left to get ab(ax"+tx")=x, so that ab divides x.

share|cite|improve this answer

Since $\rm\ \gcd(a,b) = 1\:,\ $ by Euclid's Lemma, $\rm\ \ a\:|\:b\:(x/b)\ \Rightarrow\ a\:|\:x/b\ \Rightarrow\ ab\:|\:x$

Alternatively $\rm\ \ b,a\:|\:x\ \Rightarrow\ ab\: |\: ax,bx\ \Rightarrow\ ab\ |\ gcd(ax,bx)\ =\ x\ gcd(a,b)\ =\ x $

This is the special case $\rm\ gcd(a,b) = 1\ $ of $\rm\ gcd(a,b)\ lcm(a,b)\ =\ ab\ $ which has a similar proof.

share|cite|improve this answer

No. This is not correct.
1. Integers $m_1$ and $m_2$ in $x=m_1 a$ and $x=m_2 b$ can be different.
2. In the beginning of your proof all numbers are integers. However when you write "let m be k*sqrt(a)*sqrt(b)", you don't know, that k is integer too.

Right direction: use, the fact, that each number $y$ can be uniquely represented as $p_1^{\alpha_1} p_2^{\alpha_2}\dots p_n^{\alpha_n}$, where $p_i$ are primes and $\alpha_i$ are integers.

share|cite|improve this answer
I've already understood the question from svenkatr's response, although I'm curious as to how you were suggesting to solve the problem, do you mind elaborating on your "right direction" section? – fmunshi Oct 29 '10 at 5:07

Your Answer


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.