Let $ k$ be a positive integer. Prove that the number $ (4 \cdot k^2 - 1)^2$ has a positive divisor of the form $ 8kn - 1$ if and only if $ k$ is even. Actual IMO 2007 Problem, posed as question 5 in the contest, which was used as a lemma in the official solutions for problem N6 as shown above. Author: Kevin Buzzard and Edward Crane, United Kingdom
Problem
Source: IMO Shortlist 2007, N6
Tags: quadratics, number theory, IMO, IMO 2007, Vieta Jumping, Divisibility
The QuattoMaster 6000
04.10.2008 22:31
I am not sure how necessary this solution is, as the IMO problem essentially kills it, but here is a solution:
Lemma: For positive integers $ a$ and $ b$, $ \frac {(4a^2 - 1)^2}{4ab - 1}$ is an integer if only if $ a = b$.
Proof: If $ a = b$, then $ (4a^2 - 1)|(4a^2 - 1)^2$, so we are done. If $ \frac {(4a^2 - 1)^2}{4ab - 1}$ is an integer, then we can let $ \gcd (4a^2 - 1, 4ab - 1) = n$. Then, $ n = \gcd (4a^2 - 4ab, 4ab - 1) = \gcd (4a(a - b), 4ab - 1)$. Since $ 4a$ and $ 4ab - 1$ are coprime, $ n = \gcd (a - b, 4ab - 1)$. Thus, $ \frac {(4a^2 - 1)^2}{4ab - 1}$ being an integer is equivalent to saying that $ \frac {(a - b)^2}{4ab - 1}$ is an integer, say $ k$. Upon expanding, we have that $ a^2 - a(4bk + 2b) + (b^2 + k) = 0$.
Assume that $ a\ne b$, so let $ a > b$. Then, say that we have a solution, $ (a,b)$ with $ a + b$ being minimal. Notice that the equation is symmetric in $ a$ and $ b$, so we also have solution $ (b,a)$. Now, notice that by Vieta's theorem (if we look at the equation in a quadratic in $ a$), we have that $ \frac {b^2 + k}{a}$ is the other solution. It follows that $ (\frac {b^2 + k}{a}, b)$ is a solution to the quadratic, and therefore, $ (b, \frac {b^2 + k}{a})$ is a solution. Since $ b < a$, we must have that $ \frac {b^2 + k}{a}\ge b$ or else $ b + \frac {b^2 + k}{a} < a + b$, contradicting the minimality of $ a + b$. Then, $ k\ge b(a - b)$. This implies that $ \frac {(a - b)^2}{4ab - 1}\ge b(a - b)$, meaning that $ a - b\ge 4ab^2 - b$, so $ a(4b^2 - 1)\le 0$, which is a contradiction for positive integers $ a$ and $ b$. Thus, our assumption was false and $ a = b$.
Now for the problem itself. For $ k$ even, we can let $ k = 2x$. Therefore, $ \frac {(4k^2 - 1)^2}{8kx - 1} = \frac {(4k^2 - 1)^2}{4k^2 - 1}$, which is clearly an integer. Then, $ 8kx - 1$ is a positive divisor of $ (4k^2 - 1)^2$, so it is proved if $ k$ is even. If $ k$ is odd, assume that there exists a factor of $ (4k^2 - 1)^2$ in the form of $ 8kn - 1$. Hence, we have that $ \frac {(4k^2 - 1)^2}{4\cdot k(2n) - 1}$ is an integer. Yet, by the lemma, we have that this is an integer if and only if $ k = 2n$, which means that $ k$ is even, and we have a contradiction. Thus, $ k$ cannot be odd and we are done.
AMN300
01.05.2016 01:46
Yeah, this is really very vacuous with the IMO problem in mind.
If $k$ is even the problem is trivial, take $k=2a=n$. For the other direction, by 2007 IMO 5 (you can find my solution in the thread), $4ab-1 | (4a^2-1)^2 \implies a=b$. So $4k(2n)-1 | (4k^2-1)^2 \implies k=2n$, done.
GeronimoStilton
16.11.2020 02:59
First, we prove the following result. Lemma: [IMO 2007/5] Let $a$ and $b$ be positive integers. Show that if $4ab - 1$ divides $(4a^{2} - 1)^{2}$, then $a = b$. Solution: First, observe that $\gcd(4ab-1,4a^2-1) \mid 4a^2-4ab$. It is clear that $4a$ is relatively prime to $4ab-1$, so we have $4ab-1\mid (a-b)^2$, which is a symmetric condition. We claim this condition implies $a=b$. For contradiction, suppose $a>b.$ WLOG, so $k>0$. Now, we Vieta Jump into the ground. Let $4kab-k = a^2-2ab+b^2$, which rearranges as \[a^2-(4kb+2b)a+b^2+k.\]If $\frac{b^2+k}{a}<b+1$, we can iterate our Vieta Jumping, as we cannot have $a=b\implies k=0$. Note that all $a,b$ obtained must be positive integers. Moreover, it is clearly impossible to continue Vieta Jumping forever because there exists no infinite decreasing sequence of positive integers. Then, suppose at some point that $b^2+k\ge ab+a>ab$, so $k>(a-b)b$. Then, we must have \[(a-b)^2 = (4ab-1)k>(4ab-1)(a-b)b,\]implying $a-b>(4ab-1)b$. But this is absurd; it is clear that $(4ab-1)b\ge 4a-1\ge 3a>a-b$. Hence, we have a contradiction and are done. $\fbox{}$ Now, observe the desired result is trivial in the if direction; take $n=k/2$. For a solution $k,n$, write $8kn-1 = 4k\cdot 2n-1$ and invoke the lemma to yield $k=2n$, so $k$ is even.
megarnie
09.08.2022 17:54
The if direction can be done by taking $n=\frac{k}{2}$. We now show $k$ must be even. We have \[4\cdot k\cdot 2n - 1 \mid (4k^2 - 1)^2.\]By 2007 IMO P5, we get $k=2n$, so $k$ is even.
metricpaper
10.08.2022 01:27
By IMO 2007 P5, we know that if $4k(2n)-1\mid (4k^2-1)^2$, then $k=2n$, so $k$ is even. Conversely, since $4k^2-1\mid (4k^2-1)^2$, if $k=2n$ for some positive integer $n$, then $8kn-1\mid (4k^2-1)^2$.