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}$.
Re: Eratosthenes Sieve
Posted: Tue Dec 22, 2020 12:26 am
by Mehrab4226
Is $f(n)$ not divisible by any of the first n prime numbers or all of them? I guess any of them.
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.
Re: Eratosthenes Sieve
Posted: Tue Dec 22, 2020 1:10 am
by Mehrab4226
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
$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!
Re: Eratosthenes Sieve
Posted: Tue Dec 22, 2020 9:23 pm
by Mehrab4226
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.
$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.
Re: Eratosthenes Sieve
Posted: Wed Dec 23, 2020 3:23 pm
by Mehrab4226
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.
Re: Eratosthenes Sieve
Posted: Sat Dec 26, 2020 11:51 pm
by Anindya Biswas
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!
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!
.