2007 AMC 10B Problems/Problem 25
How many pairs of positive integers are there such that and have no common factors greater than and:
is an integer?
Combining the fraction, must be an integer.
Since the denominator contains a factor of ,
Since for some positive integer , we can rewrite the fraction (divide by on both numerator and denominator) as
Since the denominator now contains a factor of , we get .
But since , we must have , and thus .
For the original fraction simplifies to .
For that to be an integer, must be a factor of , and therefore we must have . Each of these values does indeed yield an integer.
Thus there are four solutions: , , , and the answer is
Let's assume that . We get
Factoring this, we get equations:
(It's all negative, because if we had positive signs, would be the opposite sign of )
Now we look at these, and see that:
This gives us solutions, but we note that the middle term must be divisible by .
For example, in the case
, the middle term is , which is not equal to for any integer .
Apply similar reasoning to the fourth equation. This eliminates four solutions out of the above eight listed, giving us solutions total
Let . Then the given equation becomes .
Let's set this equal to some value, .
Clearing the denominator and simplifying, we get a quadratic in terms of :
Since and are integers, is a rational number. This means that is an integer.
Let . Squaring and rearranging yields:
In order for both and to be an integer, and must both be odd or even. (This is easily proven using modular arithmetic.) In the case of this problem, both must be even. Let and .
Factoring , we get pairs of numbers: and .
Looking back at our equations for and , we can solve for . Since is an integer, there are only pairs of that work: and . This means that there are values of such that is an integer. But looking back at in terms of , we have , meaning that there are values of for every . Thus, the answer is .
Rewriting the expression over a common denominator yields . This expression must be equal to some integer .
Thus, . Taking this yields . Since , . This implies that so .
We can then take to get that . Thus .
However, taking , so cannot equal 1.
Also, note that if , . Since , will be an integer, but will not be an integer since none of the possible values of are multiples of 9. Thus, cannot equal 9.
Thus, the only possible values of is 3, and can be 1, 2, 7, or 14. This yields 4 possible solutions, so the answer is .
Solution 5 (Similar to Solution 1)
Rewriting over a common denominator gives
Thus, we have
Next, we have
Next, we have
Now, we simply do casework on
Plugging in and gives that there are total solutions for
Solution 6 (Similar to solution 3)
Let So , where I is an integer. Algebraic manipulations yield: . The discriminant of this must be the square of a rational number, call this R. So . I is the sum of and . To have an integer sum, and must have the same denominator, namely 3. We proceed with casework.
Case 1. , . This yields , which is not an integer. This case produces 0 solutions.
Case 2. , . This yields . Substituting into our original equation yields: . Factoring gives: , . This case produces 2 solutions, namely (1,3) and (14,3).
Case 3. , . This yields . Substituting into our original equation yields: . Factoring gives: , . This case produces 2 solutions, namely (2,3) and (7,3).
Case 4. , . This yields , which is not an integer. This case produces 0 solutions.
Altogether, we have 4 solutions, so our answer is .
|2007 AMC 10B (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25|
|All AMC 10 Problems and Solutions|