3
$\begingroup$

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?

  • 0
    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).2010-12-03

4 Answers 4

9

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

  • 0
    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.2010-10-29
3

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

2

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.

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

1

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.

  • 0
    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?2010-10-29