Prove that if is greater than and divisible by , but not divisible by , then:
is the remainder when is divided by where is a natural number.
$\displaystyle \left(\frac{n}{2} + 1\right)^k - \left(\frac{n}{2} + 1\right) = \left(\frac{n}{2} + 1\right) \left\{\left(\frac{n}{2} + 1\right)^{k-1} - 1\right\} = \left(\frac{n}{2} + 1\right) \times \frac{n}{2} \times (\text{some number})$
It suffices to show $\displaystyle \left(\frac{n}{2} + 1\right) \times \frac{n}{2} = \frac{n(n+2)}{4}$ is divisible by n. But observe that n is an even number not divisible by 4, thus $\displaystyle 4 | n+2$ and hence $\displaystyle \frac{n(n+2)}{4}$ is divisible by n and so is the original expression.