What is mod(a,b)?

Question

I was reading the AKS Primality Test. AKS. I could not understand the line :

$(x - a)^{n} = (x^{n} - a) \pmod{(n,x^{r}-1)}$

What is $\mod{(a,b)}$ in it ?

Answer 1

$(a,b)$ is a common notation for $\gcd(a,b)$. So the line $$(x-a)^n\equiv (x^n-a)\pmod{(n,x^r-1)}$$ means the same thing as $$(x-a)^n\equiv (x^n-a)\pmod{m}$$ where $m=\gcd(n,x^r-1)$.

Answer 2

You are looking at a congruence in the polynomial ring $\mathbb{Z}[x]$. For the integer $n \in \mathbb{Z}$ whose primality shall be determined, a specific value $r$ is determined, with the property that $n$ is prime if and only if the congruence

$$(x-a)^n \equiv x^n-a \pmod{I}$$

holds (for all $a$ in some sufficiently small set), where

$$I = (n, x^r-1)$$

is the ideal of $\mathbb{Z}[x]$ generated by the two elements $n$ and $x^r-1$.

Considering the ring $R = \mathbb{Z}/(n)$, that is equivalent to the congruence

$$(x-a)^n \equiv x^n - a \pmod{(x^r-1)}$$

in $R[x]$, which may be a more familiar form.