Least Common Multiple

1. Note that \[\begin{eqnarray*} & & \nlcm(a,\zero) \\ & \href{/posts/arithmetic-made-difficult/LeastCommonMultiple.html#def-lcm} = & \nquo(\ntimes(a,\zero),\ngcd(a,\zero)) \\ & = & \nquo(\zero,a) \\ & = & \zero. \end{eqnarray*}\]
2. Note that \[\begin{eqnarray*} & & \nlcm(a,\next(\zero)) \\ & \href{/posts/arithmetic-made-difficult/LeastCommonMultiple.html#def-lcm} = & \nquo(\ntimes(a,\next(\zero)),\ngcd(a,\next(\zero))) \\ & = & \nquo(a,\next(\zero)) \\ & = & a. \end{eqnarray*}\]

1. We consider two cases: \(a = \zero\) and \(a \neq \zero\). If \(a = \zero\), we have \[\begin{eqnarray*} & & \nlcm(a,a) \\ & \href{/posts/arithmetic-made-difficult/LeastCommonMultiple.html#def-lcm} = & \nquo(\ntimes(a,a),\ngcd(a,a)) \\ & = & \nquo(\zero,\zero) \\ & = & \zero \\ & = & a \end{eqnarray*}\] as claimed. If \(a \neq \zero\), say \(a = \next(t)\), then we have \[\begin{eqnarray*} & & \nlcm(a,a) \\ & \href{/posts/arithmetic-made-difficult/LeastCommonMultiple.html#def-lcm} = & \nquo(\ntimes(a,a),\ngcd(a,a)) \\ & \href{/posts/arithmetic-made-difficult/GreatestCommonDivisor.html#thm-gcd-idempotent} = & \nquo(\ntimes(a,a),a) \\ & = & a \end{eqnarray*}\] as claimed.
2. Note that \[\begin{eqnarray*} & & \nlcm(a,b) \\ & \href{/posts/arithmetic-made-difficult/LeastCommonMultiple.html#def-lcm} = & \nquo(\ntimes(a,b),\ngcd(a,b)) \\ & = & \nquo(\ntimes(b,a),\ngcd(b,a)) \\ & \href{/posts/arithmetic-made-difficult/LeastCommonMultiple.html#def-lcm} = & \nlcm(b,a) \end{eqnarray*}\] as claimed.

1. We consider two cases: \(\ngcd(a,b) = \zero\) and \(\ngcd(a,b) \neq \zero\). If \(\ngcd(a,b) = \zero\), then we have \(a = b = \zero\). Now \[\begin{eqnarray*} & & \nlcm(\zero,\zero) \\ & \href{/posts/arithmetic-made-difficult/LeastCommonMultiple.html#def-lcm} = & \nquo(\ntimes(\zero,\zero),\ngcd(\zero,\zero)) \\ & = & \nquo(\zero,\zero) \\ & = & \zero \end{eqnarray*}\] and \(\ndiv(\zero,\zero)\) as needed. Suppose instead that \(\ngcd(a,b) \neq \zero\). Say \(b = \ntimes(k,\ngcd(a,b))\). Now \[\begin{eqnarray*} & & \nlcm(a,b) \\ & \href{/posts/arithmetic-made-difficult/LeastCommonMultiple.html#def-lcm} = & \nquo(\ntimes(a,b),\ngcd(a,b)) \\ & = & \nquo(\ntimes(\ntimes(a,k),\ngcd(a,b)),\ngcd(a,b)) \\ & = & \ntimes(a,k), \end{eqnarray*}\] so that \(\ndiv(a,\nlcm(a,b))\). A similar argument shows that \(\ndiv(b,\nlcm(a,b))\) as claimed.
2. Suppose we have \(\ndiv(a,c)\) and \(\ndiv(b,c)\). We consider two cases: either \((a,b) = (\zero,\zero)\) or \((a,b) \neq (\zero,\zero)\). First suppose \((a,b) = (\zero,\zero)\). Now \(c = \zero\), and we have \(\ndiv(\nlcm(a,b),\zero)\) as claimed. Suppose instead that \((a,b) \neq (\zero,\zero)\). Say \(c = \ntimes(a,u)\) and \(c = \ntimes(b,v)\). Now let \(d = \ngcd(a,b)\) (note that \(d \neq \zero\)) and say \(a = \ntimes(d,s)\) and \(b = \ntimes(d,t)\). Note that \(\ncoprime(s,t)\). Now we have \[\begin{eqnarray*} c & = & c \\ \ntimes(a,u) & = & \ntimes(b,v) \\ \ntimes(\ntimes(d,s),u) & = & \ntimes(\ntimes(d,t),v) \\ \ntimes(d,\ntimes(s,u)) & = & \ntimes(d,\ntimes(d,t)) \\ \ntimes(s,u) & = & \ntimes(t,v). \end{eqnarray*}\] That is, \(\ndiv(t,\ntimes(s,u))\). By Euclid’s lemma, we have \(\ndiv(t,u)\). Next, note that \[\begin{eqnarray*} & & \nlcm(a,b) \\ & \href{/posts/arithmetic-made-difficult/LeastCommonMultiple.html#def-lcm} = & \nquo(\ntimes(a,b),\ngcd(a,b)) \\ & = & \nquo(\ntimes(a,\ntimes(t,d)),d) \\ & \href{/posts/arithmetic-made-difficult/Times.html#thm-times-associative} = & \nquo(\ntimes(\ntimes(a,t),d),d) \\ & = & \ntimes(a,t). \end{eqnarray*}\] Since \(c = \ntimes(a,u)\), we have \[\begin{eqnarray*} & & \btrue \\ & = & \ndiv(t,u) \\ & = & \ndiv(\ntimes(a,t),\ntimes(a,u)) \\ & = & \ndiv(\nlcm(a,b),c) \end{eqnarray*}\] as claimed.

Since \(\ndiv(a,m)\) and \(\ndiv(b,m)\), we have \(\ndiv(\nlcm(a,b),m)\). But likewise we have \(\ndiv(m,\nlcm(a,b))\). By antisymmetry, we have \(m = \nlcm(a,b)\) as claimed.

Note that \(\ndiv(a,\nlcm(a,\nlcm(b,c)))\). We also have \(\ndiv(b,\nlcm(b,c))\), so that \[\ndiv(b,\nlcm(a,\nlcm(b,c)))\] by transitivity; similarly, \[\ndiv(c,\nlcm(a,\nlcm(b,c))).\] By the universal property of \(\nlcm\), we thus have \[\ndiv(\nlcm(a,b),\nlcm(a,\nlcm(b,c))),\] so that \[\ndiv(\nlcm(\nlcm(a,b),c),\nlcm(a,\nlcm(b,c))).\] A similar argument shows that \[\ndiv(\nlcm(a,\nlcm(b,c)),\nlcm(\nlcm(a,b),c)).\] By antisymmetry, we thus have \[\nlcm(a,\nlcm(b,c)) = \nlcm(\nlcm(a,b),c)\] as claimed.

First suppose \(\ndiv(b,a)\); say \(a = \ntimes(b,d)\). Now \(\ndiv(a,a)\) and \(\ndiv(b,a)\), and if \(\ndiv(c,a)\) and \(\ndiv(c,b)\) then \(\ndiv(c,a)\). By the universal property of \(\nlcm\) we have \(a = \nlcm(a,b)\). Conversely, suppose \(a = \nlcm(a,b)\). We consider two cases: either \((a,b) = (\zero,\zero)\) or \((a,b) \neq (\zero,\zero)\). If \((a,b) = (\zero,\zero)\) then \(\ndiv(b,a)\) as needed. Suppose then that \((a,b) \neq (\zero,\zero)\). If \(a = \zero\), then \(\ndiv(b,a)\) as claimed. Suppose \(a \neq \zero\). Now let \(d = \ngcd(a,b)\); note that \(d \neq \zero\). Say \(b = \ntimes(k,d)\). Now \[\begin{eqnarray*} & & \ntimes(a,\next(\zero)) \\ & \href{/posts/arithmetic-made-difficult/Times.html#thm-times-one-right} = & a \\ & = & \nlcm(a,b) \\ & \href{/posts/arithmetic-made-difficult/LeastCommonMultiple.html#def-lcm} = & \nquo(\ntimes(a,b),\ngcd(a,b)) \\ & = & \nquo(\ntimes(\ntimes(a,k),d),d) \\ & = & \ntimes(a,k). \end{eqnarray*}\] Since \(a \neq \zero\), we have \(k = \next(\zero)\), and thus \(b = \ngcd(a,b)\). Hence \(\ndiv(b,a)\) as claimed.

We consider two cases: either \(c = \zero\) or \(c \neq \zero\). If \(c = \zero\) we have \[\begin{eqnarray*} & & \nlcm(\ntimes(c,a),\ntimes(c,b)) \\ & = & \nlcm(\zero,\zero) \\ & \href{/posts/arithmetic-made-difficult/LeastCommonMultiple.html#thm-lcm-zero} = & \zero \\ & \href{/posts/arithmetic-made-difficult/Times.html#cor-times-up-zero} = & \ntimes(\zero,\nlcm(a,b)) \\ & = & \ntimes(c,\nlcm(a,b)) \end{eqnarray*}\] as claimed. Suppose then that \(c \neq \zero\). Now we have \[\begin{eqnarray*} & & \nlcm(\ntimes(c,a),\ntimes(c,b)) \\ & \href{/posts/arithmetic-made-difficult/LeastCommonMultiple.html#def-lcm} = & \nquo(\ntimes(\ntimes(c,a),\ntimes(c,b)),\ngcd(\ntimes(c,a),\ntimes(c,b))) \\ & = & \nquo(\ntimes(\ntimes(c,\ntimes(a,b)),c),\ngcd(\ntimes(a,b),c)) \\ & = & \nquo(\ntimes(c,\ntimes(a,b)),\ngcd(a,b)) \\ & = & \ntimes(c,\nquo(\ntimes(a,b),\ngcd(a,b))) \\ & \href{/posts/arithmetic-made-difficult/LeastCommonMultiple.html#def-lcm} = & \ntimes(c,\nlcm(a,b)) \end{eqnarray*}\] as claimed.

We have \[\begin{eqnarray*} & & \nlcm(\nlcm(a,c),\nlcm(b,c)) \\ & = & \nlcm(\nlcm(a,b),\nlcm(c,c)) \\ & = & \nlcm(b,c) \end{eqnarray*}\] so that \(\ndiv(\nlcm(a,c),\nlcm(b,c))\) as claimed.

The proofs of these two results will not be painful, but they are a little tedious, especially with the notation we’re using for arithmetic. So for this proof – and this proof only! – I’ll make two concessions to readability. Because \(\ngcd\) is associative, there is no ambiguity in an expression like \[\ngcd(a,b,c).\] Also, we will denote \(\ntimes(a,b)\) by juxtaposition (like we’re used to anyway, but have been avoiding).

1. First suppose \(a = \zero\); note that \[\begin{eqnarray*} & & \ngcd(a,\nlcm(b,c)) \\ & = & \ngcd(\zero,\nlcm(b,c)) \\ & = & \nlcm(b,c) \\ & = & \nlcm(\ngcd(\zero,b),\ngcd(\zero,c)) \\ & = & \nlcm(\ngcd(a,b),\ngcd(a,c)) \end{eqnarray*}\] as claimed. Next suppose \(b = \zero\). Now we have \[\begin{eqnarray*} & & \ngcd(a,\nlcm(b,c)) \\ & = & \ngcd(a,\nlcm(\zero,c)) \\ & = & \ngcd(a,\zero) \\ & \href{/posts/arithmetic-made-difficult/GreatestCommonDivisor.html#thm-gcd-zero} = & a \\ & = & \nlcm(\ngcd(a,b),a) \\ & \href{/posts/arithmetic-made-difficult/GreatestCommonDivisor.html#thm-gcd-zero} = & \nlcm(\ngcd(a,b),\ngcd(a,\zero)) \\ & = & \nlcm(\ngcd(a,b),\ngcd(a,c)) \end{eqnarray*}\] as claimed. Similarly, if \(c = \zero\) we have \[\begin{eqnarray*} & & \ngcd(a,\nlcm(b,c)) \\ & = & \ngcd(a,\nlcm(b,\zero)) \\ & \href{/posts/arithmetic-made-difficult/LeastCommonMultiple.html#thm-lcm-zero} = & \ngcd(a,\zero) \\ & \href{/posts/arithmetic-made-difficult/GreatestCommonDivisor.html#thm-gcd-zero} = & a \\ & = & \nlcm(a,\ngcd(a,c)) \\ & = & \nlcm(\ngcd(a,\zero),\ngcd(b,c)) \\ & = & \nlcm(\ngcd(a,c),\ngcd(b,c)) \end{eqnarray*}\] as claimed. We can now assume that \(a\), \(b\), and \(c\) are not zero; in particular, \(\ngcd(b,c)\) and \(\ngcd(a,\ngcd(b,c))\) are not zero. We begin with a sub-result. Note that \[\begin{eqnarray*} & & \ngcd(a\ngcd(b,c),bc)\ngcd(a,\ngcd(b,c)) \\ & = & \ngcd(\ngcd(ab,ac),bc)\ngcd(a,b,c) \\ & = & \ngcd(ab,ac,bc)\ngcd(a,b,c) \\ & = & \ngcd(ab\ngcd(a,b,c),ac\ngcd(a,b,c),bc\ngcd(a,b,c)) \\ & = & \ngcd(aba,abb,abc,aca,acb,acc,bca,bcb,bcc) \\ & = & \ngcd(aab,aac,acb,acc,bab,bac,bcb,bcc) \\ & = & \ngcd(aa\ngcd(b,c),ac\ngcd(b,c),ba\ngcd(b,c),bc\ngcd(b,c)) \\ & = & \ngcd(aa,ac,ba,bc)\ngcd(b,c) \\ & = & \ngcd(a\ngcd(a,c),b\ngcd(a,c))\ngcd(b,c) \\ & = & \ngcd(a,b)\ngcd(a,c)\ngcd(b,c). \end{eqnarray*}\] Note that \[\ndiv(\ngcd(b,c),a\ngcd(b,c))\] and \[\ndiv(\ngcd(b,c),bc),\] so that \[\ndiv(\ngcd(b,c),\ngcd(a\ngcd(b,c),bc));\] thus we also have \[\ndiv(\ngcd(a,\ngcd(b,c)),\ngcd(a,b)\ngcd(a,c)).\] By cross-multiplication, we have \[\begin{eqnarray*} & & \nquo(\ngcd(a\ngcd(b,c),bc),\ngcd(b,c)) \\ & = & \nquo(\ngcd(a,b)\ngcd(a,c),\ngcd(a,\ngcd(b,c))). \end{eqnarray*}\] Thus we have \[\begin{eqnarray*} & & \ngcd(a,\nlcm(b,c)) \\ & = & \ngcd(a,\nquo(bc,\ngcd(b,c))) \\ & = & \ngcd(\nquo(a\ngcd(b,c),\ngcd(b,c)),\nquo(bc,\ngcd(b,c))) \\ & = & \nquo(\ngcd(a\ngcd(b,c),bc),\ngcd(b,c)) \\ & = & \nquo(\ngcd(a,b)\ngcd(a,c),\ngcd(a,\ngcd(b,c))) \\ & = & \nquo(\ngcd(a,b)\ngcd(a,c),\ngcd(\ngcd(a,b),\ngcd(a,c))) \\ & = & \nlcm(\ngcd(a,b),\ngcd(a,c)) \end{eqnarray*}\] as claimed.
2. First suppose \(a = \zero\). Then we have \[\begin{eqnarray*} & & \nlcm(a,\ngcd(b,c)) \\ & = & \nlcm(\zero,\ngcd(b,c)) \\ & = & \zero \\ & \href{/posts/arithmetic-made-difficult/GreatestCommonDivisor.html#thm-gcd-idempotent} = & \ngcd(\zero,\zero) \\ & = & \ngcd(\nlcm(\zero,b),\nlcm(\zero,c)) \\ & = & \ngcd(\nlcm(a,b),\nlcm(a,c)) \end{eqnarray*}\] as claimed. Next suppose \(b = \zero\). Then we have \[\begin{eqnarray*} & & \nlcm(a,\ngcd(b,c)) \\ & = & \nlcm(a,\ngcd(\zero,c)) \\ & = & \nlcm(a,c) \\ & = & \ngcd(\zero,\nlcm(a,c)) \\ & \href{/posts/arithmetic-made-difficult/LeastCommonMultiple.html#thm-lcm-zero} = & \ngcd(\nlcm(a,\zero),\nlcm(a,c)) \\ & = & \ngcd(\nlcm(a,b),\nlcm(a,c)) \end{eqnarray*}\] as claimed. Similarly, if \(c = \zero\) we have \[\begin{eqnarray*} & & \nlcm(a,\ngcd(b,c)) \\ & = & \nlcm(a,\ngcd(b,\zero)) \\ & \href{/posts/arithmetic-made-difficult/GreatestCommonDivisor.html#thm-gcd-zero} = & \nlcm(a,b) \\ & \href{/posts/arithmetic-made-difficult/GreatestCommonDivisor.html#thm-gcd-zero} = & \ngcd(\nlcm(a,b),\zero) \\ & = & \ngcd(\nlcm(a,b),\nlcm(a,\zero)) \\ & = & \ngcd(\nlcm(a,b),\nlcm(a,c)) \end{eqnarray*}\] as claimed. We can now assume that \(a\), \(b\), and \(c\) are not zero; in particular, \(\ngcd(a,b)\ngcd(a,c)\) and \(\ngcd(a,\ngcd(b,c))\) are not zero; in particular, \(\ngcd(a,b)\ngcd(a,c)\) and \(\ngcd(a,\ngcd(b,c))\) are not zero. We begin with a sub-result. Note that \[\begin{eqnarray*} & & a\ngcd(a,\ngcd(b,c))\ngcd(ba,bc,ca,cb) \\ & = & a\ngcd(a,b,c)\ngcd(ba,bc,ca,cb) \\ & = & a\ngcd(a\ngcd(ba,bc,ca,cb),b\ngcd(ba,bc,ca,cb),c\ngcd(ba,bc,ca,cb)) \\ & = & a\ngcd(\ngcd(aba,abc,aca,acb),\ngcd(bba,bbc,bca,bcb),\ngcd(cba,cbc,cca,ccb)) \\ & = & a\ngcd(aba,abc,aca,acb,bba,bbc,bca,bcb,cba,cbc,cca,ccb) \\ & = & a\ngcd(aab,aac,acb,acc,bab,bac,bcb,bcc) \\ & = & a\ngcd(aa\ngcd(b,c),ac\ngcd(b,c),ba\ngcd(b,c),bc\ngcd(b,c)) \\ & = & a\ngcd(aa,ac,ba,bc)\ngcd(b,c) \\ & = & a\ngcd(a\ngcd(a,c),b\ngcd(a,c))\ngcd(b,c) \\ & = & a\ngcd(a,b)\ngcd(a,c)\ngcd(b,c). \end{eqnarray*}\] Note that \[\ndiv(\ngcd(a,\ngcd(b,c)),a\ngcd(b,c)),\] so that \[\ndiv(\ngcd(a,b)\ngcd(a,c),a\ngcd(ba,bc,ca,cb)).\] By cross-multiplication, we have \[\begin{eqnarray*} & & \nquo(a\ngcd(ba,bc,ca,cb),\ngcd(a,b)\ngcd(a,c)) \\ & = & \nquo(a\ngcd(b,c),\ngcd(a,\ngcd(b,c))). \end{eqnarray*}\] Thus we have \[\begin{eqnarray*} & & \ngcd(\nlcm(a,b),\nlcm(a,c)) \\ & = & \ngcd(\nquo(ab,\ngcd(a,b)),\nquo(ac,\ngcd(a,c))) \\ & = & \ngcd(\nquo(ab\ngcd(a,c),\ngcd(a,b)\ngcd(a,c)),\nquo(ac\ngcd(a,b),\ngcd(a,b)\ngcd(a,c))) \\ & = & \nquo(\ngcd(ab\ngcd(a,c),ac\ngcd(a,b)),\ngcd(a,b)\ngcd(a,c)) \\ & = & \nquo(a\ngcd(b\ngcd(a,c),c\ngcd(a,b)),\ngcd(a,b)\ngcd(a,c)) \\ & = & \nquo(a\ngcd(ba,bc,ca,cb),\ngcd(a,b)\ngcd(a,c)) \\ & = & \nquo(a\ngcd(b,c),\ngcd(a,\ngcd(b,c))) \\ & = & \nlcm(a,\ngcd(b,c)) \end{eqnarray*}\] as claimed.