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

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.