Basic Theorems

These theorems and ideas that will be referred to in this section are presented here without proof now, but their proofs can be found here. It will be very helpful to the reader to keep these theorems in mind when reading through the proofs.

(Note: a|b will be taken to mean "a divides b")

Definition of Divisibility

If a and b are integers (with a ≠ 0) then a|b if b=ca for some integer c.

Remark: This theorem also shows that 0 is divisible by any real number (or any real number divides 0).

Theorem 1

Let a, b, and c be integers. If a| b and b|c then a|c.

Theorem 2

Let a, b, c, m, and n be integers. If c|a and c|b, then c|(ma+nb) for some m and n.

Theorem 3

Let a, b, c, and m be integers. If c|a and c|b, then c|(a+b), c| (a-b), and c|am.

Theorem 4

If a,b,c are integers and c≠ 0, then a|b if and only if ac|bc.

Euclid's Lemma

If a, b, and c are integers such that a|bc, and a and b are relatively prime then a|c.

Decimal Expansion

Another idea we will be using in the proofs is the fact that the digits of a positive integer x can be written as: a_n· · · a₃a₂ a₁a₀.

In this form a₀ is the digit in the one’s place, a₁ is the digit in the 10’s place, a₂ is the digit in the 100’s place, etc. In addition we can state that

x = a₀ + a₁(10) + a₂(100 )+ a₃(1,000)... + a_n(10,000)

= a₀ + a₁(10) + a₂(10² )+ a₃(10³)... + a_n(10ⁿ)