2

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?

user530873
  • 123
  • 1
    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$? – Wojowu Jun 25 '15 at 20:45
  • 3
    You also only need to check up to $\sqrt{n}$ – TomGrubb Jun 25 '15 at 20:45
  • @Wojowu Well yes, because for that $a$, $n$ is evenly divisible. But does this guarantee the number to be prime? – user530873 Jun 25 '15 at 20:51
  • 1
    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. – Wojowu Jun 25 '15 at 20:53
  • Why are you using $\frac n2$ and not the square root of n? – Amy B Jun 25 '15 at 21:38
  • @RobArthan thanks, I am just starting to use La Tex today so I am still figuring it out. I have a cheat sheet by my computer, but of course I am not at my computer now. I'm still curious about my question. – Amy B Jun 25 '15 at 21:46
  • @RobArthan Appreciate the help with LaTex. Thanks – Amy B Jun 25 '15 at 21:49
  • What actually happened was that you asked this question with$\frac{n}{2}$ in place of $\sqrt{n}$ throughout and then changed the question to make it marginally less trivial in response to comments and an answer. Your remarks about which primes your test finds and Carmichael numbers make me smell troll. – Rob Arthan Jun 25 '15 at 22:39
  • 1
    @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. – user530873 Jun 25 '15 at 22:45
  • Ok - thanks for the clarification and I apologise for my suspicious whinge. If you had provided that context, I think you would have been helped more quickly to the answer, which is that you do not need to use Fermat's little theorem to test for primality. See https://en.wikipedia.org/wiki/Prime_number for the definition of prime number and how to test for primality. – Rob Arthan Jun 25 '15 at 22:51
  • @user530873 The phrasing of the exam question has some small but substantial errors. It should say "a number $n \ge 2$ is prime if..." since $n=1$ satisfies the criterion without being prime. Also, it should be "by any integer between $2$ and $n/2$" rather than "by all integers from from $2$ and $n/2$". – Erick Wong Jun 26 '15 at 00:02

1 Answers1

1

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$.

Bernard
  • 175,478