Theorem: If $b$ and $c$ are non-negative natural numbers, $m$ and $a$ are co-prime, $b = c\enspace\text{mod}\,\varphi(m)$, then $a^b = a^c\enspace\text{mod}\,m$.
Proof: Without loss of generality, suppose that $b>c$. Then $b=c+k\cdot\varphi(m)$ where $k$ is a natural number. $$a^b = a^{c+k\cdot\varphi(m)} = a^c\cdot (a^{\varphi(m)})^k = a^c \enspace\text{mod}\,m$$
Where we used Euler's theorem for $a^{\varphi(m)} = 1\enspace\text{mod}\,m$, and the fact that $$a'=a''\enspace\text{mod}\,m\,\land\,b'=b''\enspace\text{mod}\,m\implies a'b'=a''b''\enspace\text{mod}\,m$$
End of proof.
Suppose we want to calculate $a^{a^{320}}$ modulo $1000$. We can first calculate $a^{320}$ modulo $\varphi(1000)=400$ since $a$ and $1000$ are co-prime, using the theorem above.
To calculate $a^{320}$ modulo $400$, we can calculate $320$ modulo $\varphi(400)=160$, because, again, $400$ and $a$ are co-prime.
$$320 = 0\enspace\text{mod}\,160 \implies a^{320} = 1\enspace\text{mod}\,400 \implies a^{a^{320}}=a\enspace\text{mod}\,1000 $$
And because $a=531\enspace\text{mod}\,1000$, then
$$a^{a^{320}}=531\enspace\text{mod}\,1000 $$
This is equivalent to asking if there is always $m=n+p^2$ between $p^2$ and $(p+1)^2$ with $$m \equiv n+p^2 \not \equiv q+p^2 \equiv p\# \equiv 0 \pmod{2,3,...,p}$$
i.e. if there is always a prime $m=n+p^2$ between $p^2$ and $(p+1)^2$, which is Legendre’s conjecture restricted to the primes. Seems true, but probably an open problem.
Best Answer
To check that $x^{100} - 1$ is divisible by $1000$, it will suffice to check that it is divisible by $8$ and $125$. For each of these, you can use Euler's theorem, which will tell you that $x^{p^{k-1}(p-1)} \equiv 1 \pmod {p^k}$, where $p$ is a prime not dividing $x$. In this particular case, you have $x^{4} \equiv 1 \pmod{8}$ (so in particular $x^{100} \equiv 1 \pmod{8}$) and $x^{100} \equiv 1 \pmod{125}$.