# If $\gcd(a,b) = 1$ and $a,b\mid x$ then $ab\mid x$.

If $$\gcd(a,b) = 1$$ and $$a,b\mid x$$ then $$ab\mid x$$.

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). Dec 3, 2010 at 15:50

## 4 Answers

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. Oct 29, 2010 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 common $ab$ on the left to get $ab(ax''+tx'')=x$, so that $ab$ divides $x$.

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? Oct 29, 2010 at 5:07

Since $$\rm\ \color{#C00}{\gcd(a,b) = 1},\,$$ by Euclid's Lemma, $$\rm\ \ \color{#c00}{a\mid b}(x/b)\ \Rightarrow\ a\mid x/b\ \Rightarrow\ ab\mid x$$

Alternatively $$\rm\ \ b,a\:|\:x\ \Rightarrow\ ab\: |\: ax,bx\ \Rightarrow\ ab\ |\ gcd(ax,bx)\ =\ x\ \color{#c00}{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 which has an elegant view in terms of cofactor reflection.

See also the LCM Universal Property $$\ a,b\mid x\iff {\rm lcm}(a,b)\mid x$$

By induction this generalizes to

$$\qquad$$ if $$\,a_i\,$$ are pair-coprime then $$\, a_1,\cdots a_k\mid x\Rightarrow a_1\cdots a_k \mid x$$

i.e. lcm = product for pair coprimes (see also here)