Browse Questions

# For every positive integer $n$, prove that $7^n-3^n$ is divisible by 4.

We can write
$P(n) : 7^n-3^n$ is divisible by 4.
We note that
$P(1) : 7^1-3^1=4$ which is divisible by 4. Thus $P(n)$ is true for $n=1$
Let $P(k)$ be true for some natural number $k$
i.e., $P(k) : 7^k-3^k$ is divisible by 4.
We can write $7^k-3^k=4d$, where $d \in N$.
Now, we wish to prove that $P(k+1)$ is true whenever $P(k)$ is true.
Now, $7^{(k+1)}-3^{(k+1)}=7^{(k+1)}-7.3^k+7.3^k-3^{(k+1)}$
$\qquad \qquad \qquad \qquad \: \: \: = 7(7^k-3^k)+(7-3)3^k=7(4d)+(7-3)3^k$
$\qquad \qquad \qquad \qquad \: \: \: = 7(4d)+4.3^k=4(7d+3^k)$
From the last line, we see that $7^{(k+1)}-3^{(k+1)}$ is divisible by 4. Thus $P(k+1)$ is true when $P(k)$ is true. Therefore, by principle of mathematical induction the statement is true for every positive integer $n$.