Prove that $(x^2−1) \bmod 8$ $\in \{ 0 , 3 , 7 \}, \forall x \in \mathbb{Z}$. It must be verified that for all $x \in \mathbb{Z}$ it holds that $x^2 - 1 \bmod{8} \in \{0, 3, 7\}$. First some definitions. Using the following theorem a definition for $\bmod$ is provided: 
Theorem. For all $a \in \mathbb{Z}$ and $d \in \mathbb{N}$ unique integers q, r exist satisfying $a = q \cdot d + r \wedge 0 \leq r <d$

The integers $q$, $r$ correspond to the quotient and remainder, respectively, of $a$, these being defined as: 
$a = (a / d) \cdot d + a \bmod d \wedge 0 \leq a \bmod d < d$

With $q = (a/d)$ and $r = a \bmod d$. To verify the claim I use induction. I use a brute force approach where I search for all numbers $x$ such that $x^2 - 1 \bmod 8 = 0$, $x^2 - 1 \bmod 8 = 3$ or $x^2 - 1 \bmod 8 = 7$. First I search for all $x$ such that $x^2 - 1 \bmod 8 = 0$. If $x^2 - 1 \bmod 8 = 0$ then 8 is a divisor of $x^2 - 1$, i.e.: $8 \mid x^2 - 1$. Now I search for some other $x$ such that 8 is a divisor of $x^2 - 1$. Let $f(x) = x^2 - 1$ and $8 \mid f(x)$ then $8 \mid f(x + a)$ for some $a \in \mathbb{N}$. I compute this a: 
$8 \mid f(x) = 8 \mid x^2 - 1 \implies 8 \mid (x + a)^2 - 1 = 8 \mid x^2 + a^2 + 2ax - 1 = 8 \mid x^2 - 1 + a^2 + 2ax$

The implication holds for e.g.: $a = 4$ since: 
$8 \mid x^2 - 1 + a^2 + 2ax \implies 8 \mid x^2 - 1 + 16 + 8x = 8 \mid f(x) \wedge 8 \mid 16 + 8x = true$

So it can be concluded that if $8 \mid f(x)$ then $8 \mid f(x + 4)$. In fact it may be concluded that if $8 \mid f(x)$ then $8 \mid f(x + 4k), \forall x \in \mathbb{Z} \wedge k \in \mathbb{N}$, since: 
$8 \mid (x + 4k)^2 - 1 = 8 \mid x^2 - 1 + 16k^2 + 8kx = 8 \mid f(x) \wedge 8 \mid 16k^2 + 8kx$

So it holds that $8 \mid f(x) \implies 8 \mid f(x + 4k)$. By inspection one finds that $8 \mid f(1) = 8 \mid 1^2 - 1 = 8 \mid 0 = true$ and so $f(x) \bmod 8 = 0$ for all $x \in \{1, 5, 9, 13, ...\}$. Since $f(x)$ is symmetric it holds that $f(-x) = f(x)$ and so it follows that $f(x) \bmod 8 = 0$ for all $x \in \{-1, -5, -9, -13, ...\}$.  Upon further inspection one finds that $8 \mid f(3) = 8 \mid 3^2 - 1 = 8 \mid 8 = true$ and so it follows that $x^2 - 1 \bmod 8 = 0$ for all $x \in \{3, 7, 11, 15, ...\}$ and all $x \in \{-3, -7, -11, -15, ...\}$ 
Next I search for all x such that $x^2 - 1 \bmod 8 = 3$, or equivalently $x^2 - 4 \bmod 8 = 0$. Using the same approach I find that $x^2 - 1 \bmod 8 = 3$ for all $x \in \{2, 6, 10, 14, ...\}$ and all $x \in \{-2, -6, -10, -14, ...\}$. Finally $x^2 - 1 \bmod 8 = 7$ for all $x \in \{0, 4, 8, 12, ...\}$ and $x \in \{0, -4, -8, -12, ...\}$. And so one concludes that for all $x \in \mathbb{Z}$ it holds that $x^2 - 1 \bmod{8} \in \{0, 3, 7\}$. 
This question comes from a course in discrete mathematics in computer science. I feel that my approach is overkill and that I'm doing something wrong and that there must be some cleverer way of solving the problem. If anyone can help with a better, cleaner, approach, or point out errors, it will be greatly appreciated :).

$$x^2-1=(x-1)(x+1)$$
If $x$ is even, $x-1$ and $x+1$ are both odd. The possibilities are then $7\times1$, $1\times3$, $3\times5$ and $5\times7$, which gives you $3$ or $7$.
If $x$ is odd, $x-1$ and $x+1$ are both even, and one of them is divisible by $4$, so the remainder is always $0$.
