Difference between revisions of "1994 IMO Problems/Problem 4"
(New page: Find all ordered pairs <math>(m,n)</math> where <math>m</math> and <math>n</math> are positive integers such that <math>\frac {n^3 + 1}{mn - 1}</math> is an integer. == Solution == Supp...) |
m (→Solution) |
||
(3 intermediate revisions by one other user not shown) | |||
Line 1: | Line 1: | ||
+ | ==Problem== | ||
Find all ordered pairs <math>(m,n)</math> where <math>m</math> and <math>n</math> are positive integers such that <math>\frac {n^3 + 1}{mn - 1}</math> is an integer. | Find all ordered pairs <math>(m,n)</math> where <math>m</math> and <math>n</math> are positive integers such that <math>\frac {n^3 + 1}{mn - 1}</math> is an integer. | ||
− | |||
== Solution == | == Solution == | ||
− | + | Suppose <math>\frac{n^3+1}{mn-1}=k</math> where <math>k</math> is a positive integer. Then <math>n^3+1=(mn-1)k</math> and so it is clear that <math>k\equiv -1\pmod{n}</math>. So, let <math>k=jn-1</math> where <math>j</math> is a positive integer. Then we have <math>n^3+1=(mn-1)(jn-1)=mjn^2-(m+j)n+1</math> which by cancelling out the <math>1</math>s and dividing by <math>n</math> yields <math>n^2=mjn-(m+j)\Rightarrow n^2-mjn+m+j=0</math>. The equation <math>x^2-mjx+m+j=0</math> is a quadratic. We are given that <math>n</math> is one of the roots. Let <math>p</math> be the other root. Notice that since <math>n+p=mj</math> we have that <math>p</math> is an integer, and so from <math>np=m+j</math> we have that <math>p</math> is positive. | |
− | Suppose <math>\frac{n^3+1}{mn-1}=k</math> where <math>k</math> is a positive integer. Then <math>n^3+1=(mn-1)k</math> and so it is clear that <math>k\equiv -1\pmod{n}</math>. So, let <math>k=jn-1</math> where <math>j</math> is a positive integer. Then we have <math>n^3+1=(mn-1)(jn-1)=mjn^2- | ||
It is obvious that <math>j=m=n=p=2</math> is a solution. Now, if not, and <math>j,m,n,p</math> are all greater than <math>1</math>, we have the inequalities <math>np>n+p</math> and <math>mj>m+j</math> which contradicts the equations <math>np=m+j, n+p=mj</math>. | It is obvious that <math>j=m=n=p=2</math> is a solution. Now, if not, and <math>j,m,n,p</math> are all greater than <math>1</math>, we have the inequalities <math>np>n+p</math> and <math>mj>m+j</math> which contradicts the equations <math>np=m+j, n+p=mj</math>. | ||
Line 14: | Line 13: | ||
From these, we have all solutions <math>(m,n)=(2,2),(5,3),(5,2),(1,3),(1,2),(3,5),(2,5),(3,1),(2,1)</math>. | From these, we have all solutions <math>(m,n)=(2,2),(5,3),(5,2),(1,3),(1,2),(3,5),(2,5),(3,1),(2,1)</math>. | ||
+ | |||
+ | ==See also== | ||
+ | {{IMO box|year=1994|num-b=3|num-a=5}} | ||
+ | [[Category:Olympiad Number Theory Problems]] |
Latest revision as of 13:28, 26 April 2009
Problem
Find all ordered pairs where
and
are positive integers such that
is an integer.
Solution
Suppose where
is a positive integer. Then
and so it is clear that
. So, let
where
is a positive integer. Then we have
which by cancelling out the
s and dividing by
yields
. The equation
is a quadratic. We are given that
is one of the roots. Let
be the other root. Notice that since
we have that
is an integer, and so from
we have that
is positive.
It is obvious that is a solution. Now, if not, and
are all greater than
, we have the inequalities
and
which contradicts the equations
.
Thus, at least one of
is equal to
.
If one of is
, without loss of generality assume it is
. Then we have
. That is,
which gives positive solutions
. These give
and since we assumed
, we can also have
and
.
If one of is
, without loss of generality assume it is
. Then we have
. That is,
which gives positive solutions
. These give
and since we assumed
, we can also have
and
.
From these, we have all solutions .
See also
1994 IMO (Problems) • Resources | ||
Preceded by Problem 3 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 5 |
All IMO Problems and Solutions |