Thank you for providing such great help. Thanks to math.stack site.
I would like to know a good method to test any three/four digit number prime or not? I don't want to go any C or Java or any computer related calculations. I want to know the method, which will help to us to know the number is prime or not? could you share the method.
I have drawn the formula of checking the given number is prime or not form Prof. Gandhi's lecture series. That is: In expansion of $(x-1)^n – (x^n-1)$, check all the coefficients are of the expansion is divisible by $n$, then $n$ is prime, otherwise not. I could not find proof of the cited above. However, it is working for some numbers, as I checked up to primes below 10000. Could you prove this, how $(x-1)^n – (x^n-1)$ is working and how it is related to $n$ and coefficients of expansion of $(x-1)^n – (x^n-1)$?
Best Answer
Method:1
Checking if all the coefficients are divisible by $n$ is equivalent to saying that $$n |(x-1)^n - (x^n-1)$$ for some $x \in Z$ and $n$ being a prime.
Using Fermat's Theorem which states that:$$x^p \equiv x \mod p$$ where $p$ is a prime and $x \in Z$.
Hence we have,
$(x-1)^n \equiv x-1 \mod n$ and $x^n \equiv x \mod n$
The result we get is:
$(x-1)^n - (x^n-1) \equiv x-1 -x+1 \equiv 0 \mod n$.
Hence proved.
Method:2
It is enough to prove that $$ n | {n \choose r}$$ for $0 \lt r \lt n$.
$${n \choose r} ={n! \over (n-r)!r!}$$
Observe that the denominator contains integers which are $\lt n$ for any $r$. Since, $n$ is a prime, none of the integers in the denominator divides it. Hence, there will be an $n$ left in the each term, which means it is divisible by $n$.
Hence Proved.
Other efficient methods for Primality testing:
There are other methods for primality test, which are far more efficient than the one you stated. Since, you are only interested in 3/4 digit numbers, you can apply sieve of eratosthenes which gives you all the primes in $O(N)$ time.
Your method takes $O(N)$ per primality test which is quite inefficient. Another method is to check whether the number has divisors and this can be done in $O(\sqrt N)$.
Another method is using probabilistic primality testing algorithm like Miller-Rabin primality test where the time complexity is reduced further.