(i) Prove that $7 \mid (a^6 − 1)$ for any integer $a$ such that $\gcd (a, 7) = 1$.
(ii) Prove that for any integer $a$ we have $7 \mid (a^7− a)$.
(i) We'll use the Division Algorithm:
For integers $a$ and $b \ge 1$ there exist integers $q$ and $r$ such that $a = bq + r$ where $0 ≤ r < b$.
Choosing $b=7$, then $0 \le r < 7$, and
$$\begin{align} a^6 -1 &= (7q + r)^6 -1 = 117649 q^6 + 100842 q^5 r + 36015 q^4 r^2 + 6860 q^3 r^3 + 735 q^2 r^4 + 42 q r^5 + r^6 - 1 \\ \\ & = 7 q (16807 q^5 + 14406 q^4 r + 5145 q^3 r^2 + 980 q^2 r^3 + 105 q r^4 + 6 r^5) + r^6 -1 \end{align}$$
The first part of this expression is divisible by 7, so we focus on the remaining $r^6 -1$.
The integer $r$ can take values 0,1,2,3,4,5,6. However, we are given $\gcd(a,7)=1$ which means $r=0$ is ruled out. To see this more clearly, $\gcd (a = 7q+0,7) = 7$.
- $r=1$ means $r^6-1=0$, which is divisible by 7.
- $r=2$ means $r^6-1=63$, which is divisible by 7.
- $r=3$ means $r^6-1=728$, which is divisible by 7.
- $r=4$ means $r^6-1=4095$, which is divisible by 7.
- $r=5$ means $r^6-1=15624$, which is divisible by 7.
- $r=6$ means $r^6-1=46655$, which is divisible by 7.
And so $7 \mid (a^6 − 1)$ for any integer $a$ such that $\gcd (a, 7) = 1$
(ii) Let's consider $(a^7-a)$
$$ (a^7 -a) = a(a^6-1) $$
We have already shown that $7 \mid (a^6 - 1)$ for $\gcd(a,7)=1$, so for $\gcd(a,7)=1$
$$7 \mid (a^7 -a)$$
We now need to consider the case when $\gcd(a,7) \neq 1$. The only other option for $\gcd(a,7)$ is 7, which means $a$ is a multiple of 7. That is $7 \mid a$. So in this case too, $7 \mid (a^6 - 1)$.
For both cases $\gcd(a,7)=1$ and $\gcd(a,7) \neq 7$, we have shown 7 divides $(a^7-a)$.