Prove by induction: 5| (21^n+9)

Question

asked Sep 12, 2023 124k views

1 Answer

Baptiste Arnaud · Answer 1 · 2023-09-16T18:14:27+0000

It's kind of self-evident. Any power of 21 will have a 1 in the units place, and adding 9 to it makes it 0 and hence the number is divisible by 5.

To prove the claim by induction, first establish the base case. I assume
$n\in\Bbb N$ , so for
n=1 we have

21^1 + 9 = 21 + 9 = 30

and of course 30 = 5×6 is divisible by 5.

Assume the claim is true for
n=k , that
$5 \mid 21^k + 9$ . This means that for some integer
$\ell$ , we can write

$21^k + 9 = 5\ell$

Now the induction step: when
n=k+1 , we have

$21^(k+1) + 9 = \bigg(21*(21^k + 9) - 9*21\bigg) + 9 \\\\ ~~~~~~~~~~~~~~ = 21*5\ell - 9*20 \\\\ ~~~~~~~~~~~~~~= 5*(21\ell - 9*4)$

which is divisible by 5. QED