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.
***
|
