2007 IMO Problems/Problem 5
Contents
[hide]Problem
(Kevin Buzzard and Edward Crane, United Kingdom) Let and be positive integers. Show that if divides , then .
Solution
Lemma. If there is a counterexample for some value of , then there is a counterexample for this value of such that .
Proof. Suppose that . Note that , but . It follows that . Since it follows that can be written as , with . Then is a counterexample for which .
Now, suppose a counterexample exists. Let be a counterexample for which is minimal and . We note that and Now, Thus is a counterexample. But , which contradicts the minimality of . Therefore no counterexample exists.
Alternate Elegant Solution
==============
(4a²-1)² = (4ab -1 + 4a² - 4ab)² [Adding and subtracting 4ab]
≡ (4a)² (a-b)² mod (4ab - 1)
As per question, (4a²-1)² ≡ 0 mod (4ab - 1)
Now 4a can't be ≡ 0 mod (4ab - 1) unless a=0 which is not permissible Therefore, (a-b)² ≡ 0 mod (4ab - 1) So, a ≡ b mod (4ab - 1)
But a and b are both smaller than 4ab - 1 Hence a = b
Somebody please format the text :P
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
Resources
2007 IMO (Problems) • Resources | ||
Preceded by Problem 4 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
All IMO Problems and Solutions |
- <url>Forum/viewtopic.php?p=894656#p894656 Discussion on AoPS/MathLinks</url>