Difference between revisions of "1981 IMO Problems/Problem 3"
(numbers) |
(→Solution: clean up solution) |
||
| Line 7: | Line 7: | ||
We first observe that since <math>\gcd(m,n)|1 </math>, <math>m</math> and <math>n</math> are [[relatively prime]]. In addition, we note that <math>n \ge m</math>, since if we had <math>n < m</math>, then <math>n^2 +nm -m^2 = n(n-m) - m^2 </math> would be the sum of two negative integers and therefore less than <math>-1</math>. We now observe | We first observe that since <math>\gcd(m,n)|1 </math>, <math>m</math> and <math>n</math> are [[relatively prime]]. In addition, we note that <math>n \ge m</math>, since if we had <math>n < m</math>, then <math>n^2 +nm -m^2 = n(n-m) - m^2 </math> would be the sum of two negative integers and therefore less than <math>-1</math>. We now observe | ||
| − | < | + | <cmath> |
| − | |||
(m+k)^2 -(m+k)m - m^2 = -(m^2 - km - k^2) | (m+k)^2 -(m+k)m - m^2 = -(m^2 - km - k^2) | ||
| − | </ | + | </cmath>, |
| − | |||
| − | i.e., <math>(m,n) = (a,b) </math> is a solution [[iff]]. <math>(b, a+b) </math> is also a solution. Therefore, for a solution <math>(m, n)</math>, we can perform the [[Euclidean algorithm]] to reduce it eventually to a solution <math>(1,n) </math>. It is easy to verify that if <math>n </math> is a positive integer, it must be either 2 or 1. Thus by trivial induction, all the positive integer solutions are of the form <math>(F_{n}, F_{n+1})</math>, where the <math>F_i</math> are the [[Fibonacci numbers]]. Simple calculation reveals 987 and 1597 to be the greatest Fibonacci numbers less than 1981, giving <math>987^2 + 1597^2 </math> as the maximal value | + | i.e., <math>(m,n) = (a,b) </math> is a solution [[iff]]. <math>(b, a+b) </math> is also a solution. Therefore, for a solution <math>(m, n)</math>, we can perform the [[Euclidean algorithm]] to reduce it eventually to a solution <math>(1,n) </math>. It is easy to verify that if <math>n </math> is a positive integer, it must be either 2 or 1. Thus by trivial induction, all the positive integer solutions are of the form <math>(F_{n}, F_{n+1})</math>, where the <math>F_i</math> are the [[Fibonacci numbers]]. Simple calculation reveals <math>987</math> and <math>1597</math> to be the greatest Fibonacci numbers less than <math>1981</math>, giving <math>987^2 + 1597^2=3524578</math> as the maximal value. |
Revision as of 21:04, 7 December 2007
Problem
Determine the maximum value of 
, where 
and 
are integers satisfying 
and 
.
Solution
We first observe that since 
, and are relatively prime. In addition, we note that 
, since if we had 
, then 
would be the sum of two negative integers and therefore less than 
. We now observe
![\[(m+k)^2 -(m+k)m - m^2 = -(m^2 - km - k^2)\]](http://latex.artofproblemsolving.com/e/9/9/e990def068c76d29fa23986a5ad7860e3c6e28c4.png)
,
i.e., 
is a solution iff. 
is also a solution. Therefore, for a solution 
, we can perform the Euclidean algorithm to reduce it eventually to a solution 
. It is easy to verify that if is a positive integer, it must be either 2 or 1. Thus by trivial induction, all the positive integer solutions are of the form 
, where the 
are the Fibonacci numbers. Simple calculation reveals 
and 
to be the greatest Fibonacci numbers less than 
, giving 
as the maximal value.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
| 1981 IMO (Problems) • Resources | ||
| Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
| All IMO Problems and Solutions | ||
