Difference between revisions of "1995 AIME Problems/Problem 8"
IMOJonathan (talk | contribs) |
|||
Line 2: | Line 2: | ||
For how many ordered pairs of positive [[integer]]s <math>(x,y),</math> with <math>y<x\le 100,</math> are both <math>\frac xy</math> and <math>\frac{x+1}{y+1}</math> integers? | For how many ordered pairs of positive [[integer]]s <math>(x,y),</math> with <math>y<x\le 100,</math> are both <math>\frac xy</math> and <math>\frac{x+1}{y+1}</math> integers? | ||
− | == Solution == | + | == Solution 1== |
Since <math>y|x</math>, <math>y+1|x+1</math>, then <math>\text{gcd}\,(y,x)=y</math> (the bars indicate [[divisibility]]) and <math>\text{gcd}\,(y+1,x+1)=y+1</math>. By the [[Euclidean algorithm]], these can be rewritten respectively as <math>\text{gcd}\,(y,x-y)=y</math> and <math>\text{gcd}\, (y+1,x-y)=y+1</math>, which implies that both <math>y,y+1 | x-y</math>. Also, as <math>\text{gcd}\,(y,y+1) = 1</math>, it follows that <math>y(y+1)|x-y</math>. {{ref|1}} | Since <math>y|x</math>, <math>y+1|x+1</math>, then <math>\text{gcd}\,(y,x)=y</math> (the bars indicate [[divisibility]]) and <math>\text{gcd}\,(y+1,x+1)=y+1</math>. By the [[Euclidean algorithm]], these can be rewritten respectively as <math>\text{gcd}\,(y,x-y)=y</math> and <math>\text{gcd}\, (y+1,x-y)=y+1</math>, which implies that both <math>y,y+1 | x-y</math>. Also, as <math>\text{gcd}\,(y,y+1) = 1</math>, it follows that <math>y(y+1)|x-y</math>. {{ref|1}} | ||
Line 10: | Line 10: | ||
<br /><br />{{note|1}} Another way of stating this is to note that if <math>\frac{x}{y}</math> and <math>\frac{x+1}{y+1}</math> are integers, then <math>\frac{x}{y} - 1 = \frac{x-y}{y}</math> and <math>\frac{x+1}{y+1} - 1 = \frac{x-y}{y+1}</math> must be integers. Since <math>y</math> and <math>y+1</math> cannot share common prime factors, it follows that <math>\frac{x-y}{y(y+1)}</math> must also be an integer. | <br /><br />{{note|1}} Another way of stating this is to note that if <math>\frac{x}{y}</math> and <math>\frac{x+1}{y+1}</math> are integers, then <math>\frac{x}{y} - 1 = \frac{x-y}{y}</math> and <math>\frac{x+1}{y+1} - 1 = \frac{x-y}{y+1}</math> must be integers. Since <math>y</math> and <math>y+1</math> cannot share common prime factors, it follows that <math>\frac{x-y}{y(y+1)}</math> must also be an integer. | ||
+ | |||
+ | == Solution 2== | ||
+ | We know that <math>x \equiv 0 \mod y</math> and <math>x+1 \equiv 0 \mod y+1</math>. | ||
+ | |||
+ | Write <math>x</math> and <math>ky</math> for some integer <math>k</math>. Then, <math>ky+1 \equiv 0\mod y+1</math>. We can add <math>k</math> to each side in order to factor out a <math>y+1</math>. So, <math>ky+k+1 \equiv k \mod y+1</math> or <math>k(y+1)+1 \equiv k \mod y+1</math>. We know that <math>k(y+1) \equiv 0 \mod y+1</math>. We finally achieve the congruence <math>1-k \equiv 0 \mod y+1</math>. | ||
+ | |||
+ | We can now write <math>k</math> as <math>(y+1)a+1</math>. Plugging this back in, if we have a value for <math>y</math>, then <math>x = ky = ((y+1)a+1)y = y(y+1)a+y</math>. We only have to check values of <math>y</math> when <math>y(y+1)<100</math>. This yields the equations <math>x = 2a+1, 6a+2, 12a+3, 20a+4, 30a+5, 42a+6, 56a+7, 72a+8, 90a+9</math>. | ||
+ | |||
+ | Finding all possible values of <math>a</math> such that <math>y<x<100</math>, we get <math>49 + 16 + 8 + 4 + 3 + 2 + 1 + 1 + 1 = \boxed{085}.</math> | ||
== See also == | == See also == |
Revision as of 00:15, 1 September 2015
Contents
[hide]Problem
For how many ordered pairs of positive integers with
are both
and
integers?
Solution 1
Since ,
, then
(the bars indicate divisibility) and
. By the Euclidean algorithm, these can be rewritten respectively as
and
, which implies that both
. Also, as
, it follows that
. [1]
Thus, for a given value of , we need the number of multiples of
from
to
(as
). It follows that there are
satisfactory positive integers for all integers
. The answer is
^ Another way of stating this is to note that if and
are integers, then
and
must be integers. Since
and
cannot share common prime factors, it follows that
must also be an integer.
Solution 2
We know that and
.
Write and
for some integer
. Then,
. We can add
to each side in order to factor out a
. So,
or
. We know that
. We finally achieve the congruence
.
We can now write as
. Plugging this back in, if we have a value for
, then
. We only have to check values of
when
. This yields the equations
.
Finding all possible values of such that
, we get
See also
1995 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 7 |
Followed by Problem 9 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.