1. ## Proof

Prove that if $n$ is greater than $2$ and divisible by $2$, but not divisible by $4$, then:

$\frac{n}{2}+1$ is the remainder when $(\frac{n}{2}+1)^k$ is divided by $n$ where $k$ is a natural number.

2. Originally Posted by usagi_killer
Prove that if $n$ is greater than $2$ and divisible by $2$, but not divisible by $4$, then:

$\frac{n}{2}+1$ is the remainder when $(\frac{n}{2}+1)^k$ is divided by $n$ where $k$ is a natural number.
$\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 $\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 $4 | n+2$ and hence $\frac{n(n+2)}{4}$ is divisible by n and so is the original expression.