Thursday, 17 September 2015

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 ϕ(m) numbers coprime to and below m and let b=ma. Then we have m=a+b with coprime summands. We need to subtract the at most π(m)+1 cases where a is prime or a=1, and also the up to π(m)+1 cases where b is prime or b=1. Thus if ϕ(m)>2π(m)+2, we can write m as sum of coprime composites.
Actually, the ω(m) prime divisors of m are already forbidden for a and b as we picked them coprime to m. Thus a sufficient condition is
ϕ(m)+2ω(m)>2π(m)+2


or less strict
ϕ(m)>2π(m)

With π(m)<mlnm4 for m55 [Rosser, Barkley (1941). "Explicit Bounds for Some Functions of Prime Numbers". American Journal of Mathematics 63 (1): 211–232] we want to show
pm(11p)=ϕ(m)m>1lnm4


or
pm(1+1p1)<lnm4

If m30030 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 6.1).
Thus we need m6469693230, which makes lnm4>18.59.
As the product on the left over the primes p<30000 is 18.37, we conclude that m must be at least as large as the product of all primes <30000, that is m>1012920 so that lnm4>29740.
We can continue this game for a while; for example with all primes <106 the left hand side reaches only 24.6, while this forces us to make m exceed the primorial of 106, 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

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...