AoPSWiki

Want to learn how to tackle those tough MATHCOUNTS and AMC counting and probability problems? Check out Art of Problem Solving's Introduction to Counting & Probability by David Patrick.

Personal tools

Search

Toolbox

2007 IMO Problems/Problem 5

From AoPSWiki

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 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 \\&\m...$ Thus $(b,a)$ is a counterexample. But $b<a$ , which contradicts the minimality of $a$ . Therefore no counterexample exists. $\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)
Preceded by Problem 4	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 6

Discussion on AoPS/MathLinks

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/2007_IMO_Problems/Problem_5"

Category: Olympiad Number Theory Problems

Art of Problem Solving holds many free classes called Math Jams.
Click here for transcripts to past Math Jams.

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us