GCD and LCM properties proof

Question

The following website https://www.cut-the-knot.org/arithmetic/GcdLcmProperties.shtml presents three properties of GCD and LCM. I was trying to understand the proof of it, but the proof seems to me very random and does not say when any of the three properties are proven. Does anyone else make sense of that proof?

Answer 1

The proof is not very clear at all - it looks like it only seeks to prove the third property, but does a very sketchy job of that and then meanders on to a completely different property. Nothing in there addresses the first two properties presented.

The article does hint at a viable proof technique*: if you know that every integer $N$ has a unique expression as $N=p_1^{n_1}p_2^{n_2}\ldots p_k^{n_k}$ for distinct prime $p_i$ and positive integer $n_i$, questions about divisibility tend to become a lot easier. Note that, if you have two numbers $N$ and $M$ (or more generally, a finite collection of numbers) you can expand them as products of powers of the same set of primes $$N=p_1^{n_1}p_2^{n_2}\ldots p_k^{n_k}$$ $$M=p_1^{m_1}p_2^{m_2}\ldots p_k^{m_k}$$ where some the exponents might be zero - for instance we might write $6=2^1\cdot 3^1 \cdot 5^0$ and $5=2^0\cdot 3^0\cdot 5^1$. This makes a lot of operations really easy. For instance, we can write $$NM=p_1^{n_1+m_1}p_2^{n_2+m_2}\ldots p_k^{n_k+m_k}.$$ However, then the statement that $N|M$ also becomes easy; the statement $N|M$ is defined to mean that there exists some $c$ such that $cN=M$. However, if we factored $c$ then multiplied by our previous rule, that just means that we can get the factorization of $M$ by just adding some non-negative quantities to the exponents in $N$'s factorization. We can do so exactly when $n_i \leq m_i$ for every $i$ at which point we can take $c=p_1^{m_1-n_1}p_2^{m_2-n_2}\ldots p_k^{m_k-n_k}$ and note $cN=M$. However, using this, we also find expressions for the $\gcd$ and $\operatorname{lcm}$: $$\gcd(N,M)=p_1^{\min(n_1,m_1)}p_2^{\min(n_2,m_2)}\ldots p_k^{\min(n_k,m_k)}$$ $$\operatorname{lcm}(N,M)=p_1^{\max(n_1,m_1)}p_2^{\max(n_2,m_2)}\ldots p_k^{\max(n_k,m_k)}.$$ We can both prove that these are correct and prove the first two properties by noting that if $K=p_1^{l_1}p_2^{l_2}\ldots p_k^{l_k}$ is a common divisor of $N$ and $M$, then $l_i\leq n_i$ and $l_i\leq m_i$ for each $i$, so $l_i \leq \min(n_i,m_i)$ meaning that $K$ divides the $\gcd$ we proposed - also implying the proposed $\gcd$ is at least as large as any other common divisor. A similar argument holds for the min.

One can then show that $\operatorname{lcm}(N,M)\gcd(N,M)=NM$ by noting that $\min(n_i,m_i)+\max(n_i,m_i)=n_i+m_i$ and one can show that $\gcd(K\cdot N,K\cdot M)=K\cdot \gcd(N,M)$ by factoring $K$ as before and noting that $\min(n_i+l_i,m_i+l_i)=\min(n_i,m_i)+l_i$ and do a similar thing for $\operatorname{lcm}$. Pretty much everything on that web-page follows from this observation - but they don't explain it very clearly.

---

*A slight note on this technique is that unique prime factorization is a deeper theorem than the properties it is being used to prove. Generally, these theorems also follow from the fact that for any pair of integers $a,b$, there exist integers $x$ and $y$ so that $ax+by=\gcd(a,b)$ (which happens to have a short - though rather hard to find - proof)- but this is a substantially different viewpoint than the webpage adopts.