If a and b are positive integers, prove that:

Question

ab = gcd(a,b)*lcm(a,b).

Can visualize this being true and easily create examples just don't know how to prove algebraically.

well the gcd of any two number can be found by multiplying the two numbers together and the lcm of all numbers is
Thus ab = gcd(a,b)*lcm(a,b)
= (a*b)* 1
= ab

The lcd is usally the number we try to find so the gcd is never really stressed, unless you are teaching students how to compare fractions quickly when simplified fractions isn't necessary. For example:

7/8 and 9/11
set them up as ratios and cross multiply
77 and 72...the reason this works is because you basically found the gcd of 88 but since the denominators are both 88 it isn't relevant in the comparison

This is an incorrect answer as your first line, gcd "can be found multiplying the two numbers together" is wrong.

Answer 1

To prove this algebraically, we can use the fact that the greatest common divisor (gcd) and least common multiple (lcm) have unique prime factorizations.

Let's denote the prime factorization of a and b as follows:

a = p_1^a1 * p_2^a2 * p_3^a3 * ... * p_n^an
b = p_1^b1 * p_2^b2 * p_3^b3 * ... * p_n^bn

Here, p_i is the ith prime number and a_i and b_i are the exponents of the respective prime numbers in the prime factorization of a and b.

Now, the gcd of a and b can be found by taking the minimum exponent for each common prime factor:

gcd(a, b) = p_1^min(a1,b1) * p_2^min(a2,b2) * p_3^min(a3,b3) * ... * p_n^min(an,bn)

Similarly, the lcm of a and b can be found by taking the maximum exponent for each prime factor:

lcm(a, b) = p_1^max(a1,b1) * p_2^max(a2,b2) * p_3^max(a3,b3) * ... * p_n^max(an,bn)

Now we can write ab as:

ab = (p_1^a1 * p_2^a2 * p_3^a3 * ... * p_n^an) * (p_1^b1 * p_2^b2 * p_3^b3 * ... * p_n^bn)

We can see that the product of gcd(a,b) and lcm(a,b) is:

gcd(a,b) * lcm(a,b) = (p_1^min(a1,b1) * p_2^min(a2,b2) * p_3^min(a3,b3) * ... * p_n^min(an,bn)) * (p_1^max(a1,b1) * p_2^max(a2,b2) * p_3^max(a3,b3) * ... * p_n^max(an,bn))

For each prime factor p_i, we know that either a_i is equal to b_i, a_i is greater than b_i, or a_i is less than b_i.

If a_i = b_i, then min(a_i, b_i) = max(a_i, b_i) = a_i, and the product becomes p_i^a1 * p_i^b1 = p_i^(a1+b1).

If a_i > b_i, then min(a_i, b_i) = b_i and max(a_i, b_i) = a_i. The product becomes p_i^a1 * p_i^b1 = p_i^(a1+b1).

If a_i < b_i, then min(a_i, b_i) = a_i and max(a_i, b_i) = b_i. The product becomes p_i^a1 * p_i^b1 = p_i^(a1+b1).

In all cases, the product of gcd(a,b) and lcm(a,b) is equal to the product of the prime factorizations of a and b. Therefore, ab = gcd(a,b) * lcm(a,b).