Can an odd number be evenly divisible by an integer bigger than its square root?

Question

I've seen this before on a programming website. It was an efficient algorithm to check if a number is prime. I've never seen any proof for this algorithm, so I'd like someone to provide it here. The algorithm operates as follows:

---

Step #1: Check if the number is divisible by 2. If yes, move on to step #2; Otherwise, it's not prime. (apart from 2, of course.)

Step #2: Check if the number is divisible by any odd number from 3 to the square root of the number. If it isn't, it's prime; Otherwise, it's not prime.

---

Example #1, Check if 55 is prime:

• Is 55 divisible by 2? no, move on.
• We search in the range ($3: \sqrt{55}$), which is ($3: 7.41$). So we check for every odd number from 3 to 7:
  1. Is 55 divisible by 3? No, move on.
  2. Is 55 divisible by 5? Yes. It's not prime.
  3. We don't continue the search since we have already found a number that divides 55.

---

Example #2, Check if 181 is prime:

• Is 181 divisible by 2? no, move on.
• We search in the range ($3: \sqrt{181}$), which is ($3: 13.45$). So we check for every odd number from 3 to 13:
  1. Is 181 divisible by 3? No, move on.
  2. Is 181 divisible by 5? No, move on.
  3. Is 181 divisible by 7? No, move on.
  4. Is 181 divisible by 9? No, move on.
  5. Is 181 divisible by 11? No, move on.
  6. Is 181 divisible by 13? No. 181 is prime.

---

So, I want a rigorous proof for the following statement:

Given an odd prime $n$, $n$ can never be evenly divisible by an integer $x$; for $x \geq \sqrt{n}$

Answer 1

What you want a proof of is false. $$ 15 = 3 \times 5 $$ and $5$ is larger than the square root of $15$. What is true is that if $n$ is not prime then it has a nontrivial factor no larger than its square root. To see that, write $$ n = ab $$ and note that you can't have both $a$ and $b$ greater than $\sqrt{n}$.

That is why you need only test the primes up to the square root to determine whether $n$ itself is prime.

Answer 2

Take, for example, $39$. The square root of $39$ is between $6$ and $7$ yet $39$ is divisible by $13$.

Answer 3

Obviously, an odd number greater than 1 is itself one of its divisors greater than the square root. For a proper divisor greater than the square root, consider the divisor 5 of 15.

Answer 4

What is true (and the algorithm relies on it) is this:

Lemma. $(i)\,$ Let $n$ be a positive integer. The smallest integer $p>1$ which divides $n$ is prime.

$(ii)\,$ If $n$ is not prime, $1 <p <\sqrt n$

The proof is easy:

$(i)$ if $p$ were not prime, it would have a non-trivial divisor; as this divisor would also be a divisor of $n$, $p$ would not be the smallest divisor $>1$ of $n$.

$(ii)$ let $m=\smash{\dfrac np}$; it is another divisor of $n$, and if we suppose $p>\sqrt n$, as $p<n$ by hypothesis, we have $$\;1< \dfrac np <\dfrac n{\sqrt{n}}=\sqrt n,$$ which is again in contradiction with the minimality of $p$.