Sunday, November 1, 2015

elementary number theory - Prove $a mid m$ and $b mid m implies frac{a cdot b}{text{gcd}(a, b)} mid m$



I'm stuck at proving:





Let $a, b, c \in \mathbb{Z}, a\cdot b \neq 0$. Prove:
$$
a \mid m \hspace{15px}\text{and}\hspace{15px} b \mid m \implies \frac{a \cdot b}{\text{gcd}(a, b)} \mid m
$$




My current attempt looks like this:




Let $t := \text{gcd}(a, b)$ donate the greatest common divisor of $a$ and $b$.



$$
\implies\exists\, a', b': a = t\cdot a' \hspace{15px}\text{and}\hspace{15px} b = t \cdot b'
$$



$$
\implies \frac{a b}{\text{gcd}(a, b)} = \frac{a b}{t} = \frac{t a'b}{t} = a' b
$$




I know that since b \mid m: $a'b \mid m$ iff $\text{gcd}(a', b) = 1$ and $a' \mid m$, but I'm not sure whether this is the right approach to this problem.



Currently I don't know about identities involving the least common multiple.


Answer



By Bézout's lemma, there are integers $k$ and $l$ such that $\gcd(a,b)=ka+lb$. Therefore, $\gcd(a,b)m=kam+lbm$. Since $a\mid m$, $ab\mid lbm$ and since $b\mid m$, $ab\mid kam$. So, $ab\mid kam+lbm=\gcd(a,b)m$ and, since $\gcd(a,b)\mid ab$,$$ab\mid\gcd(a,b)m\iff\frac{ab}{\gcd(a,b)}\mid m.$$


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...