Find Pairs of Positive Integers

Date: 10/15/2001 at 15:50:21
From: Mike
Subject: Brain busters

With each entry I submit, I have to write a different pair of 
positive integers whose greatest common factor is 1 and whose sum is 
2000. (Pairs differing in the order of addition are counted as 1 pair, 
not as 2 different pairs.) 

For example, I submit the pair (1, 1999) with my first entry. 

With these restrictions, at most how many entries can one person 
submit?

Date: 10/15/2001 at 16:20:37
From: Doctor Jubal
Subject: Re: Brain busters

Hi Mike,

Here's the beginning of a solution. I'll leave you to figure out the 
rest.

There are 1000 ways we could add two numbers to get 2000. The first 
one is 1+1999, the 2nd one is 2+1998, and so forth until we get to 
1000+1000.

Not all of them count, though, because in some of them, the two 
numbers share a common factor. Let's call this common factor f, and 
write the two numbers as a*f and b*f.  Then

  a*f + b*f = (a+b)*f = 2000.

That is to say, if the two numbers share a common factor, 2000 must 
also share that factor. But 2000 has a lot of factors, and it would be 
tedious to look at each pair of numbers and each of the factors of 
2000 and see if the numbers are divisible by that factor of 2000.

The good news is we don't have to look at all the factors. Let's say 
that f is composite and can be factored into primes like this:

  f = p1^n1 * p2^n2 * p3^n3 * ...

Then we can rewrite the two numbers 

  a*f = a * p1^n1 * p2^n2 * ...
  b*f = b * p1^n1 * p2^n2 * ...

That is to say, if the two numbers share a composite factor, they must 
also share a prime factor.  The whole point of this is that we don't 
have to consider any of 2000's composite factors, because any pairs of 
numbers we would rule out with a composite factor, we can also rule 
out with a prime factor.

So, let's find the prime factors of 2000

  2000 = 2 * 1000 = 2 * 10^3 = 2 * (2*5)^3 = 2^4 * 5^3.

We see that 2 and 5 are the only prime factors of 2000.

Now, your task is to figure out 

(1) of the 1000 ways to add two positive numbers and get 2000, in how 
    many of them are both numbers divisible by 2?
(2) in how many of them are both numbers divisible by 5?
(3) in how many of them are both numbers divisible by both 2 and 5?

Then, from the 1000 ways, you can subtract all the number of ways 
where the numbers are divisible by 2, and you can also subtract the 
number of ways where the numbers are divisble by 5. But now, you've 
just subtracted any ways where the numbers are divisible by both 2 and 
5 twice, so you have to add that many ways back in to correct that 
mistake. And voila, you have an answer.

Does this help?  Write back if you'd like to talk about this some
more, or if you have any other questions.

- Doctor Jubal, The Math Forum
  http://mathforum.org/dr.math/