5
$\begingroup$

According to this Wikipedia article, we know that an integer $n\; (\geq 2)$ is prime if and only if the polynomial congruence relation

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

holds for all integers $a$ coprime to $n$ (or even just for some such integer $a$, in particular for $a = 1$).

Then the Fermat Little Theorem says, $n$ is a probable prime if

$ a^n \equiv a \pmod{n} $

Inside the article it said $x$ should never be substituted by a number, so If we do so, then for primality testing of a number like $211$ we would have something like this as an example :

$ (2 + 3)^{211} \equiv 2^{211} + 3 \pmod{n} $

So can't we use the above equation for some reduction in modular exponentiation?

1 Answers 1

6

If you have $n=211$, you can use it, but you have to know your $n$ is prime. And then you would have $(2+3)^{211} \equiv 2^{211} + 3 \pmod{211}$

For a prime $p$ it is always true that: $ (x+y)^p \equiv x^p + y^p\pmod{p} $

But if you are looking for the explanation of the test, you should not do that. The part that says you shouldn't substitute $x$ means, that you should be looking at the polynomial $(x-a)^n$ which will be determined by its coefficients, i.e. if $f=(x-a)^n$ then it can be written also as a sum $f=\sum_{i=0}^{n} a_{i}x^{n}$ (if you expand the product), and you should be checking if $a_i \equiv 0 \pmod{n}$ for all $1 and $a_0\equiv a \pmod{n}$.