0
$\begingroup$

When dividing an integer $a$ by 3 and 7 both results in an integer answer, I intuitively feel that $a/A$ with $A=21$ would also be integer, which seems related to the fact that $3\times7=21$.

However, for an integer $b$ that divided by 4 and 6 would result in an integer answer it seems to be that $b/A$ with $A=12$ is integer as well.

My question is: is there a way to determine $A$ based on a multiplication of the two known integer divisions?

From the two examples that I gave I can think of this $A=\frac{x\times y}{gcd(x,y)}$, where $x$ and $y$ are the two numbers that result in integer answers. But I don't have a solid reason to believe this is generally true.

$\endgroup$
1
$\begingroup$

You're right. $A = \frac{a\times b}{gcd(a,b)}$

This is usually known as Least common multiple or lowest common multiple.

$\endgroup$
1
$\begingroup$

By Bezout's Identity $ $ for the gcd: $\,\ ja+kb \ =\ (a,b)\,$ for some $\,j,k,\in\Bbb Z.\,$ Therefore

$\phantom{\rm or}\ \ \ a,b\mid c\,\Rightarrow\, ab\mid ac,bc\,\Rightarrow\, ab\mid jac+kbc=(a,b)c\,\Rightarrow\,ab/(a,b)\mid c $

${\rm or}\ \ \ a,b\mid c\,\Rightarrow\, ab\mid ac,bc\,\color{#c00}\Rightarrow\, ab\mid\ (ac,\,bc)\ =\ (a,b)c\,\Rightarrow\,ab/(a,b)\mid c $

Proof $\,2\,$ uses the GCD universal property $\,j\mid k,n\!\color{#c00}\iff\! j\mid (k,n),\,$ and, furthermore, it replaces the Bezout Identity by the GCD Distributive Law.

The arrows reverse, which shows $\ {\rm lcm}(a,b) = ab/\gcd(a,b)=\,$ least common multiple of $\,a,b.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.