8
$\begingroup$

The greatest common divisor (gcd) of two integers $a$ and $b$ can be computed with the Euclidean Algorithm.

With the gcd known, one can compute the least common multiple (lcm) via the formula $\mathrm{lcm}(a,b) = \frac{|ab|}{\gcd(a,b)}$. One can also compute the lcm directly using the prime factorization. But there is (as far as I know) no algorithm similar to the Euclidean algorithm that computes the lcm directly (without computing the gcd first).

My question is:
Why?

Is there any conceptual reason why there is an algorithm for computing the gcd but no algorithm for computing the lcm?

EDIT: As Prem's answer shows, there is an algorithm similar to the Euclidean Algorithm, but this algorithm has higher complexity. So the question is rather: Is there an algorithm with same complexity as the Euclidean algorithm, and if no, why?

$\endgroup$
2
  • 1
    $\begingroup$ Would you be okay with an algorithm that computes LCM and GCD simultaneously in the style of Euclidean? $\endgroup$ Commented Nov 27 at 16:01
  • 1
    $\begingroup$ I guess that depends on what exactly "simultaneously" means. If the algorithm computes both the lcm and the gcd, but the gcd is not used for the computation of the lcm, that would be ok for me $\endgroup$ Commented 22 hours ago

3 Answers 3

Reset to default
4
$\begingroup$

Here is the Algorithm for LCM , without calculating GCD :

Let us be given two numbers $A,B$ , we want to know the LCM.

If :
$A=B$ , LCM is $A$.
Else :
Compare the Smaller ( say $S=A$ ) with the Larger ( $L=B$ ) , If not Equal , keep adding $A$ to the Smaller $S=S+A$.
If (when) that exceeds $L$ , then add $B$ to the Larger $L=L+B$
Continue until both are Equal : $S=L$
LCM is that number.

Example 1 :

LCM of $3,5$ :
$S=3,L=5$
$S=3+3=6,L=5$
$S=3+3=6,L=5+5=10$
$S=3+3+3=9,L=5+5=10$
$S=3+3+3+3=12,L=5+5=10$
$S=3+3+3+3=12,L=5+5+5=15$
$S=3+3+3+3+3=15,L=5+5+5=15$
LCM is $15$

Example 2 :

LCM of $6,14$ :
$S=6,L=14$
$S=6+6=12,L=14$
$S=6+6+6=18,L=14$
$S=6+6+6=18,L=14+14=28$
$S=6+6+6+6=24,L=14+14=28$
$S=6+6+6+6+6=30,L=14+14=28$
$S=6+6+6+6+6=30,L=14+14+14=42$
$S=6+6+6+6+6+6=36,L=14+14+14=42$
$S=6+6+6+6+6+6+6=42,L=14+14+14=42$
LCM is $42$

ADDENDUM :

There are ways to optimize this Intuitive Algorithm , Eg (A) By using Integer Division to calculate how many times to add together (B) Solving $xA-yB=0$ (C) Taking advantage of Modulo Arithmetic.
(D) The "most Optimal way" to make it Equivalent to Euclidean Algorithm [ in terms of Complexity ] would be to use $GCD$ itself , though OP wants to avoid that.

$\endgroup$
11
  • $\begingroup$ Isn't it simpler just to forget about $L$ and update $S$, stopping when $S$ is a multiple of $B$? Or you really want to avoid division? $\endgroup$ Commented Nov 27 at 14:49
  • $\begingroup$ I don't think this counts as an equivalent algorithm. Try running this with $a = 2$, $b = 2^k + 1$ for $k \approx 4000$. $\endgroup$ Commented Nov 27 at 15:28
  • 4
    $\begingroup$ Or worse, try $n$ and $n-1$ for a large number $n$. The problem is not the fact that in this algorithm $A$ or $B$ is added once at a time instead of some multiple of it, as that can be easily fixed. It is that the numbers being added remain $A$ and $B$, and are not adjusted in the later steps in some way like in the Euclidean algorithm. I think this means this algorithm is order $O(n)$ instead of $O(\log(n))$. $\endgroup$ Commented Nov 27 at 15:45
  • 1
    $\begingroup$ The now-removed word "Equivalent" was not used by OP , who actually just wanted some thing "Similar" to Euclidean Algorithm , @DanielV , I introduced that word unnecessarily. $\endgroup$ Commented Nov 27 at 21:29
  • 1
    $\begingroup$ Thanks for the answer. As pointed out, this algorithm is similar to the Euclidean Algorithm (as I asked) but has not the same order when compared to the Euclidean Algorithm. So my question should better be phrased as: Is there an anlgorithm with same complexity, and if not, why? (edited the question) $\endgroup$ Commented 22 hours ago
