Lemmas on Divisibility

Lemma: Let a, b, and c be any integers. Assume that a divides both b and c. Then a also divides the sum b + c.

Proof: By the definition of divisibility, we can find integers x and y such that

b = ax and c = ay.

Therefore,

b + c = ax + ay = a(x + y).

Applying the definition again, we see that a also divides the sum.

Lemma: If a divides b, then a divides bc for any other integer c.

Proof: By the definition of divisibility, we can find an integer x such that

b = ax.

Therefore

bc = (ax)c = a(xc).

Applying the definition again, we see that a also divides the product.

These lemmas are applied, for example, in the proof that there are infinitely many primes. In that proof, one constructs an integer

N = P₁ P₂ ... P_M + 1.

Now suppose that P_i divides N. By the second lemma, P_i also divides the product. By the first lemma, it must also divide

1 = N - P₁ P₂ ... P_M.

Since no prime number can divide 1, this is impossible. Arguing by contradiction, we see that none of the primes P_i can divide N.

[Home Page] [Bioinformatics] [Mathematics] [Creative Efforts]

[HOME] [PREVIOUS] [NEXT] [UP] [DOWN]