If you have the gcd or the LCM of two numbers, call them a and b, you can use the relationship that gcd(a,b) = (a multiplied by b) divided by LCM (a,b) where LCM or gcd (a,b) means the LCM or a and b. This means the gcd multiplied by the LCM is the same as the product of two numbers.
Let's assume you have neither.
There are several ways to do this. One way to approach both problems at once is to factor each number into primes. You can use these prime factorizations to find both the LCM and gcd
To compute the Greatest common divisor, list the common prime factors and raise each to the least multiplicities that occurs among the several whole numbers.
To compute the least common multiple, list all prime factors and raise each to the greatest multiplicities that occurs among the several whole numbers.
Chat with our AI personalities
The smallest number that is a multiple of two given numbers is called the least common multiple (LCM) of those two numbers. It can be found by taking the product of the two numbers and dividing it by their greatest common divisor (GCD).
Short answer: Yes. Long answer: Explanation: lcm means least common multiple, gcd means greatest common divisor, |a| means the absolute of a, a / b means a divided by b, a * b means a multiplied by b Premise: Let a and b be a natural numbers, i.e. a ⋲ IN, b ⋲ IN. 1: It is known that lcm(a, b) = (|a| * |b|) / gcd(a, b) 2: Also the gcd of two numbers is at least 1, or in math: ∀ a ⋲ IN: gcd(a, b) >= 1. 3: From 1 and 2 we can conclude: lcm(a, b) = |a| * |b| / gcd(a, b) <= |a| * |b| 4: From 3 and the premise we can conclude (because ∀ a ⋲ IN: |a| = a): lcm(a, b) <= a * b 5: Now the product of two natural numbers (like a and b) is a natural number as well, or in math: ∀ a ⋲ IN, b ⋲ IN: a * b ⋲ IN 6: From 2 and 5 we can finally conclude, that: ∀ a ⋲ IN, b ⋲ IN ∃ c ⋲ IN: lcm(a, b) <= c
These are the two functions you need: public static int lcm(int i1, int i2) { return (i1*i2/gcd(i1,i2)); } public static int gcd(int i1, int i2) { // using Euclid's algorithm int a=i1, b=i2, temp; while (b!=0) { temp=b; b=a%temp; a=temp; } return a; }
Any two numbers who are relatively prime will workSo look at 9 and 4. Neither is prime and their GCD is 1.You must need two numbers with NO other factors in common.
No, the only way the GCF and LCM of two numbers can be the same is if the numbers are the same.