Prove that there are infinitely natural numbers $n$ such that $n$ can't be written as a sum of two positive integers with prime factors less than $1394$.
Problem
Source: Iranian third round number theory P1
Tags: number theory, algebra
fractals
06.09.2015 23:56
I made a very similar problem in the past year... can Iran read things from my mind? Just kidding. The slightly harder (more annoying, definitely) version is where $n$ can't be written as a sum or a difference of these guys (or a product or a division, or even an exponentiation, but those last two cases are easily dispatched). In fact, every infinite arithmetic progression contains infinitely many of these guys (and there exist multitudes of infinite arithmetic progressions consisting of only these guys). I'll leave that as an exercise to the reader.
Lemma. For any negative integer $c$, there exists infinitely many primes $p$ such that $c$ is a quadratic nonresidue modulo $p$; that is, $\left(\frac{c}{p}\right) = -1$.
Proof:
We will choose a prime $p >> c$, so factor out any squares that divide $c$ and get rid of them. Now suppose that $c$ is squarefree. We let its factorization be $c = -p_1p_2\ldots p_k$, and factor the Legendre symbol as $\left(\frac{-1}{p}\right)\prod_{j = 1}^k \left(\frac{p_i}{p}\right)$. Now use Dirichlet's theorem along with selecting appropriate $p$ to win; the $-1$ term at the beginning always gives us enough freedom, even if one of the $p_i$ is two. There exist elementary ways to prove this as well, but I am too lazy to rederive those.
(Corollary. The same is true for negative rationals. Indeed, multiply them by appropriate squares to turn them into integers.)
Any number with primes factors strictly less than $1394$ can be written as $c_i x^2$ for $c_i \in C$, where $C$ is a finite set (with $2^a$ elements, if there are $a$ primes less than $1394$).
Then we want infinite $n$ which are not of the form $c_i x^2 + c_j y^2$ ever. But we can make $n$ have only one factor of $p_{i, j}$, where $p_{i, j}$ for every pair $(i, j)$ is chosen so that $-\frac{c_j}{c_i}$ is a nonresidue modulo $p$, and so that it is larger than all the $c_i$.
Because we know that $p_{i, j}|c_i x^2 + c_j y^2$ then implies that $p_{i, j}|x, y$, which means that it should not appear only once in the number.
Once we let $n$ have only one factor of each $p_{i, j}$ (we can make them distinct to avoid annoyances), we can now multiply it by anything relatively prime to those factors.
This in fact gives us an infinite arithmetic progression of such numbers!
SCLT
07.09.2015 10:42
We can bound the number of positive integers which are at most $m$ and which have prime factors less than $1394$ by the expression:
$x_m = (\log_{p_1}(m)+1) \cdot (\log_{p_2}(m)+1) \cdots (\log_{p_k}(m)+1)$, where $p_1,p_2, \dots, p_k$ are the primes less than 1394.
So the number of naturals which are at most $m$ and which are a sum of two such numbers is at most the square of the above quantity, $x_m^2$.
It follows that there are at least $m - x_m^2$ natural numbers at most $m$ which cannot be written as a sum of two numbers with prime factors less than 1394.
But as $m \rightarrow \infty$, so also $m - x_m^2 \rightarrow \infty$, so we get the result.
andria
07.09.2015 11:32
very nice solution by SCLT: we can generalize this problem by the same way: Let $k,s$ be two positive integer. prove that there are infinitely natural numbers $n$ such that $n$ can't be written as a sum of at most $s$ integers with prime factors less than $k$.
Garfield
25.03.2016 11:36
Not sure I am right but this is too simple solution.Let n be odd(it's exactly same if it's even),$n=x+y$ , $WLOG x>y$ so $x=n-y$ so $y\in1,2,3...\frac{n-1}{2}$.Now let $p_{1},p_{2}...p_{\frac{n-1}{2}}$ be primes greater then $1394$ and let $n\equiv \frac{n-1}{2} (modp_{\frac{n-1}{2}}), n\equiv \frac{n-3}{2} (modp_{\frac{n-3}{2}}), ...n\equiv 1 (mod p_{1})$ which is equivalent $n\equiv \ -1 (modp_{\frac{n-1}{2}}), n\equiv -3 (modp_{\frac{n-3}{2}}),.. n\equiv 1 (mod p_{1})$ so by $CRT$ there are infinetly many $n$ satysfing this condition so $x$ is always divisible by $p_{1}$ or $p_{2}$...or$ p_{\frac{n-1}{2}}$ so we are done.
FISHMJ25
30.05.2019 17:22
Garfield wrote: Not sure I am right but this is too simple solution.Let n be odd(it's exactly same if it's even),$n=x+y$ , $WLOG x>y$ so $x=n-y$ so $y\in1,2,3...\frac{n-1}{2}$.Now let $p_{1},p_{2}...p_{\frac{n-1}{2}}$ be primes greater then $1394$ and let $n\equiv \frac{n-1}{2} (modp_{\frac{n-1}{2}}), n\equiv \frac{n-3}{2} (modp_{\frac{n-3}{2}}), ...n\equiv 1 (mod p_{1})$ which is equivalent $n\equiv \ -1 (modp_{\frac{n-1}{2}}), n\equiv -3 (modp_{\frac{n-3}{2}}),.. n\equiv 1 (mod p_{1})$ so by $CRT$ there are infinetly many $n$ satysfing this condition so $x$ is always divisible by $p_{1}$ or $p_{2}$...or$ p_{\frac{n-1}{2}}$ so we are done. This is incorrect. You cant use CRT like that, first you fix $n$ and then you say it exists.
Arefe
03.08.2020 09:38
SCLT wrote:
We can bound the number of positive integers which are at most $m$ and which have prime factors less than $1394$ by the expression:
$x_m = (\log_{p_1}(m)+1) \cdot (\log_{p_2}(m)+1) \cdots (\log_{p_k}(m)+1)$, where $p_1,p_2, \dots, p_k$ are the primes less than 1394.
So the number of naturals which are at most $m$ and which are a sum of two such numbers is at most the square of the above quantity, $x_m^2$.
It follows that there are at least $m - x_m^2$ natural numbers at most $m$ which cannot be written as a sum of two numbers with prime factors less than 1394.
But as $m \rightarrow \infty$, so also $m - x_m^2 \rightarrow \infty$, so we get the result.
You can prove it easier : if $ k $ is the number of prime numbers less than $1394 $ , we have at most $ a^k $ numbers between $ 1 $ to $ 2^a $ such that every prime divisor of these numbers are less than $ 1394 $ . so we have at most $ a^{2k} $ good numbers between $ 1 $ to $ 2^a $ . and easy to see that $ 2^{a} - a^{2k} $ is going to infinite and the problem is solved $ \blacksquare $
Al3jandro0000
03.08.2020 12:06
Very closely to above. Consider the set $N$ of numbers $n$ such that $M\ge \nu_p(n)$ for every arbitrary prime indeed $$n=\prod_{i=1}^k p_i^{\nu_{p_i}(n)}$$So if we consider the greatest number in $N$ this must be $m=\prod_{i=1}^k p_i^M$. So clearly we have $\# N=\tau(m)=(M+1)^k$. So we have bounded the numbers such that are the sum of two elements from $N$ indeed is at most $\tau(m)^2$. Consider $f(x)=\frac{x}{\tau(x)^2}$. Notice that $f(mn)=f(m)f(n)$ for integers such that $\gcd(m,n)=1$. So consider a prime $p$ and so $f(p^e)=\frac{p^e}{2e+2}$ it's easy to see $f(p^e)$ becomes arbitrary larger for larger values of $e$. So $f(x)$ also becomes arbitrary larger and this means $x-\tau(x)^2$ becomes arbitrary larger and we are done.
Sprites
20.08.2021 20:40
Let $P_k=[p_1,p_2,p_3,....p_k]$ denote the primes less than $1394$ in increasing order and let $S_n$ be the set of numbers $j \in [1,2,3,4.......,2^n]$ all of whose factors belong to the set $P_k$.
Note that $|S_n| \le (n+1)^k$ by CRT.
It follows that there are at most $(n+1)^{2k}$ numbers which can be written as the sum of two numbers in $|S_n|$
If $n$ is large enough then $(n+1)^{2k}<2^{n-1}$, implying the result.