Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1994 IMO Problems/Problem 4"
m (→‎Solution)
 
(One intermediate revision by one other user not shown)
Line 3: Line 3:
  
 
== 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-(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.   
  
 
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 16: Line 16:
 
==See also==
 
==See also==
 
{{IMO box|year=1994|num-b=3|num-a=5}}
 
{{IMO box|year=1994|num-b=3|num-a=5}}
 +
[[Category:Olympiad Number Theory Problems]]

Latest revision as of 12:28, 26 April 2009

Problem

Find all ordered pairs $(m,n)$ where $m$ and $n$ are positive integers such that $\frac {n^3 + 1}{mn - 1}$ is an integer.

Solution

Suppose $\frac{n^3+1}{mn-1}=k$ where $k$ is a positive integer. Then $n^3+1=(mn-1)k$ and so it is clear that $k\equiv -1\pmod{n}$. So, let $k=jn-1$ where $j$ is a positive integer. Then we have $n^3+1=(mn-1)(jn-1)=mjn^2-(m+j)n+1$ which by cancelling out the $1$s and dividing by $n$ yields $n^2=mjn-(m+j)\Rightarrow n^2-mjn+m+j=0$. The equation $x^2-mjx+m+j=0$ is a quadratic. We are given that $n$ is one of the roots. Let $p$ be the other root. Notice that since $n+p=mj$ we have that $p$ is an integer, and so from $np=m+j$ we have that $p$ is positive.

It is obvious that $j=m=n=p=2$ is a solution. Now, if not, and $j,m,n,p$ are all greater than $1$, we have the inequalities $np>n+p$ and $mj>m+j$ which contradicts the equations $np=m+j, n+p=mj$. Thus, at least one of $j,m,n,p$ is equal to $1$.

If one of $m,j$ is $1$, without loss of generality assume it is $j$. Then we have $np=m+1, n+p=m$. That is, $np-n-p=1\Rightarrow (n-1)(p-1)=2$ which gives positive solutions $(n,p)=(3,2),(2,3)$. These give $m=5$ and since we assumed $j=1$, we can also have $m=1$ and $j=5$.

If one of $n,p$ is $1$, without loss of generality assume it is $p$. Then we have $n=m+j, n+1=mj$. That is, $mj-m-j=1\Rightarrow (m-1)(j-1)=2$ which gives positive solutions $(m,j)=(3,2),(2,3)$. These give $n=5$ and since we assumed $p=1$, we can also have $n=1$ and $p=5$.

From these, we have all solutions $(m,n)=(2,2),(5,3),(5,2),(1,3),(1,2),(3,5),(2,5),(3,1),(2,1)$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1994_IMO_Problems/Problem_4&oldid=31476"