Mathematical-Reasoning · Unit 6 · Video 2 · Interactive Practice

Why Divisibility Is Transitive: Building a Proof from Axioms, Definitions and One Constructed Integer

IKey Formulas

Formula	Name	Role in the proof
$m \mid n \iff (\exists q \in \mathbb{Z})(n = m \cdot q)$ , with $m \ne 0$	Definition of divides	Unpacks the hypothesis and confirms the conclusion
$b = a \cdot s$ and $c = b \cdot t$ , with $s, t \in \mathbb{Z}$	Hypothesis unpacked	Two letters, because the two multipliers need not be equal
$c = (a \cdot s) \cdot t = a \cdot (s \cdot t)$	Substitution, then the associative property	Regroups the product around $a$
$q = s \cdot t \in \mathbb{Z}$	The constructed integer (closure of $\mathbb{Z}$ )	Gives $c = a \cdot q$ , so $a \mid c$

Key Insight: An existential quantifier in the show part, such as $(\exists q \in \mathbb{Z})$ , signals the construction method: build the object from what is known.

IIFinding the Proof in a Know-Show Table

The table is filled from both ends: backward from $a \mid c$ to an $\exists q$ , then forward to construct $q$ .

Example Step 1

IIIConstructing $q = s \cdot t$

Regrouping $(a \cdot s) \cdot t$ as $a \cdot (s \cdot t)$ exhibits $c$ as $a$ times the integer $s \cdot t$ .

a 2 s 3 t 4

💡 The value $s = 0$ never occurs: it would make $b = a \cdot s = 0$ , and $b$ must be nonzero to act as the divisor in $b \mid c$ . The value $t = 0$ is allowed, and the same construction proves $a \mid 0$ .

IVQuiz Questions

Problem 1 · Name the Statement

Given: once the theorem “divisibility is transitive” is proved, the statement “if $a$ , $b$ , $c$ are nonzero integers, $d$ is an integer, and $a \mid b$ , $b \mid c$ and $c \mid d$ , then $a \mid d$ ” follows almost immediately by applying the theorem twice. Which term fits this statement?

✅ Correct! A corollary is a theorem that is easy to prove once another theorem has been proven. Two applications of transitivity prove this one.

❌ Not quite. An axiom is accepted as true without proof. This statement has a proof: apply the transitivity theorem twice.

❌ Close, but… a lemma is proven mainly to help prove some theorem. Here the dependence runs the other way: this statement is derived from the theorem, so it is a corollary.

❌ Not quite. A conjecture is believed true but not yet proved. This statement is proved by two applications of the theorem.

Show solution

First application. From $a \mid b$ and $b \mid c$ , with $a \ne 0$ and $b \ne 0$ , the theorem gives $a \mid c$ .

Second application. From $a \mid c$ and $c \mid d$ , with $a \ne 0$ and $c \ne 0$ , the theorem gives $a \mid d$ .

The statement follows almost immediately from a proven theorem, so it is a corollary. An axiom has no proof, a conjecture is not yet proved, and a lemma is proved in order to prove some later theorem.

Problem 2 · One Letter Too Few

Given: a student begins the proof with “Since $a \mid b$ and $b \mid c$ , there is an integer $q$ with $b = a \cdot q$ and $c = b \cdot q$ .” What is wrong with this step?

✅ Correct! Each use of the definition supplies its own integer, so the proof needs two letters,

s

and

t

❌ Not quite. With one letter the step covers only the integers whose two multipliers happen to be equal. In

2 \mid 6

and

6 \mid 24

the multipliers are

3

and

4

, and no integer

q

satisfies both

6 = 2 \cdot q

and

24 = 6 \cdot q

❌ Not quite. The definition asks only for an integer

q

. For example

3 \mid -6

, because

-6 = 3 \cdot (-2)

❌ Not quite. That reverses the definition. The statement

m \mid n

means

n = m \cdot q

, so

a \mid b

means

b = a \cdot s

for some integer

s

Show solution

The definition of divides is used twice, and each use introduces its own integer:

a \mid b \ \Rightarrow\ (\exists s \in \mathbb{Z})(b = a \cdot s), \qquad b \mid c \ \Rightarrow\ (\exists t \in \mathbb{Z})(c = b \cdot t).

Nothing in the hypothesis says $s = t$ . In the video's first example, $6 = 2 \cdot 3$ and $24 = 6 \cdot 4$ , so $s = 3$ and $t = 4$ . Writing both equations with one letter $q$ would prove the theorem only for the special integers where $s = t$ .

