# Proof verification: ab = gcd(a,b)lcm(a,b) without use of prime factorization

I am trying to proof $ab = \gcd(a,b)\mathrm{lcm}(a,b)$.

The definition of $\mathrm{lcm}(a,b)$ is as follows:

$t$ is the lowest common multiple of $a$ and $b$ if it satisfies the following:

i) $a | t$ and $b | t$

ii) If $a | c$ and $b | c$, then $t | c$.

Similiarly for the $\gcd(a,b)$.

Here is my proof:

Case I: $\gcd(a,b)\neq 1$

Suppose $\gcd(a,b) = d$.

Then $ab = dq_1b = dbq_1 = d(dq_1q_2)$

Claim: $\mathrm{lcm}(a,b) = dq_1q_2$

$a = dq_1 | dq_1q_2$

$b = dq_2 | dq_2q_1$.

Supppose $\mathrm{lcm}(a,b) = c$. Hence $c \leq dq_1q_2$ .

To get the other inequality we have $dq_1 | a$ and $dq_2 | b$. Hence $dq_1 \leq a \leq c \leq dq_1q_2$ similarly for $dq_2$.

Suppose that c is strictly less than $dq_1q_2$, so we have $dq_1q_2 < cq_2$ and $dq_1q_2 < cq_1$.

So $dq_1q_2 < c < cq_2 < dq_2^2q_1$ and $dq_1q_2 < c < cq_2 < dq_1^2q_2$, but $dq_1^2q_2 > dq_1q_2$ so $c < dq_1q_2$ and

$c > dq_1q_2$ contradiction. Hence $c = dq_1q_2$

Notice that the case where $\gcd(a,b) = 1$ we can just set $q_1 = a$ and $q_2 = b$, and the proof will be the same.

• Simpler as below. See also here for a more conceptual way via (inversion) duality. $$a,b\mid m \iff ab\mid am,bm \iff ab\mid (am,bm)=(a,b)m \iff ab/(a,b)\mid m$$ – Bill Dubuque Jul 6 '16 at 21:06

I prefer to do a proof that avoids any explicit reference to ordering (so it will work in more general settings). Moreover, I want to use our fundamental relation that if $\gcd(a,b)=1$, then $1=am+bn$ for some $m,n$. In order to use your explicit definition of lcm, use this to write $t=amt+bnt$ and show that $ab$ satisfies the definition of lcm. Then reduce the general case to this.
Yes, except maybe first explicitly define $q_1$ and $q_2$, even though they are obvious. You can use $q_a$ and $q_b$ for more clarity.