Let define $f:\mathbb{Z}^{+}\to \mathbb{Z}^{+}$ such that if $p \in \mathbb{P}$ and $p\mid n$ then $v_{p}(f(n)) = 1$, $f(1) = 1$. Lemma. Given non square-free $n$, then $n - f(n) \ge 2$ and the equality holds iff $n = 4$ Turn back to the problem, for contrary suppose there exists non square-free $n$ satisfy the condtion. Since $n \neq 4$ and $n \neq 1$, lemma 1 gives that $2 \le f(n) \le n - 2$. Now, just pick $m = f(n) + 1$. I will show that $n\mid m^{n} - 1$: Let $p \mid n$, according to LTE's lemma, we obtain $v_{p}(m^{n} - 1) = v_{p}(f(n)) + v_{p}(n) = 1 + v_{p}(n) > v_{p}(n)$. This concludes $n\mid m^{n} - 1$, which is a contradition. The stronger result is if $n$ is a square - free and $\gcd(n, \varphi(n)) = 1$ then $A = \{0^{n} - 1, 1^{n} - 1, 2^{n} - 1, \cdots (n - 1)^{n} - 1\}$ forms a complete residues modulo $n$ (The inverse problem is also true) kills the second part immediately.

Suppose $n$ is not squarefree and let $p^2 \mid n, \quad p>1$. Then necessarily, $1 < p < \left( \frac{n}{p} + 1 \right) < n$. So $\left( \frac{n}{p} + 1 \right)^n -1 \in A$. Let $p^k \mid \mid n$ and notice that $$\left( \frac{n}{p} + 1 \right)^n -1 \equiv (1)^n - 1 \equiv 0 \pmod{\frac{n}{p^k}}$$and $$\left( \frac{n}{p} + 1 \right) ^n -1 = \left( \frac{n}{p} \right) ^n + n \left( \frac{n}{p} \right) ^{n-1} + \ldots + n \left( \frac{n}{p} \right) + 1 - 1 \equiv \frac{n^2}{p} \equiv 0 \pmod{p^k}.$$ It follows that $n$ divides $\left( \frac{n}{p} + 1 \right)^n -1 \in A$, contradiction! So $n$ must be squarefree.