We have $504 = 2^3 \cdot 3^2 \cdot 7$.

a) $\Rightarrow$ b). First we prove that $(n, 5) = 1$. If $(n, 5) \neq 1$ then $n = 5k$.
The sequence $(5m + 2)_{m \ge 1}$ is an arithmetic sequence with ratio 5. Its first term being coprime with the ratio, from Dirichlet's Theorem it follows that the sequence contains infinitely many primes. Then, there exists a prime $p$ such that $p = 5m + 2$ and $p > n$. As $(p, n) = 1$ it follows that $p^6 \equiv 1 \pmod n$, i.e., $n \mid (5m + 2)^6 - 1$. As $5 \mid n$ and $(5m + 2)^6 = M_5 + 2^6$, we get that 5 divides 63, absurd!
As $(n, 5) = 1$, according to the hypothesis $5^6 \equiv 1 \pmod n$, i.e. $n \mid (5^6 - 1)$.
But $5^6 - 1 = (5^3 - 1)(5^3 + 1) = (5 - 1)(5^2 + 5 + 1)(5 + 1)(5^2 - 5 + 1) = 4 \cdot 31 \cdot 6 \cdot 21 = 2^3 \cdot 3^2 \cdot 7 \cdot 31$, hence $n \mid 2^3 \cdot 3^2 \cdot 7 \cdot 31$ (1)
From (1) one can notice that $(n, 11) = 1$, hence $11^6 \equiv 1 \pmod n$, i.e., $n \mid (11^6 - 1)$. But $11^6 - 1 = (11^3 - 1)(11^3 + 1) = (11 - 1)(11^2 + 11 + 1)(11 + 1) \cdot (11^2 - 11 + 1) = 10 \cdot 133 \cdot 12 \cdot 111$, therefore
$$n \mid 2^3 \cdot 3^2 \cdot 5 \cdot 7 \cdot 19 \cdot 37 \quad (2)$$
From (1) and (2) it follows that $n \mid 2^3 \cdot 3^2 \cdot 7$, i.e., $n \mid 504$.

b) $\Rightarrow$ a). Let $x \in \mathbb{Z}$. Then $x^6 - 1 = (x^2 - 1)(x^4 + x^2 + 1)$. We have:
1. if $(x, 2) = 1$ then $x - 1$ and $x + 1$ are consecutive even numbers, hence $2^3 \mid x^6 - 1$;
2. if $(x, 7) = 1$, from Fermat's Theorem we obtain $7 \mid x^6 - 1$;
3. if $(x, 3) = 1$ then $x = 3k \pm 1$. Obviously $3 \mid x-1$ or $3 \mid x+1$, hence $3 \mid x^2-1$. We also have
$$x^4 + x^2 + 1 = (3k \pm 1)^4 + (3k \pm 1)^2 + 1 = (M_3 + 1) + (M_3 + 1) + 1 = M_3, \text{ i.e.,} \\ 3 \mid x^4 + x^2 + 1.$$
It follows that for $(x, 3) = 1$ we have $3^2 \mid x^6 - 1$.
If $n \in \mathbb{N}$, $n \ge 2$ and $n \mid 504$, then $n = 2^a \cdot 3^b \cdot 7^c$ with $a \in \{0, 1, 2, 3\}$, $b \in \{0, 1, 2\}$, $c \in \{0, 1\}$ and $a, b, c$ not all of them 0. From the three statements above it follows that for all integer $x$ coprime with $n$ we have $n \mid x^6 - 1$, i.e. $x^6 \equiv 1 \pmod n$.