Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
Suppose $xy=N=\sqrt{N}\sqrt{N}$. If $x\ge\sqrt{N}$, then $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.)
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).
HINT $\rm\ \ N = ab,\ a\le b\ \Rightarrow\ a^2 \le ab\ \Rightarrow\ a\le \sqrt{ab} = \sqrt{N}\:.$
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}$.
