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?

$\endgroup$

1 Answer 1

6
$\begingroup$

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<i<n$ and $a_0\equiv a \pmod{n}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .