the RELATIONSHIP between LEAST COMMON MULTIPLE and GREATEST COMMON DIVISOR

[@PawelS_77]

My proof: From definitions of lcm and gcd we can observe that: lcm(m,n) = m*a = n*b gcd(m,n) = m/c = n/d Where a, b, c, d are some integers. So, m/n = b/a = c/d a and b are relatively prime, because otherwise we could divide them by their common factor and achieve a smaller lcm. Likewise, c and d are relatively prime, because otherwise we could divide them by their common factor and achieve a bigger gcd. So b/a and c/d are equal, and are irreducible fractions. Which means b = c and a = d. Therefore: lcm(m,n)*gcd(m,n) = (m*a) * (n/a) = m*n (Alternatively: lcm(m,n)*gcd(m,n) = (n*b) * (m/b) = m*n)

[@rexcool188]

Thats so elegant, thank you for this!

[@Alan-zf2tt]

Outstanding! I particularly admire the switching between groups and rings. It sort of justifies they "hey" alarm bells about extending things into 'new' or 'novel' areas.

[@junkdubious]

This was the first program I ever coded on an Apple II.

[@junkdubious]

@Abhinav I did that years before on a TI-99/4A.

[@Felipe-sw8wp]

An elementary proof below which I like. Let ℓ=lcm(m,n). Then by property mentioned in 4:54, we have that m⋅n=ℓ⋅d, for some d. The number d is a common divisor of m and n because m=(ℓ/n)⋅d and n=(ℓ/m)⋅d. Another fact is that if d' is any common divisor of m and n, then there is an ℓ′ which is a common multiple of m and n such that d'⋅ℓ′=m⋅n (it is easy to prove this). Finally we prove that d=gcd(m,n) as follows: Suppose there is a common divisor d' of m and n such that d'>d. Then by the fact mentioned above, there is a common multiple ℓ′ of m and n such that d'⋅ℓ′=m⋅n=d⋅ℓ and d'>d. Hence ℓ′

[@harryh5666]

Love the new jazzy intro, clean blackboard, color variation, and (as always) attention to detail ! Makes a huge difference : )

[@matematicacommarcospaulo]

Abstract algebra and Number Theory are my favorite parts of Mathematics, that's why I loved this video

[@jacemandt]

5:58 Michael coins a new word: "lcm-ness"

[@davidemasi__]

I saw this proof on your second channel and I really loved it, thank you Michael

[@alonamaloh]

lcd picks the maximum of each exponent in the prime factorizations, and gcd picks the minimum. Then take the obvious identity max(a,b) + min(a,b) = a + b. Apply that to the exponents of each prime and we are done.

[@Raspberry_aim]

Brilliant proof; thank you for sharing!

[@synaestheziac]

Wow, this really helps to motivate the Second Isomorphism Theorem for Rings, which has always been mysterious to me!

[@seanbastian4614]

A fun follow up proof is that the Euler's phi(totient) function preserves that very same equation. In other terms, let f be Euler's phi function. Then f(lcm(a,b))*f(gcd(a,b))=f(a)*f(b).

[@TheEternalVortex42]

It's true for any multiplicative function.

[@chrisdaley2852]

Euler's phi function is only multiplicative for a and b which are coprime. This identity works for gcd(a,b)>1 too.

[@nathanryan12]

Such an amazing channel. Thank you!

[@sohamsen9295]

My Proof :: Need to Prove : lcm[m, n]gcd(m, n) = mn Let gcd(m, n) = k. Then write m = ak and n = bk for some a and b Note that gcd(a, b) = 1 Then, lcm[m, n] = lcm[ak, bk] = abk Finally, LHS = lcm[m, n]gcd(m, n) = abk * k = abk^2 RHS = mn = ak*bk = abk^2 LHS = RHS. Hence proved.

[@MyOneFiftiethOfADollar]

Instructive insight into the value of relating groups with one operation and rings possessing two operations. Have seen this proof where the lcm and gcd symbols were used all the way through the proof which makes the exposition less legible than your approach of assigning single letters.

[@sidimohamedbenelmalih7133]

Still the decomposition of the two numbers and writing them and grouping the lcm and gcd my best and easy way to solve this problem

[@Nerdwithoutglasses]

Here is another way to see why it is true. Call PF: prime factorization. Let A, B are the sets that represent PF(n), PF(m). Then lcm(m,n) is the union of A and B, gcd(m,n) is the intersection of A and B. Now we can prove it visually (this way is not rigorous but it is easier to understand)

[@mtaur4113]

A and B have to be understood as having "duplicates", so that if p_1=2, and n is divisible by 2^4, then A has the elements p_{1,1}, p_{1,2}, ..., p_{1,4}

[@spicymickfool]

By definition the gcd(g) of x and y implies x=mg and y=ng with m and n having no common factors other than 1, otherwise that would be a factor of g increasing its value therefor contradicting that it is the greatest common factor. xy=mng^2. xy is a multip of mg=x and a factor of ng=y and remains so upon division by g. xy/g=mng fails to be divisible by x or y if divided by any factor greater than 1 for this will remove a necessary factor to get either x or y. Thus mng is the least common multiple of both x and y and xy=g(x,y)l(x,y).

[@terryendicott2939]

Have sledge hammer will kill flies.

[@notfancy2000]

6:13 There's no need to prove the converse as every step in the deduction can be reversed, so that implications are actually equivalences. In short, the proof of the “pong” is the proof of the “ping” read bottom to top.

