How do I prove divisibility by 3 without induction?

Question

How do I prove that:

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

2. $3$ divides $n^3-n$, where $n$ is a natural number?

All without induction?(only number theory)

Thanks !

Answer 1

$4=1$ (mod 3) so the first reduces to $4^n-1=0$ (mod 3) and the second we have that $a^p=a$ (mod p) for any prime and any $a$ not divisible by $p$This is Fermat's Luttle Theorem. This $n^3-n=0$ (mod 3) if $3\not| n$ but if $3|n$ it should be clear that it still holds.

Answer 2

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$.