Congruence notation
 

I read about the AKS primality test. That algorithm uses the relation (x - a)^n = (x^n - a) mod (n, x^r - 1). What does it mean? I know that a=b mod c <=> c|a-b but the notation a=b mod (c,d) is new for me. Or is (n,x^r-1) just the greatest common divisor of n and x^r-1?

[QUOTE=meknowsnothing;107364]I read about the AKS primality test. That algorithm uses the relation (x - a)^n = (x^n - a) mod (n, x^r - 1). What does it mean?[/QUOTE]

Must be something going around. fetofs asked the same question earlier this month. The answers are pretty good.

[url]http://www.mersenneforum.org/showthread.php?t=8119[/url]