If you find any mistakes, please make a comment! Thank you.

Using the principle of mathematical induction to show divisibility II

Solution: The $n$-th proposition is
P_n: \quad 36 \text{ divides } 7^n-6n-1.
$$ Clearly, $P_1$ is true because $7^1-6\cdot 1-1$ is zero which is divisible by any nonzero integer. We have the induction basis.

Now we assume $P_n$ is true, that is $36$ divides $7^n-6n-1$. We would like to show $P_{n+1}$ is true based on $P_n$. Note that we have
\end{equation} Since $36$ divides $7^n-6n-1$ by $P_n$, we have $36n+7\big(7^n-6n-1\big)$ is divisible by $36$. By \eqref{eq:1-7-1}, we conlude that $7^{n+1}-6(n+1)-1$ is divisible by 36. Therefore $P_{n+1}$ is true if $P_n$ is true. By the principle of mathematical induction, we make the conclusion that $P_n$ is true for all positive integers $n$.

Leave a Reply

Close Menu