1
$\begingroup$

This may or may not satisfy your request. It is a way to compute GCD, LCM, and Modular Multiplicative Inverses at the same time using the Euclidean Algorithm.

Bill Dubuque has shared this approach.

The basic idea is, the usual Euclidean algorithm works by iterating:

a' = b
b' = a mod b

If you replace a,b with Bézout equations, you get the Extended Algorithm:

a = 450
b = 105

(e1)   1a + 0b  = 450     Start with
(e2)   0a + 1b  = 105     Start with
(e3)   1a - 4b  =  30     e3 = e1 - 4*e2
(e4)  -3a + 13b =  15     e4 = e2 - 3*e3
(e5)   7a - 30b =   0     e5 = e3 - 2*e4

The last line, $7a = 30b$ is the statement of the LCM. That is, $\rm{LCM} = 7 \cdot 450 = 30 \cdot 105$. And you don't know that the $15$ is the GCD in the 2nd to last line, until after the statement of the LCM is made in the final line.

And if the GCD is 1, then the coefficients of the 2nd to last line are the modular inverses.

$\endgroup$
0
$\begingroup$

Multiply the two numbers together. Go through the numbers one by one to find factors of it. Check each factor if divides one or the other of the original numbers discard for the original number and keep track. If it divides both disgard both but only keep track of one.

Ex.

to find LCM of $18$ and $75$. First $18\times 75=1350$.

$18, 75: 1350$. Is divisible by $2$ but $2$ only divides $18$.

$\frac {18}2=9, 75: 2,\frac {1350}2=675$. $675$ is divisible by $3$ and $3$ divides both $9$ and $75$. So divide out the $3$ from $9, 75$ and and from $675$ twice but only count it once.

$\frac 93=3, \frac {75}3=25: 2\times 3=6,\frac {675}{3^2}=75$. $75$ is divisible by $3$ but $3$ only divides $3$.

$\frac 33=1,25: 3\times 6=18, \frac {75}3 = 25$. $25$ is divisible by $5$ and $5$ again.

$1, 5: 90, 5$

$1,1: 450, 1$

So LCM of $18$ and $75$ is $450$.

....

Maybe a longer example $120, 252$

$120, 252: 30240$

$60, 126: 2, \frac {30240}{2^2}= 7560$

$30, 63: 4, \frac {7560}{2^2} = 1890$

$15, 63: 8, \frac {1890}{2} = 945$

$5,21: 24, \frac {945}{3^2}= 105$

$5,7: 72, \frac{105}3 = 35$

$1,7: 360, \frac {35}5=7$

$1,1: 2520,\frac 77=1$.

So LCM of $120, 252 = 2520$

$\endgroup$
1
  • $\begingroup$ Not an answer OP seeks efficient algorithms ("same complexity as Euclidean algorithm") but this answer requires integer factorization, for which no such efficient algorithms are known. You are essentially using the LCM Distributive Law $\,[ab,ac] = a[b,c].\,$ But this is of no help w/o knowing some common factor $\,a.\,$ Of course we can use their gcd $\,d=(a,b)\,$ as common factor: $\,[a,b] = d[a/d,b/d] = d(a/d)b/d = ab/d,\,$ but the OP prohibits use of gcds. $\ \ $ $\endgroup$ Commented 16 hours ago

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.