Divisibility (Leaving Cert Mathematics): Revision Notes

If $a$ is divisible by $b$ that means that $a$ can be expressed as $bk$ where $k \in \mathbb{Z}$. For example, $15$ is divisible by $5$, because $15$ can be expressed as $5 \cdot 3$.

Prove by induction that $2^n$ is divisible by $2$ where $n \in \mathbb{N}$.

Prove for base case, $n=1$ :

$2$ is divisible by $2$ because you can express $2$ as $2 \cdot 1$.

Assume true for $n=k$ , that is, assume that $2^k$ can be expressed as $2 \cdot a$ where $a \in \mathbb{Z}$.

Prove true for $n=k+1$

We need to show that $2^{k+1}$ can be expressed as $2 \cdot k$ for some $k \in \mathbb{Z}$.

We can apply indices rules :

Observe that we have expressed $2^{k+1}$ as $2 \cdot a$ for some $a \in \mathbb{Z}$ because $2^k$ is an integer from our inductive hypothesis :

Prove by induction that $7^{2n+1}+1$ is divisible by $8$ for $n \in \mathbb{N}$.

Prove for base case, $n=1$ :

$344$ is divisible by $8$ because $344=8 \cdot 43$.

Assume true for $n=k$

for some $a \in \mathbb{Z}$.

Prove true for $n=k+1$

$7^{2(k+1)+1}+1$ has been expressed as $8 \cdot b$ for some $b \in \mathbb{Z}$. We assumed that $a$ is an integer, so $49a$ is also an integer (closed under multiplication). An integer subtracted by an integer is also an integer (closed under subtraction), so $(49a-6) \in \mathbb{Z}$.

$\therefore$ True for $n=k+1$, assuming that the proposition is true for $n=k$. Hence the proposition is true for all $n \in \mathbb{N}$.