Corollaries of Bezout's Identity and the Linear Combination Lemma

Section 8.3 Corollaries of Bezout's Identity and the Linear Combination Lemma

Below we prove some useful corollaries using Bezout's Identity (Theorem 8.2.13) and the Linear Combination Lemma.

Corollary 8.3.1.

Let \(a,b,c\in\ZZ\text{.}\) Suppose \(c\neq 0\text{,}\) \(c\) divides \(ab\) and \(\gcd(a,c)=1\text{.}\) Then \(c\) divides \(b\text{.}\)

Proof.

There are integers \(s\) and \(t\) such that \(1=\gcd(c,a)=sa+tc\text{.}\) This gives \(b=sab+tcb\text{.}\) Then \(c\) divides \(b\) by the Linear Combination Lemma .

Corollary 8.3.2.

Let \(a,c\in\ZZ\) and let \(d\in\ZZ\) be so that \(d\) divides \(a\) and \(d\) divides \(c\text{.}\) Then \(d\) divides \(\gcd(a,c)\text{.}\)

Proof.

By Bezout's Identity, there are integers \(s\) and \(t\) such that \(\gcd(a,c)=sa+tc\text{.}\) Then as \(d\) divides \(a\) and \(d\) divides \(b\text{,}\) we have \(d\) divides \(\gcd(a,c)\) by the Linear Combination Lemma.

Corollary 8.3.3.

Let \(d\) be a common divisor of \(a\) and \(c\text{,}\) which is divisible by all divisors of \(a\) and \(c\text{.}\) Then \(d = \pm gcd(a,c)\text{.}\)

Proof.

By the previous corollary, \(d\) divides \(\gcd(a,c)\text{,}\) and since \(d\) is divisible by all divisors, it is divisible by \(\gcd(a,b)\text{,}\) so now we apply Corollary 8.1.3.

Here are some versions of the above corollaries when some of the numbers involved are primes:

Corollary 8.3.4.

If \(a,b\in\ZZ\text{,}\) \(p\) is prime, and \(p\) divides \(ab\text{,}\) then either \(p\) divides \(a\) or \(p\) divides \(b\) (or both).

This just follows from Corollary 8.3.1 by letting \(c=p\text{.}\)

Corollary 8.3.5.

If \(n=p_1^{m_1}\cdots p_k^{m_k}\text{,}\) where each of \(p_1,\dots,p_k\) is prime, and if \(p\) is a prime number that divides \(n\text{,}\) then \(p=p_i\) for some \(i=1,\ldots, k\text{.}\)

Proof.

We prove this by induction. If \(k=1\text{,}\) then \(p\) divides \({p_1}^{m_1}\text{,}\) so by the previous corollary, \(p=p_1\text{.}\) Assume that the theorem is true for \(k=r\text{;}\) let us prove it for \(k=r+1\text{.}\) Assume that \(p\) divides \(p_{1}^{m_1}\cdots p_{r+1}^{m_{r+1}}\text{.}\) Again by the previous corollary, either \(p\) divides \(p_{k+1}^{m_{r+1}}\) or \(p\) divides \(p_1^{m_1}\cdots p_r^{m_r}\text{.}\) Thus, either \(p=p_{r+1}\text{,}\) or, by the induction hypothesis, \(p=p_i\) for some \(i=1,2,...,r\text{.}\) This completes the proof.

Let's use these results to solve a simple diophantine equation.

Example 8.3.6.

Find all integer solutions to \(2x=5y\text{.}\)

Suppose \((x,y)\) are integers solving \(2x=5y\text{.}\) Then Corollary 8.3.4 implies \(2\) divides \(y\) and \(5\) divides \(x\text{,}\) so \(y=2z\) and \(x=5w\) for some integers \(z\) and \(w\text{.}\) Inserting these into the original equation, we get a new equation

\begin{equation*} 10w = 2(5w)=5(2z) = 10z\text{.} \end{equation*}

Thus, \(w=z\text{.}\) Hence, any solution \((x,y)\) must be of the form \((x,y)=(5w,2w)\) for some integer \(w\text{.}\) We can also see that each pair of integers of the form \((5w,2w)\) is a solution. Thus, the solutions to \(2x=5y\) are exactly all pairs of integers \(\{(5w,2w) : w\in\ZZ\}\text{.}\)