Method 1. The prime factorization:
The prime factorization of a number: finding the prime numbers that multiply together to make that number.
1,000,000,000,000 = 212 × 512
1,000,000,000,000 is not a prime number but a composite one.
99,999,999,999 = 32 × 21,649 × 513,239
99,999,999,999 is not a prime number but a composite one.
* The natural numbers that are only divisible by 1 and themselves are called prime numbers. A prime number has exactly two factors: 1 and itself.
* A composite number is a natural number that has at least one other factor than 1 and itself.
Calculate the least common multiple, lcm:
Multiply all the prime factors of the two numbers, taken by the largest exponents (largest powers).
lcm (1,000,000,000,000; 99,999,999,999) = 212 × 32 × 512 × 21,649 × 513,239
lcm (1,000,000,000,000; 99,999,999,999) = 212 × 32 × 512 × 21,649 × 513,239 = 99,999,999,999,000,000,000,000
The two numbers have no prime factors in common:
99,999,999,999,000,000,000,000 = 1,000,000,000,000 × 99,999,999,999
Method 2. The Euclidean Algorithm:
Calculate the greatest (highest) common factor (divisor):
This algorithm involves the process of dividing numbers and calculating the remainders.
'a' and 'b' are the two natural numbers, 'a' >= 'b'.
Divide 'a' by 'b' and get the remainder of the operation, 'r'.
If 'r' = 0, STOP. 'b' = the gcf (hcf, gcd) of 'a' and 'b'.
Else: Replace ('a' by 'b') and ('b' by 'r'). Return to the step above.
Step 1. Divide the larger number by the smaller one:
1,000,000,000,000 ÷ 99,999,999,999 = 10 + 10
Step 2. Divide the smaller number by the above operation's remainder:
99,999,999,999 ÷ 10 = 9,999,999,999 + 9
Step 3. Divide the remainder of the step 1 by the remainder of the step 2:
10 ÷ 9 = 1 + 1
Step 4. Divide the remainder of the step 2 by the remainder of the step 3:
9 ÷ 1 = 9 + 0
At this step, the remainder is zero, so we stop:
1 is the number we were looking for - the last non-zero remainder.
This is the greatest (highest) common factor (divisor).
The greatest (highest) common factor (divisor):
gcf, hcf, gcd (1,000,000,000,000; 99,999,999,999) = 1
Calculate the least common multiple:
The least common multiple, Formula:
lcm (a; b) = (a × b) / gcf, hcf, gcd (a; b)
lcm (1,000,000,000,000; 99,999,999,999) =
(1,000,000,000,000 × 99,999,999,999) / gcf, hcf, gcd (1,000,000,000,000; 99,999,999,999) =
99,999,999,999,000,000,000,000 / 1 =
99,999,999,999,000,000,000,000
lcm (1,000,000,000,000; 99,999,999,999) = 99,999,999,999,000,000,000,000 = 212 × 32 × 512 × 21,649 × 513,239