For the sake of manually implementing the AKS primality test I've tried to simplify the following expression:
$$((x+a) ^n \bmod (x^r-1)) \bmod n $$
I have tested some values of $n$ and was always able to reduce this to $$a^n \bmod n + x^{n \bmod r}$$
It seems to work for all $ n < 15000 $ and for a few thousand $ n > 10 ^{10} $.
Is it possible to prove the formula $$((x+a) ^n \bmod (x^r-1)) \bmod n = a^n \bmod n + x^{n \bmod r}$$ for all $ n > 1 $ under the conditions $ n \neq p^q (p, q \in \mathbb{N})$, $a \le r \lt n$, $gcd(a, n) = 1$, $gcd(r, n) = 1$?
Let $$ n=10, \quad r=7, \quad a=1 $$ so $a\le r < n $ and $n\neq p^q$ where $p,q\in\mathbb{N}$ and $1 < n$ and $\gcd(a,n)=1, \gcd(a,r)=1$ as required.
Then the two expressions are
$$ \big((x+1)^{10}\bmod (x^7-1)\big)\bmod 10 $$ and $$ 1^{10} (\bmod 10)+ x^{10\bmod 7} $$
Let now $x=2$ then $$ \big(\underbrace{(2+1)^{10}\bmod (2^7-1)\big)}_{121}\bmod 10=1 $$ and $$ \underbrace{1^{10} (\bmod 10)}_{1}+ \underbrace{2^{10\bmod 7}}_{2^3=8}=9 $$
So I think that the assumption is not true.