[@MyOneFiftiethOfADollar]

Right, this would be denoted with the standard thick double equivalence arrows all the way through which can be cumbersome to read.

[@notfancy2000]

@@MyOneFiftiethOfADollar I find ping-pong proofs far more tiresome than calculational-style ones: not only you have to read essentially the same proof twice, you have to keep in mind the ping to completely understand the pong. With calculational proofs, you only have to convince yourself that the equivalence holds step by step. It is not clever and that is precisely its strength.

[@MyOneFiftiethOfADollar]

@@notfancy2000 sure, but you have to be on the lookout for proofs that are only unidirectional. For example, differentiability implies continuity, but continuity does not imply differentiability. Absolute value function being the common example of this.

[@notfancy2000]

@@MyOneFiftiethOfADollar Implications can be proved equationally by treating the "implies" as a Boolean operator (sometimes proving "the consequent or not the antecedent" is easier, cf proofs by contradiction). Dijkstra tried to systematize the style in his Calculus of Boolean Structures. The algebra of proofs didn't catch on but the style did in CS circles oriented to functional and declarative programming (John Reynolds is a good example of someone who was astride both the mathematical and computer science worlds).

[@MyOneFiftiethOfADollar]

@@notfancy2000 any reason that you don’t produce math or computer science videos on your channel?

[@ishaangoud3180]

This actually comes in group theory

[@derekfordyce9]

Hey, just saw this on Dr. Barker's channel

[@DirtShaker]

me too, i was curios if someone mentioned this here 🙂- Dr Barkers Proof took about 2 Minutes and no heavy weapons.

[@krisbrandenberger544]

Hey, Michael! @ 11:14 Should be nvx, not nvy.

[@nothingbutmathproofs7150]

I was just going to note that as well.

[@stevenwilson5556]

I was good until we got to the end, I don't have enough background in rings and group theory to get the last part.

[@mtaur4113]

Proof that every common multiple is a multiple of the lcm deserves to be written out. After all, before you can call it the definition, you have to prove that you can assert this special property in addition to just being the smallest. But it takes a few lemmas, so idk. Undergrad number theory will cover it.

[@tomholroyd7519]

Wow, yeah, that's pretty fancy.

[@maxvangulik1988]

How are natural numbers different from integers?

[@lefty5705]

By the fundamental thm of arithmetic, m and n can be expressed as a product of power of primes lcm(m,n) and gcd(m,n) are product of min and max number of power of prime respectively. so clearly lcm(m,n)×gcd(m,n) =mn

[@toricon8070]

max(m,n)+min(m,n) = m+n mirrors lcm(m,n)×gcd(m,n) = m×n very nicely, and this proof takes you directly from one to the other.

[@lefty5705]

Thank you for the comment

[@silver6054]

@@toricon8070 What do you mean by max and min here? If the normal meaning, isn't it trivial? Case 1: m >= n, then max(m,n) = m (say) and min(m,n)= n. So max(m,n) + min(m,n) = m+n. And similarly for the case where m < n

[@toricon8070]

@@silver6054 right, exactly. and lcm and gcd take the max and min of each power of primes, respectively, and multiplication just adds each power of primes. and the FToA glues it all together.

[@gonzoz1]

and Lefty's proof doesn't obscure anything.

[@emanuellandeholm5657]

"least" does not spook me. Any non-empty subset of N has a least element. As for Z, we can just disregard 0 and use the magnitude to get rid of the sign.

[@loloolaf6359]

The same relation holds for polynomials. here, integers appears as order of some Groups. the question is :anybody knows an elegant proof of this result for polynomials?

[@lavneetjanagal]

Any such proof would either be proving fundamental theorem of algebra or be circular in nature because lcm(m,n) gcd(m,n) = mn is true by definition of (lcm and gcd) and fundamental theorem of algebra.

[@Bodyknock]

Do you mean the fundamental theorem of arithmetic? (Fundamental Theorem of Algebra says polynomials of degree n have n complex roots which isn't the theorem I think you mean. Fundamental Theorem of Arithmetic says positive integers have unique prime factorizations.)

[@jakobr_]

If you lay out the prime factors of m and n (which exist by fundamental theorem of arithmetic), notice that the gcd is the list of everything that’s been double-counted, and the lcm is everything that’s counted (without repeating between m and n). Together they account for all factors of mn.

[@paulfoss5385]

It isn't circular, it's just proving it from the properties of how the operations act on the set of integers. The proof in the video is definitely overkill, like swatting a fly with a bazooka, but overkill is really useful in math because it let's you learn a new tool on a concept you have an intuitive grasp of, before using it on the difficult problems its meant for.

[@Bodyknock]

@@paulfoss5385 This brings up an interesting question. The video uses the fact that every pair of m and n in the ring's domain has an lcm and a gcd. But that means this proof is maybe a bit more generalizable since it's not clear that if a ring is a gcd-domain that it is necessarily uniquely factorizable. In other words using the Fundamental Theorem of Arithmetic means the theorem works for rings that are unique factorization domains, but the proof in the video might apply to rings that are gcd domains but not UFDs.

[@icew0lf98]

is this proved with a group theory to demonstrate group theory or? because it seems very easy to prove with elementary school knowledge

[@Al.2]

Nice tricky proof 😂

[@goodplacetostop2973]

14:50

[@marc-andredesrosiers523]

A constructive proof exploiting the fundamental theorem of arithmetic would have been more enlightening.

[@benjiusofficial]

Second Isomorphism Jumpscare