Can it be shown that



> 
> There are finitely many positive integers $n$ that can't be expressed as
> 
> 
> $$n=a+b$$
> 
> 
> for any composite integers $a$ and $b$ relatively prime to each other?
> 
> 
> 


<http://oeis.org/A096076> is the sequence, *"Not the sum of two relatively prime composite numbers"*.
It's given as


$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 28, 30, 32, 36, 38, 40, 42, 45, 48, 50, 54, 56, 60, 66, 70, 72, 78, 80, 84, 90, 96, 105, 108, 110, 120, 126, 132, 138, 140, 150, 180, 210.$


It says,
"Max Alekseyev showed that this sequence is finite; proof completed by several people to show that the list is complete."


No proof is given, nor any link to a proof.


How can we approached this problem? Are there any reference or related problem?




---


To understand, I construct below problem


There are infinitely many $n\in\mathbb{Z}\_+$ which can **not** be written as $n=2u+3v$ where $u,v \in\mathbb{Z}\_+$ with $\gcd(u,v)=1$?


$n=\{1,2,3,4,6,10,\cdots\}$


Or there are only $\{1,2,3,4,6,10\}$?




---


I already posted both problem on maths stack exchange, link are given below


$n=a+b$, [Link for 1st problem](https://math.stackexchange.com/q/3556923/647719)


$n=2u+3v$, [Link for 2nd problem](https://math.stackexchange.com/q/3566296/647719)


Thanks in advance for your advice, solution, comment.



Not the sum of two relatively prime composite numbers
Following fedja's comment, the number of decomposition $n=a+b$ with $\gcd(a,b)=1$ equals $\varphi(n)$. Among these, there are at most $2\pi(n)$ decompositions in which $a$ or $b$ is prime, hence $n$ has a suitable decomposition when $\varphi(n)>2\pi(n)$. Now the well-known explicit lower bounds for $\varphi(n)$ and upper bounds for $\pi(n)$ imply an explicit finite list of exceptions. For more details, see the relevant Wikipedia articles ([link1](https://en.wikipedia.org/wiki/Euler%27s_totient_function) and [link2](https://en.wikipedia.org/wiki/Prime-counting_function)), or Rosser-Schoenfeld: Approximate formulas for some functions of prime numbers (1961).


**Added.** By (3.6) and (3.42) in the paper of Rosser and Schoenfeld, the inequality $\varphi(n)>2\pi(n)$ holds as long as
$$e^\gamma\log\log n+\frac{2.51}{\log\log n}<\frac{\log n}{2.52}.$$
In particular, $\varphi(n)>2\pi(n)$ holds for $n>10^7$.


