Why in Sieve of Erastothenes of $N$ number you need to check and cross out numbers up to $\sqrt{N}$? How it's proved?

Question

Why in Sieve of Erastothenes of $N$ number you need to check and cross out numbers up to $\sqrt{N}$? How it's proved?

For example if $N = 20$:

with $2$ we cross out:

2 4 6 8 10 12 14 16 18 20

with $3$:

3 9 15

and with $5$ we don't need to check because $10$, $15$ and $20$ are already crossed out and same with others biggers.

Answer 1

Suppose $xy=N=\sqrt{N}\sqrt{N}$. If $x\ge\sqrt{N}$, then $y = \frac{xy}{x} \leq \frac{N}{\sqrt{N}} = \sqrt{N}$, so $y\le\sqrt{N}$ and vice-versa. Thus, if $xy=N$, then one of $x$ or $y$ must be less than or equal to $\sqrt{N}$. This means that if $N$ can be factored, one of the factors must be less than or equal to $\sqrt{N}$.

This is the contrapositive of what Gadi A said, but sometimes, if a statement doesn't make sense to you, its contrapositive might.

To answer the question asked: if you've crossed out the multiples of all the numbers less than or equal to $\sqrt{N}$, all multiples of numbers greater than $\sqrt{N}$ will already be crossed out. This is because any number which is less than or equal to $N$ and is a multiple of a number greater than $\sqrt{N}$, will have a factor that is less than or equal to $\sqrt{N}$ and therefore will already be crossed out. (Of course, when we are speaking of multiples here we mean multiples of $2\times$ or more, as in the Sieve.)

Answer 2

Quite simple: Denote the root of N by a, so $a\cdot a\ge N$.Now, if a number $c$ factors $c=xy$ such that $x,y> a$ we have $c=xy> a\cdot a\ge N$.

In words: if a numbers has only factors bigger than the square root of N, it must be larger than N (and in other words - if a number smaller than N has a factor larger than the square root of N, it must also have a small factor).

Answer 3

If a number $N$ has a prime factor greater than $\sqrt{N}$ (but not equal to $N$ itself), then it also has a prime factor less than $\sqrt{N}$.

To see why, suppose $N$ has a prime factor $A$ not equal to $N$ itself. Then it has another factor $B$, so that $AB = N$. But it is impossible that $A>\sqrt{N}$ and $B \ge \sqrt{N}$, because then $AB > N$, so $N>N$.

So we must have $B < \sqrt{N}$.

Answer 4

HINT $\rm\ \ N = ab,\ a\le b\ \Rightarrow\ a^2 \le ab\ \Rightarrow\ a\le \sqrt{ab} = \sqrt{N}\:.$