Problems & Puzzles: Puzzles

Puzzle 278.  The Rupinski's question

Andrew Rupinski sent the following puzzle around a variation of the Goldbach's conjecture. The main question is:

Is there an integer M such that every integer Z greater than M can be expressed as the sum of two relatively prime composite integers?

Rupinski claims to have a formal mathematical proof for the asked M value for Z odd. Regarding the even Z case he has just certain empirical evidence about the probable value of the M value ("the even case is somewhat more difficult")

Questions:

Do you want to try your own proofs or arguments about the M values of the Rupinski question?

Solution: Note: Important news should come from Rupinski soon. In the meanwhile...

Ken Wilke has proved that "for any odd integer Z > 105, Z can be expressed as the sum of two relatively prime composite integers". His proof is interesting because in a crucial part he uses the Bertrand's postulate. As Rupinski, he says that the even case "is definitely more difficult!". Here goes his proof:

Proof: Consider odd numbers (mod 30). We have:

For Z= = 1(mod 30),    Z = 4 +  (27 + 30(k - 1)) for any integer k > = 1.
For Z= = 3(mod 30),    Z = 8 +  (25 + 30(k -1)) for any integer k > = 1.
For Z= = 5(mod 30),    Z = 8 +  (27 + 30(k - 1)) for any integer k > = 1
For Z= = 7(mod 30),    Z = 16 + (21 + 30(k - 1)) for any integer k > = 1.
For Z= = 9(mod 30),    Z = 4 + (5 + 30k) for any integer k > = 0.
For Z= = 11(mod 30),  Z = 6 + (5 + 30k) for any integer k > = 0.
For Z= = 13(mod 30),  Z = 8 + (5 + 30k) for any integer k > = 0.
For Z= = 17(mod 30),   Z = 9 + (8 + 30k) for any integer k > = 0.
For Z= = 19(mod 30),   Z = 9 + (10 + 30k) for any integer k > =0.
For Z= = 21(mod 30),   Z = 16 + (5 + 30k) for any integer k > = 0.
For Z= = 23(mod 30),   Z = 14 + (9 + 30k) for any integer k > = 0.
For Z= = 25(mod 30),   Z = 16 + (9 + 30k) for any integer k > = 0.
For Z= = 27(mod 30),   Z = 32 + (25 + 30(k - 1)) for any integer k > = 1.
For Z= = 29(mod 30),   Z = 9 + (20 + 30k) for any integer k > = 0.

Thus, except for the case in which Z = = 15 (mod 30) for any odd integer Z > = 107, one can construct the desired representation by expressing Z in the form r + 30k for positive integers k and r with 0 < = r < = 14 and 16<= r <30 and k >= 1and then taking A to be the integer immediately following the equals sign for the corresponding residue class of Z (mod 30) and B to be the quantity in parentheses. Clearly B is composite since (B,30) > 1 for any valid choice of k corresponding to an odd integer Z > = 107. Also for Z = 105, by testing the  possible values of A and B, one can easily verify that either (A, B) > 1 or not both A and B are composite.

In the case where r = 15, we have Z= = 15 (mod 30) and Z = 49 +(26 + 30(k - 2)) for any integer k > = 2 which provides the desired representation all integers k except when k = = 3 (mod)7 when the quantity 26 + 30(k - 2) is divisible by 7. In this situation Z has the form Z = 105 + 210t for some integer t where t >=0. For Z = 105 this gives Z = 49 + 56 which does not satisfy the conditions of the problem.

In the following, we take Z = 210t + 105 for some positive integer t.  Now let p be the largest prime such that p^2 < Z = (105 + 210t). Then Z = p^2 + (210t + 105 - p^2) provides the required representation provided that p does not divide the quantity (210t + 105 - p^2). If p divides the quantity (210t + 105 - p^2), then p divides Z. By replacing p with another prime q such that q <  p and (q, Z) = 1, then  Z = q^2 + (210t + 105 -  q^2) provides the required representation.

It remains to show that q exists. The smallest case in which p divides Z occurs when t = 44. Here Z = 9345 = 3 * 5 * 7 * 89 when p = 89. We can take q = 53 so that z = 53^2 + 6536. More generally, by Bertrand’s Postulate there is a prime q such that (p-1)/2 < q < p-1. Clearly q does not divide Z since (q, p) = 1 and p divides Z. Thus when p divides Z, replace p by q where q is a prime in the interval (p-1)/2 < =  q <  p-1.

***

Jon Wharf wrote (16/8/04):

Rupinski conjecture: "Is there an integer M such that every integer Z greater than M can be expressed as the sum of two relatively prime composite integers?"

The requirements for the least M of the Rupinski conjecture are similar in principle for odd and even numbers. In both cases it is necessary to avoid partitioning Z in such a way that one of the factors of Z divides one partition as that factor will then also divide the other partition, destroying coprimality. Additionally we need to avoid prime numbers in either partition. These two conditions are sufficient to fulfill the required partition of Z.

