3.4 Coprime Integers
Two integers \(a\) and \(b\) are coprime (or relatively prime) if \(\gcd(a, b)=1\).
For example, \(15\) and \(23\) are coprime, but \(15\) and \(20\) are not.
When dealing with more than two integers, there is two ways to generalise.
- The integers \(a_1, a_2, \ldots, a_n\) are coprime if {\(\gcd(a_1, a_2, \ldots, a_n)=1\).}
- The integers \(a_1, a_2, \ldots, a_n\) are mutually coprime if {\(\gcd(a_i, a_j)=1\) whenever \(i\neq j\).}
It should be clear that if the integers \(a_1, a_2, \ldots, a_n\) are mutually coprime then they are coprime (since \(\gcd(a_1, a_2, \ldots)|\gcd(a_i, a_j)\)).
The converse is false: for example, the integers \(6, 10, 15\) are coprime but are not mutually coprime.
Two integers \(a\) and \(b\) are coprime if and only if there exist integers \(x\) and \(y\) such that \[ax+by=1.\]
Proof. If \(\gcd(a,b)=1\) then by Theorem 3.16, we have \(ax+by=1\) for some \(x, y\in{\mathbb Z }\).
Conversely we know that \(\gcd(a,b)\) is the least positive value of \(ax+by\), so if this is \(1\) for some \(x,y\) then \(\gcd(a,b)=1\).
The following two corollaries will prove extremely useful, and will be used on a number of occasions in subsequent chapters.
If \(\gcd(a, b)=d\) then \[\gcd(ma, mb)=md\] for every integer \(m>0\), and \[\gcd(u,v)=1\]
where \(u\) is the unique integer such that \(a=ud\) and \(v\) is the unique integer such that \(b=vd\).
Proof. By Theorem 3.16, \(\gcd(ma, mb)\) is the smallest positive value of \(max+mby=m(ax+by)\), where \(x, y\in{\mathbb Z}\), while \(d\) is the smallest positive value of \(ax+by\), so \(\gcd(ma, mb)=md\). Write \(d=ax+by = (du)x + (dv)y\). Then by the cancellation lemma \(ux+vy=1\). Corollary 3.25 then implies that \(u\) and \(v\) are coprime.
Let \(a\) and \(b\) be coprime integers.
- If \(a|c\) and \(b|c\) then \(ab|c\).
- If \(a|bc\) then \(a|c\).
Proof. Let \(a\) and \(b\) be coprime integers.
We have \(ax+by=1,\; c=ae\) and \(c=bf\) for some integers \(x, y, e\) and \(f\). Then \(c=cax+cby=(bf)ax+(ae)by=ab(fx+ey)\), so \(ab|c\).
As in (a), \(c=cax+cby\). Since \(a|bc\) and \(a|a\), Corollary 3.11 implies that \(a|(cax+cby)=c\).
Least Common Multiple
If \(a\) and \(b\) are integers, then a common multiple of \(a\) and \(b\) is an integer \(c\) such that \(a|c\) and \(b|c\). If \(a\) and \(b\) are both non-zero, then they have positive common multiples (such as \(|ab|\)), so by the well-ordering principle they have a least common multiple or, more precisely, a least positive common multiple; this is the unique positive integer \(l\) satisfying
- \(a|l\) and \(b|l\) (so \(l\) is a common multiple), and
- if \(a|c\) and \(b|c\), with \(c>0\), then \(l\le c\) (so no positive common multiple is less than \(l\)).
Let \(a\) and \(b\) be positive integers, with \(d=\gcd(a, b)\) and \(l=\text{ lcm}(a, b)\). Then \[dl=ab.\]
NOTE: We can assume that \(a,b>0\) since \(\gcd(a,b)=\gcd(|a|,|b|)\) and \(\text{lcm}(a,b)=\text{lcm}(|a|,|b|)\).
Proof. Let \(a = ed\) and \(b = fd\), so that \[ab=efd^2.\] Now consider \(efd\), clearly this is positive, so we can show that it is equal to \(l\) by showing that it satisfies conditions (1) and (2) of the definition of \(\text{lcm}(a,b)\).
Firstly, \[efd=(ed)f=af\quad\text{and}\quad edf=(fd)e=be;\] thus \(a|def\) and \(b|def\), so (1) is satisfied.
Secondly, suppose that \(a|c\) and \(b|c\), with \(c>0\); it follows that there exist integers \(p,q\) such that \(c=ap = bq\). We need to show that \(def\le c\).
By Theorem 3.16 there exist integers \(u\) and \(v\) such that \(d=au+bv\). Now \[(ab) (qu+pv)= abqu+abpv = acu+bcv = c(au+bv) = cd\]
hence \(ab\) is a divisor of \(cd\).
This implies that \(cd=kab\) for some integer \(k\), so \(cd=kd(def)\). The cancellation lemma means that \(c=kdef\). Hence \(def\) divides \(c\), and so, as we noted in Lemma 3.9, \(def\le c\) as required.
If \(a=16\) and \(b=12\), then \(d=4\) and \(l=48\); thus \(dl=192=ab\), agreeing with Theorem 3.28.
We can use Theorem 3.28 to find \(l=\text{ lcm}(a, b)\) efficiently by first using Euclid’s algorithm to find \(d=\gcd(a, b)\), and then calculating \(l=ab/d\).
Since \(\gcd(1815, 1415)=5\) we have \(\text{lcm}(1815, 1415)=(1815\times 1415)/5=513645\).