Difference between revisions of "2007 IMO Problems/Problem 5"
Suvamghosh (talk | contribs) |
(→Second Solution) |
||
(3 intermediate revisions by 3 users not shown) | |||
Line 24: | Line 24: | ||
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> | ||
+ | |||
+ | (''Sean Yu, US'') | ||
+ | |||
+ | |||
+ | ==Second Solution == | ||
+ | |||
+ | As <math>(4a^2-1)^2 = (4a^2-4ab + 4ab-1)^2 \equiv (4a)^2(a-b)^2 \pmod {4ab-1}</math>, since <math>gcd((4a)^2, 4ab -1 ) = 1</math>, we only need to show that <math>4ab -1 \mid (a-b)^2 \Rightarrow a=b</math>. We will use the Vieta Jumping technique to solve it. | ||
+ | |||
+ | Suppose there exist counterexamples, which means the set <math>S = \{(x, y): \mbox {x and y are positive integers}, x \ne y, 4xy-1 \mid (x-y)^2\}</math> is not empty. Then there exists a pair <math>(a, b)\in S</math> such that <math>a+b</math> has the minimum sum among all pairs in <math>S</math>. Without loss of generality, we assume <math>a > b</math>. Let <math>k=\frac{(a-b)^2}{4ab-1}</math>. Then <math>k</math> is a positive integer and <math>a^2-(2+4k)ba + b^2+k = 0</math>. So <math>a</math> is a root for the quadratic equation <math>x^2-(2+4k)bx + b^2+k = 0</math>. Using the Vieta Lemma, we know the equation has another root <math>a' = \frac{b^2 + k}{a} > 0</math> and from <math>a' = (2+4k)b -a</math> we know it is an integer. Note that since <math>4ab -1 \mid(a-b)^2</math> and <math>a>b</math>, we have <math>4ab -1 \le (a-b)^2 \le a^2-1</math>, which implies <math>b\le a/4</math>. Also <math>k=\frac{(a-b)^2}{4ab-1} \le \frac{a^2}{3ab} \le a/3 </math>, thus <math>a' = \frac{b^2 + k}{a} \le \frac{(a/4)^2 + a/3}{a} = a/16 + 1/3 < a</math>, and we get another pair <math>(a', b)\in S</math>, but <math>a' + b < a+b</math>, which contradicts the assumption that <math>a+b</math> has the minimum sum. <math>\hfill\blacksquare</math> | ||
+ | |||
+ | |||
+ | <!-- Solution with a flaw below | ||
Alternate Elegant Solution | Alternate Elegant Solution | ||
========================== | ========================== | ||
− | (4a²-1)² = (4ab -1 + 4a² - 4ab)² [Adding and subtracting 4ab] | + | (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) | 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 | Now 4a can't be ≡ 0 mod (4ab - 1) unless a=0 which is not permissible | ||
− | Therefore, (a-b)² ≡ 0 mod (4ab - 1) | + | Therefore, (a-b)² ≡ 0 mod (4ab - 1) <--- this doesn't imply the next step in an obvious way |
So, a ≡ b mod (4ab - 1) | So, a ≡ b mod (4ab - 1) | ||
Line 40: | Line 52: | ||
Somebody please format the text :P | Somebody please format the text :P | ||
− | + | --> | |
{{alternate solutions}} | {{alternate solutions}} | ||
Line 47: | Line 59: | ||
{{IMO box|year=2007|num-b=4|num-a=6}} | {{IMO box|year=2007|num-b=4|num-a=6}} | ||
− | * <url> | + | * <url>viewtopic.php?p=894656#p894656 Discussion on AoPS/MathLinks</url> |
[[Category:Olympiad Number Theory Problems]] | [[Category:Olympiad Number Theory Problems]] |
Latest revision as of 04:00, 20 December 2024
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.
(Sean Yu, US)
Second Solution
As , since , we only need to show that . We will use the Vieta Jumping technique to solve it.
Suppose there exist counterexamples, which means the set is not empty. Then there exists a pair such that has the minimum sum among all pairs in . Without loss of generality, we assume . Let . Then is a positive integer and . So is a root for the quadratic equation . Using the Vieta Lemma, we know the equation has another root and from we know it is an integer. Note that since and , we have , which implies . Also , thus , and we get another pair , but , which contradicts the assumption that has the minimum sum.
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>viewtopic.php?p=894656#p894656 Discussion on AoPS/MathLinks</url>