So in order to achieve the required partition, pick the two smallest primes p & q which do not divide Z. (In the case of odd numbers of course we choose p=2). Our partition will be Z = ap + bq (a,b>0). Call the set of partitions defined by {(a,b)} which satisfy this, the chop of Z over p & q, Ch(Z,p,q).

Now Z == m mod p and Z == n mod q, so we need ap == n mod q and bq == m mod p. Clearly there will be a smallest a and b which satisfy these modularity constraints, a' < q and b' < p (unique in each case). Then a == a' mod q and b == b' mod p. Take z' = a'p + b'q and note that Z == z' mod pq. Then the members of Ch(Z,p,q) are given by a = a'+iq, b = b'+(k-i)p for i = 0 to k where k=(Z-z')/pq, to give k+1 partitions. Since z' < 2pq, #Ch(Z,p,q) = Z/pq - z'/pq +1 > Z/pq - 1

Many members of Ch(Z,p,q) can also be divisible by factors of Z. We need to establish a value of a which is coprime to Z (which automatically gives b also) and avoid a=1 or b=1. Taking Ch(Z,p,q) in increasing a, we will find that for each prime factor s of Z, divisibility by s will occur every s terms of Ch(Z,p,q). We are therefore seeking a chop set size sufficiently large that we must have at least one term remaining from this sieve not divisible by any prime factor of Z - we will say there are v such factors. The worst case of this sieve is given by the smallest v primes, and in this case by analogy with Bertrand's Postulate we must have an unsieved member provided we have w members, where w is twice the v'th prime. For completeness we should also eliminate the first and last members of the set, in case a' = 1or b' = 1, so we need w+2 members of the chop set.

Now suppose Z>= pq(w+3). Then #Ch(Z,p,q) > Z/pq-1 > w+2 and a Rupinski partition must exist.

For the Primorials, which are the hardest case (because p, q and w are forced to be larger relative to Z), this criterion is reached for Z=13# = 30030 > 9367 = 17*19*(2*13+3). For larger values the disparity is clearly greater. For non-primorial the value is reached much earlier e.g.. for Z = 9345 = 3*5*7*89 > 374 = 2*11*(2*7+3).

So the existence of M is proven and is shown by investigation to be 210 (which is 7#). For odd numbers the largest M is exactly half of this, 105.

***

Rupisnki wrote (18/8/04):

My proof is similar to Kens in that the final step utilizes Bertrand's postulate. Firstly, consider each odd N > 51. If 3 does not divide N, then 9 and N-9 are both composite clearly and sum to N. Similarly, if 5 does not divide N, then 25 and N-25 are both composite clearly; if 7 does not divide N, then 49 and N-49 are both composite (recall N>51 so N-49 is even and greater than 2). Thus the only case we need consider is when 3,5,7 divide N, i.e. N=105k. If k>1 then 121 = 11^2 is less than N and coprime to N unless 11 divides k. But if 11 divides k then N = 1155m and clearly 13^2 is less than N, and so on. Formally, since 100<105, Bertrand's postulate guarantees the square of a prime between 10^2 and (2*10)^2. At the same time, multiplying 105 by the next prime not dividing it, gives a larger number, for which there must lie a coprime square of a prime less than  it. Specifically, if N = p(n)#/2, then p(n+1)^2<N for n>5, this is easy to see by considering that for n>2, p(n)>4 so p(n)*p(n-1)#/2 > 4*p(n-1)#/2 and since there is a square of an integer less than p(n-1)#/2, say m^2<p(n-1)#/2 then the square of some prime q between m and 2m clearly satisfies q^2 < p(n)#/2. But we can take q = p(n+1) for sufficiently large n (in this case n = 4 I believe) since a stronger version of Bertrand's postulate states that for any K and all sufficiently large integers L, there are at least K primes between L and 2L. In our case here we take K = 2 and L = 6 suffices. Thus the square of p(n+1) is less than p(n)#/2 for all n>4 which establishes that there is a decomposition of p(n)#/2 = [p(n)#/2 - p(n+1)^2] + [p(n+1)^2] into coprime composites. On the other hand, all odd N which are not of the form p(n)#/2 have a smallest prime not dividing N, say N = [p(n)#/2]*Q where p(n+1) does not divide Q and n>3 (if n is less than or equal to 4 then 9, 25, or 49 is prime to N as discussed earlier), so by the previous argument p(n+1)^2 < N and the proof is complete for odd N>105.

*** Records   |  Conjectures  |  Problems  |  Puzzles  Home | Melancholia | Problems & Puzzles | References | News | Personal Page | Puzzlers | Search | Bulletin Board | Chat | Random Link Copyright © 1999-2012 primepuzzles.net. All rights reserved.