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

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?

-
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

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

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

-

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.

-

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.

-
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