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

$\endgroup$
4
  • 4
    $\begingroup$ 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. $\endgroup$
    – Did
    Aug 21, 2011 at 11:19
  • 2
    $\begingroup$ 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}$. $\endgroup$ Aug 21, 2011 at 11:56
  • $\begingroup$ 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? $\endgroup$ Aug 21, 2011 at 13:10
  • $\begingroup$ @GerryMyerson any farther than the square root $\endgroup$
    – Templar
    Aug 21, 2011 at 17:23

4 Answers 4

13
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ ok, finally I got it, thanks $\endgroup$
    – Templar
    Aug 22, 2011 at 13:32
  • $\begingroup$ A bit late to the party, but I don't follow the logic in the second sentence, where you conclude that If $x \geq \sqrt{N}$, then $y \leq \sqrt{N}$. If $x \geq \sqrt{N}$ and $xy = \sqrt{N}\sqrt{N}$, then this implies that $xy = \sqrt{N}\sqrt{N} \geq x \sqrt{N}$, i.e. that $\sqrt{N} \geq x$, which can only simultaneously be true with our assumption if $x = \sqrt{N}$. I don't see how we arrive at the conclusion that $y \leq \sqrt{N}$. $\endgroup$ Sep 26, 2022 at 13:57
  • 1
    $\begingroup$ @AleksandrH: If $\color{#C00}{xy=N}$ and $\color{#090}{x\ge\sqrt{N}}$, then $y=\frac{\color{#C00}{xy}}{\color{#090}{x}}\le\frac{\color{#C00}{N}}{\color{#090}{\sqrt{N}}}=\sqrt{N}$. $\endgroup$
    – robjohn
    Sep 26, 2022 at 16:44
  • $\begingroup$ @robjohn Awesome, thanks for clarifying! $\endgroup$ Sep 26, 2022 at 17:49
6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I don't really understand :/ if c=xy why c>xy and how xy >= aa if x and y are bigger than a? it should be xy>aa? $\endgroup$
    – Templar
    Aug 21, 2011 at 11:34
  • $\begingroup$ You are right, this was a typo. Fixed. $\endgroup$
    – Gadi A
    Aug 21, 2011 at 11:44
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .