Associated Topics || Dr. Math Home || Search Dr. Math

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

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

more, or if you have any other questions.

- Doctor Jubal, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Puzzles
Middle School Factoring Numbers
Middle School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search