Number Theory • Topic 2

Divisibility

Divisibility is the study of how integers break down into smaller integer components.

Definition

Definition (Divisibility)

Let

a

and

b

be integers with

a \neq = 0

. We say $a$ divides $b$ (written

a ∣ b

) if there exists an integer

k

such that

b = ak

Transitivity: If $a ∣ b$ and $b ∣ c$ , then $a ∣ c$ .
Linearity: If $a ∣ b$ and $a ∣ c$ , then $a ∣ (b x + cy)$ for any integers $x, y$ .
Magnitude: If $a ∣ b$ and $b \neq = 0$ , then $∣ a ∣ \leq ∣ b ∣$ .
Reflexivity: $a ∣ a$ for all $a \neq = 0$ .
Anti-symmetry: If $a ∣ b$ and $b ∣ a$ , then $a = \pm b$ .

Theorem (Division Algorithm)

For any integers

a

and

b

with

b > 0

, there exist unique integers

q

(quotient) and

r

(remainder) such that:

a = b q + r, 0 \leq r < b

Exercise (Problem 1)

Prove that if

n

is an integer, then

n (n + 1) (2 n + 1)

is divisible by 6.

Exercise (Problem 2)

Let

a, b, c

be integers such that

a + b + c

is divisible by 6. Prove that

a^{3} + b^{3} + c^{3}

is also divisible by 6.

Exercise (Problem 3)

Find all positive integers

n

such that

n + 1

divides

n^{2} + 1