32
$\begingroup$

There is a recent question about this famous problem from 1988 on this forum, but I'm unable to respond to this because the subject is closed for me (insufficient reputation). Therefore this new post on the subject.

here's the link to the earlier subject

The problem: Let a and b be positive integers. Let $$ k={{a^2+b^2}\over{1+ab}} $$ Show that if $k$ is an integer then $k$ is a perfect square.

The question was: Is there a more direct and intuitive way to arrive at the solution (instead of the usual proof using Vieta jumping and proof by contradiction)?

After seeing this hilarious Numberphile video on Youtube i decided i had to give it a go myself.

The solution i came up with below seems to me more canonical because it's not a proof by contradiction, and it arrives at the actual solution . It doesn't just prove $k$ is a square but more specifically:

$$ k= {\gcd(a,b)}^2 $$

Here goes the proof:

Let $a > 1$ and $b > a$. In this form: $$ k={{1+{{b^2}\over{a^2}}}\over{{{1}\over{a^2}}+{{b}\over{a}}}} $$ it's easy to see that $$ {b\over a} - 1 < k < {b\over a} + 1 \enspace (*) $$ When $b\over{a}$ is a fraction there are exactly two integers in the interval $$ \left\langle{b\over a} - 1 , {b\over a} + 1\right\rangle $$ (thanks zyx for pointing out my error!).
However when $a$ divides $b$ then $b\over{a}$ becomes an integer.
Then the above open interval can contain only one integer
which of course must be $k$ itself! (**).
We'll use that fact below.

Now if we write $$b=ka+c$$ we see that $$\mid c \mid < a$$ because of (*) above. Substituting this expression in the expression for $k$ gives: $$ k={{a^2+(ka+c)^2}\over{1+a(ka+c)}} \enspace or \enspace k(1-ca) = {a^2+c^2} \enspace \enspace $$ We see that $c$ must be negative and replace $a$ with $b'$ and $-c$ with $a'$ to get: $$ k={{a'^2+b'^2}\over{1+a'b'}} $$ Iterating this process is in fact the Euclidean algorithm (Slightly different, but similar. See remark zyx below) for finding the greatest common divisor of $a$ and $b$ eventually stopping at : $$ a' = \gcd(a,b) \enspace $$ but by that time ${{b'}\over{a'}}$ is no longer a fraction but an integer, so it must be equal to $k$ because of $(**)$. ($a'$ divides $b'$ because $a' = \gcd(a,b)$)
so: $$ {{b'}\over{a'}}={{a'^2+b'^2}\over{1+a'b'}} \text{ or } b' =a'^3 \text{ or }k =a'^2 \text{ or }k= {\gcd(a,b)}^2 $$

Is the above correct or did i miss something? If not could this be a more direct way to prove the famous problem 6?

Let me know what you think!

UPDATE 12/9/2016:
see this link for another solution

$\endgroup$
  • 1
    $\begingroup$ Vieta Jumping is often presented as just contradiction. It is better to say that it provides inequalities; if there are any solutions, there are some satisfying the inequalities. I put a copy of the 1907 Hurwitz paper here: zakuski.utsa.edu/~jagy/Hurwitz_A_1907.pdf This is where I learned the simple idea of a "fundamental solution." $\endgroup$ – Will Jagy Aug 29 '16 at 1:11
  • 8
    $\begingroup$ ciapan: I don't really understand what you mean. I'm answering somebody else's question as i explained above. Because my reputation points at the time were insufficient to answer that post directly. I get a lot of comments like this but don't see what all the fuss is about actually. $\endgroup$ – Rutger Moody Aug 31 '16 at 11:08
  • 3
    $\begingroup$ You're right I know. But it still converges to the gcd but now 'from the other side' $\endgroup$ – Rutger Moody Sep 2 '16 at 6:49
  • 4
    $\begingroup$ Ciapan: I tried to follow your advice. Posted an answer to ensure the 'question' didn't remain open. But now i find my answer deleted again by 'henrik' because the answer didn't provide enough information. So that doesn't work either. Can we just leave it at that? $\endgroup$ – Rutger Moody Sep 2 '16 at 6:54
  • 10
    $\begingroup$ It's amazing how pettily meticulous some people can get on this website, but don't pay too much mind to it, Rutger $\endgroup$ – Spine Feast Sep 2 '16 at 12:16
2
$\begingroup$

Geometric solution to Q6: Consider a rectangle with sides ๐‘Ž, ๐‘ Its diagonal has length $$ \sqrt{a^2+b^2} $$

This diagonal is a side of square A

Area A $$= a^2+b^2$$ Area B = $$ ๐‘. \sqrt{a^2+b^2}$$ Geometrically Q6 becomes equation (1) , $$ ๐‘˜ = Area A / Area B $$

Length ๐‘Ž is projected onto the side square A to yield a length, ๐‘

Now, $$ ๐‘ = ๐‘Ž/cosฯด $$ And $$cosฯด = ๐‘/โˆš{a^2+b^2}$$ So $$๐‘ = ๐‘Ž/๐‘. โˆš{a^2+b^2}$$ Area B $$= ๐‘Ž/๐‘. {a^2+b^2}$$ Then from (1) $$๐‘˜ = ๐‘/๐‘Ž $$ (2)

Now if Area B = $$๐‘Ž๐‘ + 1$$ as in Q6 then $$๐‘Ž๐‘ + 1 = a/b.{a^2+b^2}$$ $$b^2 + ๐‘/๐‘Ž = {a^2+b^2}$$ $$๐‘ = a^3$$ From (2) $$๐‘˜ = a^2,$$ a perfect square

$\endgroup$
  • 1
    $\begingroup$ I don't understand where you got your equation (1) from (what does Area B have to do with anything?). In any case, this can't be correct since you've never used that $k$ is an integer. $\endgroup$ – Eric Wofsey Dec 11 '16 at 8:07
  • $\begingroup$ The Latex syntax is not everywhere correct. But I think I see what you mean. Also it would be nice if you could illustrate with a picture. But I don't think this counts as a solution to Q6. It's more like a geometric reconstruction of the last step of the Euclidean algorithm. Your conclusion is that $ b = a^3 $. But this is generally not the case. You assumed a priori that rectangle B can be constructed as a projection on rect A. That gives a good picture for the last step. But what if B just is not that rectangle? It would be nice if you could construct a picture like this for every step. $\endgroup$ – Rutger Moody Dec 11 '16 at 11:54

Your Answer

By clicking โ€œPost Your Answerโ€, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.