[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

2033.0. "Crux Mathematicorum 2123" by RUSURE::EDP (Always mount a scratch monkey.) Thu Mar 21 1996 09:13

    Proposed by Sydney Bulman-Felming and Edward T. H. Wang, Wilfrid
    Laurier University, Waterloo, Ontario.
    
    It is known (e.g., exercise 23, page 78 of Kenneth H. Rosen's
    Elementary Number Theory and its Applications, Third Edition) that
    every natural number greater than 6 is the sum of two relatively prime
    integers, each greater than 1.  Find all natural numbers which can be
    expressed as the sum of three pairwise relatively prime integers, each
    greater than 1.

T.R Title User Personal
Name Date Lines

2033.1 answer FLOYD::YODER MFY Fri Mar 22 1996 15:43 31

T.R	Title	User	Personal Name	Date	Lines
2033.1	answer	FLOYD::YODER	MFY	`Fri Mar 22 1996 15:43`	31
	Summary: all even numbers >= 10, and all odd numbers >= 15 except 17. Three numbers which are relatively prime in pairs (RPIP) are either one even and two odd (in which case the sum is even) or three odd (in which case the sum is odd). So three such numbers with an even sum must sum to at least 2 + 3 + 5 >= 10. Now the sums 2 + n + (n+2) and 4 + n + (n+2) are, for n odd and >=3, sums of RPIP numbers which cover all even numbers >= 10. This demonstrates the claim about even numbers. Lemma. If n is odd and p is an odd prime such that (n+4)/3 < p <= n-8, then if n-p = 2k, n = p + (k-e) + (k+e) is a sum of RPIP numbers greater than 1 if e = 1 or 2 and e is chosen so k+e and k-e are odd. Proof. p <= n-8 insures that k >= 4, so k-e >= 3 and k+e >= 5. (n+4)/3 < p implies n-p >= (2n-4)/3, so k <= (n-2)/3, so k+e <= (n+4)/3, so k+e < p. This guarantees that k-e and k+e are relatively prime to p, and they are relatively prime to each other because they are odd and their difference is either 2 or 4. Now: let n be odd. If n > 32, there exists a prime p such that (n+4)/3 < p < 2(n+4)/3, such a prime p will be odd, and will be <= n-8. If 21 <= n <= 31, p = 13 satisfies (n+4)/3 < p <= n-8. Finally, 19 = 11 + 3 + 5, 15 = 3 + 5 + 7. The only set of distinct odd integers > 1 which sum to 17 is {3,5,9}, which doesn't work. Three distinct odd integers > 1 must sum to at least 3+5+7 = 15, so no other cases need be considered.

Summary: all even numbers >= 10, and all odd numbers >= 15 except 17.

Three numbers which are relatively prime in pairs (RPIP) are either one even and
two odd (in which case the sum is even) or three odd (in which case the sum is
odd). 

So three such numbers with an even sum must sum to at least 2 + 3 + 5 >= 10. 
Now the sums 2 + n + (n+2) and 4 + n + (n+2) are, for n odd and >=3, sums of
RPIP numbers which cover all even numbers >= 10.  This demonstrates the claim
about even numbers.

Lemma.  If n is odd and p is an odd prime such that (n+4)/3 < p <= n-8, then if
n-p = 2k, n = p + (k-e) + (k+e) is a sum of RPIP numbers greater than 1 if e = 1
or 2 and e is chosen so k+e and k-e are odd.

Proof.  p <= n-8 insures that k >= 4, so k-e >= 3 and k+e >= 5.  (n+4)/3 < p
implies n-p >= (2n-4)/3, so k <= (n-2)/3, so k+e <= (n+4)/3, so k+e < p.
This guarantees that k-e and k+e are relatively prime to p, and they are
relatively prime to each other because they are odd and their difference is
either 2 or 4.

Now: let n be odd.  If n > 32, there exists a prime p such that (n+4)/3 < p <
2(n+4)/3, such a prime p will be odd, and will be <= n-8.

If 21 <= n <= 31, p = 13 satisfies (n+4)/3 < p <= n-8.

Finally, 19 = 11 + 3 + 5, 15 = 3 + 5 + 7.

The only set of distinct odd integers > 1 which sum to 17 is {3,5,9}, which
doesn't work.  Three distinct odd integers > 1 must sum to at least 3+5+7 = 15,
so no other cases need be considered.