Difference between revisions of "1981 IMO Problems/Problem 3"
(→Solution: clean up solution) |
m (→Solution) |
||
Line 5: | Line 5: | ||
== Solution == | == Solution == | ||
− | 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 | + | 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> | <cmath> |
Revision as of 08:52, 28 April 2010
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
,
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 |