Prove: $(n \in \mathbb{Z}) \land (6|n) \Rightarrow (3|n)$

by daniel p pflager
nov 6, 2022
mathematics proofs

$\left[\exists(n \in \mathbb{Z}) \land (6|n) \right] \Rightarrow \left[\exists(k \in \mathbb{Z}) \land (n = 6k)\right]$

Suppose $n$ is an integer and suppose 6 divides n, then by (3) we know that there is an integer $k$ such that $a = dk$.

(4)

$\left[\exists(k \in \mathbb{Z}) \land (n = 6k)\right] \Rightarrow \left[\exists(k \in \mathbb{Z}) \land (n = 3 \cdot 2k)\right]$

If there exists an integer $k$ such that $n=6k$, and because $6$ may be written as $3\cdot 2$, then we know that (4) may be written $n = 3\cdot 2k$.

(5)

$\left[\exists(k \in \mathbb{Z}) \land (n = 3 \cdot 2k) \land (k' := 2k)\right] \Rightarrow \left[\exists(k \in \mathbb{Z}) \land (n = 3k')\right]$

If there exists an integer $k$ such that $n=3 \cdot 2k$, and because we are free to define a new constant $k' := 2k$, then we may rewrite (5) to say that there exists an integer $k'$ such that $a = 3k'$.

(6)

$\left[\exists(k' \in \mathbb{Z}) \land (n = 3k')\right] \Rightarrow \left[\exists(k' \in \mathbb{Z}) \land (3|n)\right]$

If there exists an integer $k'$ such that $n=3k'$, we can use (3) to rewrite (6) to say that there exists an integer $k'$, such that $3|n$.

(7)

$\left[(k := k') \land \exists(k \in \mathbb{Z}) \land (n = 6k)\right] \Rightarrow \left[\exists(k' \in \mathbb{Z}) \land (3|n)\right]$

Since we are free to redefine $k'$ to be $k$, we can rewrite (4) to say that there exists an integer $k$, such that $6|n$ which implies that there exists an integer $k'$ such that $3|n$.

(8)

$(6|n) \Rightarrow (3|n)$

By convention, we need not specify that there are two different constants, $k$ and $k'$, nor do we need to write them. In other words we may omit them, and read the conclusion as $6$ divides $n$ implies $3$ divides $n$. □

(9)