Difference between revisions of "2007 IMO Problems/Problem 5"
(Problem and solution) |
Suvamghosh (talk | contribs) |
||
Line 23: | Line 23: | ||
\end{align*} </cmath> | \end{align*} </cmath> | ||
Thus <math>(b,a)</math> is a counterexample. But <math>b<a</math>, which contradicts the minimality of <math>a</math>. Therefore no counterexample exists. <math>\blacksquare</math> | Thus <math>(b,a)</math> is a counterexample. But <math>b<a</math>, which contradicts the minimality of <math>a</math>. Therefore no counterexample exists. <math>\blacksquare</math> | ||
+ | |||
+ | 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 | ||
Revision as of 11:54, 21 November 2009
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>