# Math Help - Divisible or Remainder??

1. ## Divisible or Remainder??

Does 9 divide 5^(23) + 1? If not, what is the remainder?

How is this done?

2. Note $23 = 16+4+2+1$ (all powers of $2$). So $5^{23} = 5^{16}\cdot 5^4\cdot 5^2\cdot 5^1$.

$5^1 \equiv 5 \mod{9}$
$5^2 \equiv 7 \mod{9}$
$5^4 =\left(5^2\right)^2 \equiv 7^2 \equiv 4 \mod{9}$
$5^8 =\left(5^4\right)^2 \equiv 4^2 \equiv 7 \mod{9}$
$5^{16} =\left(5^8\right)^2\equiv 7^2 \equiv 4 \mod{9}$

Thus $5^{23}+1 \equiv 4\cdot 4\cdot 7\cdot 5+1 \equiv 3 \mod{9}$.