As I was playing around with Fermat's little theorem, I came up with another method to check if numbers are prime, if the remainder of the division of $n \over a$ was not $0$ for any integer a between $2$ and $\sqrt n$, then the number should be prime, right?

This seems to work well, it finds all of the same primes as Fermat's little theorem, and has the added advantage of not finding Carmichael numbers.

As the title states, is it correct to say an integer $n$ is prime if $n \bmod a \neq 0$ for all integers $a$ where $2 \leq a \leq\sqrt n$, and why?

  • 1
    $\begingroup$ Think about contrapositive - is it true that if $n$ is not prime then for some $a$ in specified integral we have $n\mod a\equiv 0$? $\endgroup$ – Wojowu Jun 25 '15 at 20:45
  • 3
    $\begingroup$ You also only need to check up to $\sqrt{n}$ $\endgroup$ – TomGrubb Jun 25 '15 at 20:45
  • $\begingroup$ @Wojowu Well yes, because for that $a$, $n$ is evenly divisible. But does this guarantee the number to be prime? $\endgroup$ – user530873 Jun 25 '15 at 20:51
  • 1
    $\begingroup$ If $n$ is evenly divisible by $a$ which isn't $1$ nor $n$, then $n$ must be composite (by the very definition), so not a prime. $\endgroup$ – Wojowu Jun 25 '15 at 20:53
  • 1
    $\begingroup$ @RobArthan Actually, this comes from an exam from a programming class. The question had to do with prime numbers and also had "Hint: a number $n$ is prime if it is not evenly divisible by all integers from $2$ to $n \over 2$". I was wondering the correctness of this statement, as I thought you had to use Fermat's little theorem to find prime numbers. My apologies if this anyhow came off "troll" like. $\endgroup$ – user530873 Jun 25 '15 at 22:45

Lemma 1. Let $n\in\mathbf N$, $n>1$. The smallest number $a>1$ that divides $n$ is prime.

Indeed, if $a$ is not prime, it has a non trivial divisor $b$, $1<b<a$, hence it isn't the smallest divisor $>1$ of $n$.

Lemma 2. If $n>1$ is not prime, it has a non-trivial divisor $ a\le\sqrt n$. . Either Proof: Let $a$ be any non trivial divisor of $n$. Either $a\le \sqrt n$, and the assertion is true, or $a>\sqrt n$, and the quotient $b=\dfrac na$ is another divisor and $b<\sqrt n$.

Corollary: If $a\in\mathbf N$ does not divide $n$ for all $1<a\le\sqrt n$, $\,n$ is prime. In other words, if $n\bmod a\neq 0$ for all $1<a\le\sqrt n$, $\,n$ is prime.

A fortiori, the conclusion is true if the condition is satisfied for all $\,1<a<\Bigl\lfloor\dfrac n2\Bigr\rfloor$, since $\,\sqrt n\le\dfrac n2$ for $n\ge 4$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.