7
$\begingroup$

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.

  • 3
    Because if N is composite, one of its factors is at most sqrt(N) hence one already encountered this decomposition of N when all the multiples of integers at most sqrt(N) have been crossed out.2011-08-21
  • 2
    You mean "square root of $N$", not "square of $N$" but everyone seems to realise that. Notice that if $N = p^2$ for a prime $p$, then the sieve method won't cross out $N$ until you try the prime $\sqrt{N}$.2011-08-21
  • 0
    Are you asking why you need to go all the way up to the square root? or are you asking why you don't have to go any farther than the square root?2011-08-21
  • 0
    @GerryMyerson any farther than the square root2011-08-21

4 Answers 4

7

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

  • 0
    ok, finally I got it, thanks2011-08-22
6

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

  • 0
    I don't really understand :/ if c=xy why c>xy and how xy >= a*a if x and y are bigger than a? it should be xy>a*a?2011-08-21
  • 0
    You are right, this was a typo. Fixed.2011-08-21
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}$.

2

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