Eratosthenes Sieve

For discussing Olympiad Level Number Theory problems
User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:
Eratosthenes Sieve

Unread post by Anindya Biswas » Tue Dec 22, 2020 12:00 am

Let $f:\mathbb{N}\rightarrow\mathbb{N}$ such that $f(n)$ is the smallest composite number that is not divisable by the first $n$ prime numbers. Prove that $f(n)$ is a perfect square for all $n\in\mathbb{N}$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Eratosthenes Sieve

Unread post by Mehrab4226 » Tue Dec 22, 2020 12:26 am

Is $f(n)$ not divisible by any of the first n prime numbers or all of them? I guess any of them.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Eratosthenes Sieve

Unread post by Anindya Biswas » Tue Dec 22, 2020 12:31 am

Mehrab4226 wrote:
Tue Dec 22, 2020 12:26 am
Is $f(n)$ not divisible by any of the first n prime numbers or all of them? I guess any of them.
Not divisable by all of the first $n$ primes.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Eratosthenes Sieve

Unread post by Mehrab4226 » Tue Dec 22, 2020 1:10 am

Ans:
$f(n)=((n+1)^{th}prime)^2$
proof that I am a bad solution writer:
Solution:
$Let, f(n)=x$,
Let, the prime numbers in ascending order be $p_1,p_2,p_3\cdots$
we claim $x=f(n)=p_{n+1}^2$
we know, $p_1,p_2,\cdots p_n \nmid x$
Let, $x = a_1 \times a_2$ where $a_i$ are primes not in {$p_1,p_2,p_3\cdots p_n$}[The reason we took two primes is for getting the smallest composite]
If any of $a_i,a_2 \neq p_{n+1}$ it will contradict the "minimality" of x

Thus $f(n)=p_{n+1}^2$[proved]
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Eratosthenes Sieve

Unread post by Anindya Biswas » Tue Dec 22, 2020 8:26 pm

Mehrab4226 wrote:
Tue Dec 22, 2020 1:10 am
Ans:
$f(n)=((n+1)^{th}prime)^2$
proof that I am a bad solution writer:
Solution:
$Let, f(n)=x$,
Let, the prime numbers in ascending order be $p_1,p_2,p_3\cdots$
we claim $x=f(n)=p_{n+1}^2$
we know, $p_1,p_2,\cdots p_n \nmid x$
Let, $x = a_1 \times a_2$ where $a_i$ are primes not in {$p_1,p_2,p_3\cdots p_n$}[The reason we took two primes is for getting the smallest composite]
If any of $a_i,a_2 \neq p_{n+1}$ it will contradict the "minimality" of x

Thus $f(n)=p_{n+1}^2$[proved]
Nice, you won! :)
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Eratosthenes Sieve

Unread post by Mehrab4226 » Tue Dec 22, 2020 9:23 pm

Yeah, but I couldn't explain it that well in my solution. Your's one in the USAMO was exceptional because it actually simplified things and did the proof.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Dustan
Posts:71
Joined:Mon Aug 17, 2020 10:02 pm

Re: Eratosthenes Sieve

Unread post by Dustan » Wed Dec 23, 2020 1:38 pm

Mehrab4226 wrote:
Tue Dec 22, 2020 1:10 am
Ans:
$f(n)=((n+1)^{th}prime)^2$
proof that I am a bad solution writer:
Solution:
$Let, f(n)=x$,
Let, the prime numbers in ascending order be $p_1,p_2,p_3\cdots$
we claim $x=f(n)=p_{n+1}^2$
we know, $p_1,p_2,\cdots p_n \nmid x$
Let, $x = a_1 \times a_2$ where $a_i$ are primes not in {$p_1,p_2,p_3\cdots p_n$}[The reason we took two primes is for getting the smallest composite]
If any of $a_i,a_2 \neq p_{n+1}$ it will contradict the "minimality" of x

Thus $f(n)=p_{n+1}^2$[proved]
Didn't understand the last part! Explain please.

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Eratosthenes Sieve

Unread post by Mehrab4226 » Wed Dec 23, 2020 3:23 pm

I know I am really bad at solution writing especially when they are number theory and combinatorics. I get what the solution is but cannot turn them into words :( .
Okay let me take a different approach,
We claim, $f(n)=p_{n+1}^2$
Let, $S=\{p_1,p_2,\cdots p_n\}$
let, $f(n) \neq p_{n+1}^2$
Then, $f(n)=a_1^{k_1} \times a_2^{k_2} \times \cdots a_m^{k_m}$ where $a_i<a_l$ if $i<l$ and $a_i$ not in $S$
If some $a_1 = p_{n+1}$ and $k_1>2$ then $f(n)>p_{n+1}^2$ contradicting the minimality of f(n)
Again if $a_1^{k_1}=p_{n+1}$ and all other $a_i^{k_i}=1$ then $f(n)$ won't be a composite. And if any other $a_i^{k_i} \neq 1 $, then $f(n)>p_{n+1}^2$ contradicting the minimality of $f(n)$. And if $a_i \neq p_{n+1}$ then $f(n)>p_{n+1}^2$ because $f(n)$ has to be composite with primes greater than $p_{n+1}$
Thus $f(n) = p_{n+1}^2$
Since we now know the function and we can clearly see that $f(n)$ is a square. The proof is done.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Eratosthenes Sieve

Unread post by Anindya Biswas » Sat Dec 26, 2020 11:51 pm

We can have a simplier argument, let's assume $f(n)<p_{n+1}^2$. Which implies $\sqrt{f(n)}<p_{n+1}$. It is well known that every composite number $a$ has a divisor $d$ such that $1<d\leq\sqrt{a}$. So, this means $f(n)$ has a divisor $d$ less than $p_{n+1}$ and greater than $1$, but this means $d$ has a prime divisor which is less than $p_{n+1}$, which is not permitted. so this is a contradiction!
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Eratosthenes Sieve

Unread post by Mehrab4226 » Sun Dec 27, 2020 6:39 pm

Anindya Biswas wrote:
Sat Dec 26, 2020 11:51 pm
We can have a simplier argument, let's assume $f(n)<p_{n+1}^2$. Which implies $\sqrt{f(n)}<p_{n+1}$. It is well known that every composite number $a$ has a divisor $d$ such that $1<d\leq\sqrt{a}$. So, this means $f(n)$ has a divisor $d$ less than $p_{n+1}$ and greater than $1$, but this means $d$ has a prime divisor which is less than $p_{n+1}$, which is not permitted. so this is a contradiction!
This is way easier than mine.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Post Reply