Cryptography Reference
In-Depth Information
Function:
least common multiple (lcm)
int lcm_l (CLINT a_l, CLINT b_l, CLINT c_l);
Syntax:
a_l, b_l
(operands)
Input:
c_l
(lcm)
Output:
E_CLINT_OK
if all ok
E_CLINT_OFL
if overflow
Return:
int
lcm_l (CLINT a_l, CLINT b_l, CLINT c_l)
{
CLINT g_l, junk_l;
if (EQZ_L (a_l) || EQZ_L (b_l))
{
SETZERO_L (c_l);
return E_CLINT_OK;
}
gcd_l (a_l, b_l, g_l);
div_l (a_l, g_l, g_l, junk_l);
return (mul_l (g_l, b_l, c_l));
}
It holds for the least common multiple as well that its calculation for more
than two arguments can be recursively reduced to the case of two arguments:
lcm (
n
1
,...,n
r
) = lcm (
n
1
,
lcm (
n
2
,...,n
r
))
.
(10.5)
Formula (10.4) above does not, however, hold for more than two numbers:
The simple fact that
lcm(2
,
2
,
2)
=2
3
can serve as a
counterexample. There does exist, however, a generalization of this relation
between the greatest common divisor and the least common multiple for more
than two arguments. Namely, we have
·
gcd(2
,
2
,
2) = 4
lcm(
a, b, c
)
·
gcd(
ab, ac, bc
)=
|abc|
(10.6)
and also
gcd(
a, b, c
)
·
lcm(
ab, ac, bc
)=
|abc|.
(10.7)
The special relationship between the greatest common divisor and the least
common multiple is expressed in additional interesting formulas, demonstrating
an underlying duality, in the sense that exchanging the roles of greatest common
divisor and least common multiple does not affect the validity of the formula, just
