2.2: Corollaries of Be ́zout’s Lemma

Lemma 2.6 (Euclid's Lemma)

Let \(a\) and \(b\) be such that \(\gcd (a, b) = 1\) and \(a | bc\). Then \(a | c\).

Proof

By Be ́zout, there are \(x\) and \(y\) such that \(ax+by = 1\). Multiply by \(c\) to get:

\[acx+bcy = c \nonumber\]

Since \(a|bc\), the left hand side is divisible by \(a\), and so is the right hand side.

Euclid’s lemma is so often used, that it will pay off to have a few of the standard consequences for future reference.

Theorem 2.7 Cancellation Theorem

Let \(\gcd (a, b) = 1\) and \(b\) positive. Then \(ax = _{b} ay\) if and only if \(x = _{b}y\).

Proof

The statement is trivially true if \(b = 1\), because all integers are equal modulo 1.

If \(ax = _{b} ay\), then \(a(x-y) = _{b} 0\). The latter is equivalent to \(b|a(x-y)\). The conclusion follows from Euclid’s Theorem. Vice versa, if \(x = _{b} y\), then \((x-y)\) is a multiple of \(b\) and \(a(x-y)\) is a multiple of \(b\).

Used as we are to cancellations in calculations in \(\mathbb{R}\), it is easy to underestimate the importance of this result. As an example, consider solving \(21x = _{35} 21y\). It is tempting to say that this implies that \(x = _{35} y\). But in fact, \(\gcd (21, 35) = 7\) and the solution set is \(x = _{5} y\), as is easily checked. This example is in fact a special of the following corollary.

Corollary 2.8

Let \(\gcd (a, b) = d\) and \(b\) positive. Then \(ax = _{b} ay\) if and only if \(x = _{b/d} y\).

Proof

Again the statement is equivalent to \(b|a(x-y)\). But now we can divide by \(d\) to get \(\frac{b}{d}|\frac{a}{d} (x-y)\). Now we can apply the cancellation theorem.

Corollary 2.9

Let \(\gcd (a, b) = 1\) and \(b\) positive. If \(a|c\) and \(b|c\) then \(ab|c\).

Proof

We have \(c = ax = by\) and thus \(ax =_{b} 0\). The cancellation theorem implies that \(x = _{b} 0\).

Proposition 2.10

\(ax = _{m}c\) has a solution if and only if \(\gcd (a, m)|c\).

Proof

By Definition 1.5, \(ax = _{m} c\) means \(ax+my = c\) for some \(y\), and the result follows from Bezout.

Corollary 2.11

For any \(n \ge 1\), if \(p\) is prime and \(p| \prod_{i=1}^{n} a_{i}\), then there is \(j \le n\) such that \(p|a_{j}\).

Proof

We prove this by induction on \(n\), the number of terms in the product. Let \(S(n)\) be the statement of the Corollary.

The statement \(S(1)\) is: If \(p\) is prime and \(p|a_{1}\), then \(p|a_{1}\), which is trivially true.

For the induction step, suppose that for any \(k > 1\), \(S(k)\) is valid and let \(p| \prod_{i=1}^{k+1} a_{i}\). Then,

\[p| ((\prod_{i=1}^{n} a_{i}) a_{k+1}) \nonumber\]

Applying Euclid's Lemma, it follows that,

\[\begin{array} {ccc} {p| \prod_{i=1}^{n} a_{i}}&{\mbox{or, if not, then }}&{p | a_{k+1}} \end{array} \nonumber\]

In the former case \(S(k+1)\) holds because \(S(k)\) does. In the latter, we see that \(S(k+1)\) also holds.

Corollary 2.12

If \(p\) and \(q_{i}\) are prime and \(p| \prod_{i=1}^{n} q_{i}\), then there is \(j \le n\) such that \(p = q_{j}\).

Proof

Corollary 2.11 says that if \(p\) and all \(q_{i}\) are primes, then there is \(j \le n\) such that \(p|q_{j}\). Since \(q_{j}\) is prime, its only divisor are 1 and itself. Since \(p \ne 1\) (by the definition of prime), \(p = q_{j}\).