The correct step is: there exist integers $s$ and $t$ with $b = a \cdot s$ and $c = b \cdot t$ .

Problem 3 · Run the Construction

Given: $a = -3$ , $b = 12$ and $c = -60$ , so $a \mid b$ and $b \mid c$ . Follow the proof: find the integers $s$ and $t$ with $b = a \cdot s$ and $c = b \cdot t$ , then the constructed integer $q$ with $c = a \cdot q$ .

What are $s$ and $t$ ?

What is the constructed $q$ ?

✅ Correct!

q = s \cdot t = (-4) \cdot (-5) = 20

, and indeed

-60 = (-3) \cdot 20

❌ Check the signs.

(-3) \cdot 4 = -12

, not

12

, and

12 \cdot 5 = 60

, not

-60

❌ Close, but…

s = -4

is right, since

(-3) \cdot (-4) = 12

. But

12 \cdot 5 = 60

, while

c = -60

❌ Not quite. These are swapped:

(-3) \cdot (-5) = 15

, not

12

. The integer

s

links

a

b

, and

t

links

b

c

❌ Check $s$ and $t$ . Solve

12 = (-3) \cdot s

and

-60 = 12 \cdot t

❌ Check the sign. The product of two negative integers is positive. Also

(-3) \cdot (-20) = 60

, not

-60

❌ Not quite. That is

s + t

. The regrouping

c = a \cdot (s \cdot t)

builds

q

as the product, and

(-3) \cdot (-9) = 27

❌ Not quite. That is

t

, the multiplier from

b

c

. The multiplier from

a

c

s \cdot t

, and

(-3) \cdot (-5) = 15

❌ Check $q$ . The proof builds

q = s \cdot t

Show solution

Unpack the hypothesis. $12 = (-3) \cdot s$ gives $s = -4$ , and $-60 = 12 \cdot t$ gives $t = -5$ .

Substitute and regroup.

-60 = 12 \cdot (-5) = \big((-3) \cdot (-4)\big) \cdot (-5) = (-3) \cdot \big((-4) \cdot (-5)\big) = (-3) \cdot 20.

Construct $q$ . $q = s \cdot t = 20$ , an integer, so $-3 \mid -60$ .

Problem 4 · The Construction Method, Transferred

Given: $a$ and $b$ are integers with $a \ne 0$ , and $m \mid n$ means $n = m \cdot q$ for some integer $q$ (where $m \ne 0$ ). To prove “if $a \mid b$ , then $a^2 \mid b^2$ ,” the show part is $(\exists q \in \mathbb{Z})(b^2 = a^2 \cdot q)$ , and the hypothesis gives an integer $s$ with $b = a \cdot s$ . Which $q$ does the construction method build?

✅ Correct!

b^2 = (a \cdot s)(a \cdot s) = a^2 \cdot s^2

, and

s^2

is an integer by closure.

❌ Not quite.

q = s

is the integer for

a \mid b

, not for

a^2 \mid b^2

. With

a = 2

and

s = 3

b^2 = 36

but

a^2 \cdot s = 12

❌ Not quite. Squaring is not doubling. With

a = 2

and

s = 3

b^2 = 36

but

a^2 \cdot 2s = 24

❌ Close, but… this has one factor of

a

too many:

a^2 \cdot a \cdot s^2 = a^3 s^2

. With

a = 2

and

s = 3

that is

72

, not

b^2 = 36

Show solution

Backward. To prove $a^2 \mid b^2$ (note $a^2 \ne 0$ since $a \ne 0$ ), we must show $(\exists q \in \mathbb{Z})(b^2 = a^2 \cdot q)$ . The $\exists$ is the signal to construct $q$ .

Forward. Since $a \mid b$ , there is an integer $s$ with $b = a \cdot s$ . Substituting,

b^2 = (a \cdot s) \cdot (a \cdot s) = (a \cdot a) \cdot (s \cdot s) = a^2 \cdot s^2,

using the commutative and associative properties of multiplication.

Construct. $s^2 = s \cdot s$ is an integer because $\mathbb{Z}$ is closed under multiplication, so $q = s^2$ gives $b^2 = a^2 \cdot q$ and $a^2 \mid b^2$ .

Solved: 0 / 4

Why Divisibility Is Transitive: Building a Proof from Axioms, Definitions and One Constructed Integer

IKey Formulas

IIFinding the Proof in a Know-Show Table

IIIConstructing q=s⋅tq = s \cdot tq=s⋅t

IVQuiz Questions

IIIConstructing $q = s \cdot t$