Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2007 IMO Problems/Problem 5"

(→‎Resources)
(→‎Second Solution)
 
(One intermediate revision by the same user not shown)
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>
 +
 +
 +
(''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
 
<!-- Solution with a flaw below

Latest revision as of 04:00, 20 December 2024

Problem

(Kevin Buzzard and Edward Crane, United Kingdom) Let $a$ and $b$ be positive integers. Show that if $4ab-1$ divides $(4a^2-1)^2$, then $a=b$.

Solution

Lemma. If there is a counterexample for some value of $a$, then there is a counterexample $(a,b)$ for this value of $a$ such that $b<a$.

Proof. Suppose that $b >a$. Note that $4ab -1 \equiv -1 \pmod{4a}$, but $(4a^2-1)^2 \equiv 1 \pmod{4a}$. It follows that $(4a^2-1)^2/(4ab-1) \equiv -1 \pmod{4a}$. Since \[0<(4a^2-1)^2/(4ab-1) < (4a^2-1)^2/(4a^2-1) = 4a^2-1,\] it follows that $(4a^2-1)^2/(4ab-1)$ can be written as $4ab'-1$, with $0<b'<a$. Then $(a,b')$ is a counterexample for which $b'<a$. $\blacksquare$

Now, suppose a counterexample exists. Let $(a,b)$ be a counterexample for which $a$ is minimal and $b<a$. We note that \[\gcd(4ab-1,2a-1) \mid 4ab-1 - 2b(2a-1) = 2b-1,\] and \[\gcd(4ab-1,2a+1) \mid 2b(2a+1) - (4ab-1) = 2b+1 .\] Now, \begin{align*} 4ab-1 &\mid (4a^2-1)^2 = (2a-1)^2(2a+1)^2 \\ &\mid \gcd(4ab-1,2a-1)^2 \cdot \gcd(4ab-1,2a+1)^2 \\ &\mid (2b-1)^2(2b+1)^2 = (4b^2-1)^2 . \end{align*} Thus $(b,a)$ is a counterexample. But $b<a$, which contradicts the minimality of $a$. Therefore no counterexample exists. $\blacksquare$


(Sean Yu, US)


Second Solution

As $(4a^2-1)^2 = (4a^2-4ab + 4ab-1)^2 \equiv (4a)^2(a-b)^2 \pmod {4ab-1}$, since $gcd((4a)^2, 4ab -1 ) = 1$, we only need to show that $4ab -1 \mid (a-b)^2 \Rightarrow a=b$. We will use the Vieta Jumping technique to solve it.

Suppose there exist counterexamples, which means the set $S = \{(x, y): \mbox {x and y are positive integers}, x \ne y, 4xy-1 \mid (x-y)^2\}$ is not empty. Then there exists a pair $(a, b)\in S$ such that $a+b$ has the minimum sum among all pairs in $S$. Without loss of generality, we assume $a > b$. Let $k=\frac{(a-b)^2}{4ab-1}$. Then $k$ is a positive integer and $a^2-(2+4k)ba + b^2+k = 0$. So $a$ is a root for the quadratic equation $x^2-(2+4k)bx + b^2+k = 0$. Using the Vieta Lemma, we know the equation has another root $a' = \frac{b^2 + k}{a} > 0$ and from $a' = (2+4k)b -a$ we know it is an integer. Note that since $4ab -1 \mid(a-b)^2$ and $a>b$, we have $4ab -1 \le (a-b)^2 \le a^2-1$, which implies $b\le a/4$. Also $k=\frac{(a-b)^2}{4ab-1} \le \frac{a^2}{3ab} \le a/3$, thus $a' = \frac{b^2 + k}{a} \le \frac{(a/4)^2 + a/3}{a} = a/16 + 1/3 < a$, and we get another pair $(a', b)\in S$, but $a' + b < a+b$, which contradicts the assumption that $a+b$ has the minimum sum. $\hfill\blacksquare$


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>
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_IMO_Problems/Problem_5&oldid=237357"