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"

(Problem and solution)
 
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

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$

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