Thursday, September 1, 2016

Numbers as sum of two relatively prime composite numbers



It is not hard to prove by analytical method the existence of a positive integer $n$ such that for all integers $m > n$ the following assertion is true:




There exist two positive integers $a$ and $b$ with $a+b = m$ such that $a$ and $b$ are both composite and they are relatively prime, i.e., the g.c.d. of $a$ and $b$ is $1$.



My question is if someone knows the smallest value of $n$ such that this is satisfied for all $m > n$ (not just numerical evidence, a claim that comes with a proof). Maybe there is a reference where this problem is discussed?


Answer



I suspect that all $m>210$ can be written as sum of two coprime composites. One easily verifies the claim, for $210

Let $a$ range over the $\phi(m)$ numbers coprime to and below $m$ and let $b=m-a$. Then we have $m=a+b$ with coprime summands. We need to subtract the at most $\pi(m)+1$ cases where $a$ is prime or $a=1$, and also the up to $\pi(m)+1$ cases where $b$ is prime or $b=1$. Thus if $\phi(m)>2\pi(m)+2$, we can write $m$ as sum of coprime composites.
Actually, the $\omega(m)$ prime divisors of $m$ are already forbidden for $a$ and $b$ as we picked them coprime to $m$. Thus a sufficient condition is
$$ \phi(m)+2\omega(m)>2\pi(m)+2$$
or less strict

$$\phi(m)>2\pi(m) $$
With $\pi(m)<\frac{m}{\ln m-4}$ for $m\ge 55$ [Rosser, Barkley (1941). "Explicit Bounds for Some Functions of Prime Numbers". American Journal of Mathematics 63 (1): 211–232] we want to show
$$\prod_{p\mid m}\left(1-\frac1p\right)=\frac{\phi(m)}{m}>\frac1{\ln m-4}$$
or
$$\prod_{p\mid m}\left(1+\frac1{p-1}\right)<\ln m-4$$
If $m\ge30030$ then the RHS is $>6.3$ so that we need at least $10$ primes on the left (the product with the nine smallest primes is $\approx 6.1$).
Thus we need $m\ge 6469693230$, which makes $\ln m-4>18.59$.
As the product on the left over the primes $p<30000$ is $\approx 18.37$, we conclude that $m$ must be at least as large as the product of all primes $<30000$, that is $m>10^{12920}$ so that $\ln m-4>29740$.
We can continue this game for a while; for example with all primes $<10^6$ the left hand side reaches only $\approx 24.6$, while this forces us to make $m$ exceed the primorial of $10^6$, makeing the right hand side $>998480$. It should be straightforward to deal with the "large $m$" case, as the left hand side expands to a sum of reciprocals of just "a few" integers $

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...