**Definition:** An integer b is** divisible **by a

non zero integer a if there is an integer c

such that ac = b.

**Note:** Saying that b is divisible by a is

equivalent to saying any of the following:

a is a **divisor** of b.

a **divides** b.

a is a ** factor ** of b.

**Notation: **aІb denotes that a divides b.

**Theorem 1: **For any integers a, b, and c:

**a. **aІ0, 1Іa, and aІa.

**b.** aІ1 if and only if a = ±1.

**c.** If aІb and cІd, then acІbd.

**d.** If aІb and bІc, then aІc.

**e.** aІb and bІa if and only if a = ±b.

**f. **If aІb and aІc, then aІ(bx + cy) for any

integers x and y.

**Some proofs of Theorem 1**

**Th 1a: **aІ0, 1Іa, and aІa.

Recall: aІb <=> ac = b for some integer c.

**Proof:** a·0 = 0, 1·a = a, and a·1 = a.

So it fol lows from the def . of “is

a divisor of” that aІ0, 1Іa, and aІa.

**Th 1b:** aІ1 if and only if a = ±1.

**Proof:** By the definition of “is a divisor of,”

aІ1 => ac = 1 for some integer c.

But the only integers whose product

is 1 are 1·1 and (-1)·(-1). So a = ±1.

On the other hand,

a = ±1 => a·(±1) = 1 => aІ1.

**Th 1d:** If aІb and bІc, then aІc.

**Scratch work:**

aІb and bІc => ap = b and bq = c

=> a(pq) = (ap)q = bq = c

=> aІc

**Th 1d:** If aІb and bІc, then aІc.

**Proof: **By the def. of “is a divisor of’” there

are integers p and q such that

aІb and bІc => ap = b and bq = c

=> a(pq) = (ap)q = bq = c

It now follows from the def. of “is a

divisor of that aІc.

**Th 1e:** aІb and bІa if and only if a = ±b.

**Sketch of Proof in one direction :**

** Greatest Common Divisor**

d is the **greatest common divisor **of

integers a and b if d is the largest integer

which is a common divisor of both a and b.

Notation: d = gcd(a, b)

**Example: **±2, ±7, and ±14 are the only

integers that are common divisors of both

42 and 56. Since 14 is the largest,

gcd(42, 56) = 14.

**Use of the gcd**

Reducing fractions

Not all fractions are easily reduced.

**The Division Algorithm**

For integers a and b, with b > 0, there

exist integers q and r such that

a = qb + r and 0 ≤ r < b.

**Euclidean Algorithm**

To find gcd(a, b) where b < a:

Divide b into a and let r_{1} be the remainder.

Divide r_{1} into b and let r_{2} be the remainder.

Divide r_{2} into r_{1} and let r_{3} be the

remainder.

**Continue to divide the remainder into the**

divisor until you get a remainder of zero.

**gcd(a, b) = the last nonzero remainder.**

**Find gcd(8633, 8051)**

**Theorem 2**

For any nonzero integers a and b, there

exist integers x and y such that

gcd(a, b) = ax + by.

Here’s how you use the Euclidean

Algorithm to write gcd(8633, 8051) as a

linear combination of 8633 and 8051.

• Use the Euclidean Algorithm to find

gcd(8633, 8051).

• Solve each division problem, except the

last one, for the remainder (r = a – bq) .

**Take note** of the quotient in each solution .

• Use these equations

in reverse order to find

the linear combination .