Eratóstenes

Number Theory Level 3

$2017$ is a prime number. To see that $2017$ is a prime number is sufficient to divide $2017$ by all prime numbers less than $2017$ . However, this condition is not necessary. We can divide $2017$ until a largest prime number to make sure that $2017$ is really a prime number. What is this largest prime number?

The answer is 43.

2 solutions

Zee Ell
Sep 18, 2016

Relevant wiki: Sieve of Eratosthenes

If N is a composite number, it can be written as:

$N = n_1 × n_2 \text { , where } n_1 , n_2 \in \mathbb {N} \text { and } 1 < n_1, n_2 < N$

Now, we can assume, that:

$n_1 ≤ n_2$

Then:

$n_1 ≤ \sqrt {N}$

In other words, it is enough to check the prime numbers which are smaller or equal to the (floor of the) square root of our original number ( p ≤ √N ) , if we want to factorise an integer (or just decide, whether it is prime or not).

In the case of 2017, we have to check the p primes, for which:

$p ≤ \lfloor \sqrt {2017} \rfloor$

$p ≤ 44$

The biggest prime number, which is smaller or equal to 44 is:

$\boxed {43}$

Tapas Mazumdar
Sep 21, 2016

Relevant wiki: Sieve of Eratosthenes

It is not necessary to divide the given number by all prime numbers smaller than it to check if it is prime or not.

This is the easiest way to prove my statement:

$\text{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_}$

Suppose $N$ be a number which is a perfect square. Then:

$N=k^{2}$ for some integer $k$ .

If we look into all the possible divisor pairs that give $N$ on multiplication, we'll find that,

$n_{1} < k < n_{2}$ for $n_{1} < n_{2}$ and $n_{1}\cdot n_{2} = N$ .

Thus from here we conclude that for every $n_{1}$ which is a divisor of a perfect square $N$ and less than its square root there exists another divisor $n_{2}$ which is greater than its square root such that $n_{1}\cdot n_{2} = N$ .

This approach can also be extended to numbers which are not perfect squares (such as $2017$ as given in the problem). This can be done by taking the floor function of its irrational square root (say $\left\lfloor \sqrt{N} \right\rfloor = m$ ) and check for divisibility by dividing it with all prime numbers, $p \le m$ .

Hence, for the problem above,

$\left\lfloor \sqrt{2017} \right\rfloor = 44$

Largest prime number, $p \le 44$ is $p=\boxed{43}$

Eratóstenes

The answer is 43.

2 solutions

0 pending reports