# Least Common Multiple and Greatest Common Factor

Whether or not you are likely to need to determine these values on your web page will depend on what topic your web site covers. If your site does anything involving numbers then there is at least a possibility that at some point you may need to calculate one or both of these values. These may even turn up in places you wouldn't expect. For example they are used with asymmetric key encryptions.

To make sure we know what we are talking about let's briefly consider just what the LCM and GCF are.

The greatest common factor of two numbers is the largest number that will divide exactly into both of the numbers. To use a simple example, if the two numbers are 12 and 9 then the largest number that will divide into both is 3 and so that is the greatest common factor. If the two numbers were 7 and 11 then the largest number that divides into both is 1. Note that in each case we are dealing with integers and division where there is no remainder.

The least common multiple is the smallest number that is divisible by both the supplied numbers. Again to use a simple example, if the two numbers are 12 and 9 then the smallest number divisible by both is 36.

These two concepts are inter-related which is why I am dealing with both in the same article. The simplest way to determine the LCM of two numbers is to first determine the GCF.

Finding the GCF of two numbers is going to involve some recursion. If we divide the first number by the second and get a remainder of 0 then the second number is the GCF as the second divides into the first. If it doesn't then do the test again substitution the second number for the first and the remainder for the second. This ensures that after the first test the second number is always smaller than the first so that our recursion will eventually terminate when the second number reaches 0 at which time the first number will be the GCF.

Here's the JavaScript code to do this:

``function gcf(a, b) {return (b === 0) ? a : gcf(b, a % b);}``

Note that this code works because the non-zero remainder is the biggest number that still has a possibility of being the GCF of the original two numbers. With our 12 and 9 example the remainder from the first iteration is 3 since 9 divides into 12 once with 3 as the remainder. As that remainder divides exactly into 9 that is the GCF since 3x3 gives 9 and 3x3+3 (ie. 4x3) gives 12.

The LCM is related to the GCF in that if the GCF is 1 then the LCM is obtained by multiplying the two numbers together (as the two numbers are not both divisible by any number greater than 1). Where there is a number that divides into both numbers then the LCM will be the two numbers multiplied together and then divided by the greatest of the numbers that will divide into both (ie. the GCF).

So in JavaScript our LCM function looks like this:

``function lcm(a, b) {return a * b / gcf(a,b);}``