<s>[INST] How do I prove divisibility by 3 without induction? How do I prove that:


*

*$3$ divides $4^n-1$, where $n$ is a natural number, and

*$3$ divides $n^3-n$, where $n$ is a natural number?
All without induction?(only number theory)
Thanks !
 [/INST] For the first one, use modulo arithmetic:
$$4^n - 1 \equiv 1- 1 \pmod 3\\
= 0 \pmod 3\\
\implies 3 | (4^n - 1)$$

For the second one, do a simple factorization:

$$n^3 - n = n (n^2 - 1) = (n-1)(n)(n+1)$$
and then notice that one  of $n-1, n, n+1$ must be divisible by $3$. This is a clever and very worthy trick : One and only one of $k$ consecutive positive integers must be divisible by $k$.
In fact, using similar arguments, we can deduce that $2$ divides $n^3 - n$ as well, and therefore since both $2$ and $3$ are divisors, then $6$ must also be a divisor of $n^3 - n$.

Just for completeness' sake: 
$$\begin{align}4^n &= (1 + 3)^n \\
&= 1 + 3\binom{n}{1} + 3^2\binom{n}{2} +\cdots+3^n\binom{n}{n}\\
&= 1 + 3\left(\binom{n}{1} + 3\binom{n}{2} +\cdots+3^{n-1}\binom{n}{n}\right)\end{align}$$
So we've proved that for integers $n \ge 1$, $4^n$ gives a remainder of $1$ when divided by $3$, i.e. $4^n \equiv 1 \pmod 4$.
</s>