number theory hint (no solution wanted)

OP

Original post by RDKGames

[video="youtube;L0Vj_7Y2-xY"]https://www.youtube.com/watch?v=L0Vj_7Y2-xY[/video]

I'm reluctant to watch cos it might reveal too much at once lol

Reply 3

Original post by chemphys

I'm reluctant to watch cos it might reveal too much at once lol

For what it's worth, this question is regarded as one of the hardest ever IMO questions (although the techniques for solving it are now a lot more well known and so it would not be regarded so today).

Smallish hint

Reply 4

Original post by chemphys

i feel I'm close but i just need a bit of hint in proving these are the only solution forms (I'm pretty sure they are- though i may be wrong)

Spoiler

Reply 5

OP

Original post by DFranklin

Spoiler

ahh damn - thanks for that - saves me going down the wrong route trying to prove it

oh wait thats just 'one iteration' further in the method i used to find the 2nd form (sum of roots in quadratics)

(edited 7 years ago)

Reply 6

OP

oh i think i might have been on the right lines before- i stupidly didn't continue on from the first 2 forms

yeh I've got a sequence of solutions that get 'larger' so i guess the reverse gets a sequence that gets smaller
and theres only so far you can go before u start going into negatives(i.e. 0,0) - i haven't got a formal proof but thats right line?

(edited 7 years ago)

Reply 7

Yes, you should be able to adapt your approach to go down - I don't think you'll get down to (0,0), but you should get to where it's obvious k must be square.

Reply 8

OP

Original post by DFranklin

Yes, you should be able to adapt your approach to go down - I don't think you'll get down to (0,0), but you should get to where it's obvious k must be square.

ah thanks- i think this is ok but I struggled to get across what i was thinking
let a,b satisfy (a^2+b^2)/(ab+1)=k (*) where a>b (only 1 solution where both the same) for now, let k be a fixed positive integer

then a^2+b^2=k(ab+1) (**)

then there exists a pair a',b' satisfying a'^2+b'^2=k(a'b'+1),where b'=b and a'=kb-a

from (**)/a we get a+b^2/a=kb+k/a so a'=(b^2-k)/a<(b^2-k)/b<b since k>0
so clearly a' is less than b.
clearly we can keep iterating to get smaller and smaller values for the lower integer of the pair of solutions. eventually we should end up with one of the lower value being the square root of k . if this didn't happen eventually we would get a value that is negative for one of the pair but if one of the pair is negative k can't be positive ,a contradiction since we fixed k to be positive integer .

However, if we get to a stage where the lower value of a pair squared =k then we we get the next iteration to be 0. now this leads to the next lowest number being negative but this still allows k to be positive so no 'breaking' the equation there (I'm kind of artificially allowing one of the terms a, b to be negative for this last step but this is ok because its an exception where k is still positive)
so the only way for k to be positive which it must be is for it to equal some b^2

(edited 7 years ago)

Reply 9

chemphys

..

The basic idea looks fine, but some of your arguments are really too vague to really nail this down as a full solution. Words like "clearly" and "should" are always suspect in this kind of thing.

Some thoughts on things you might want to do to clean things up.

If you want to argue that "we can keep iterating", you need to make it very clear that the original conditions are still satisfied. It's kind of trivial, but making a' = b and b' = kb-a would mean that your argument showed that a' > b' and so we have a more direct parallel with the initial scenario with a > b.

Also, with a "we can keep iterating", you generally want to pay more attention to "when do/should we stop?" In this case you should find your argument for finding b' fails when b = 0. So you can see that this is when the iteration stops and then you have k = a^2, so k is a square.

(edited 7 years ago)

Reply 10

OP

Original post by DFranklin

The basic idea looks fine, but some of your arguments are really too vague to really nail this down as a full solution. Words like "clearly" and "should" are always suspect in this kind of thing.

Some thoughts on things you might want to do to clean things up.

If you want to argue that "we can keep iterating", you need to make it very clear that the original conditions are still satisfied. It's kind of trivial, but making a' = b and b' = kb-a would mean that your argument showed that a' > b' and so we have a more direct parallel with the initial scenario with a > b.

Also, with a "we can keep iterating", you generally want to pay more attention to "when do/should we stop?" In this case you should find your argument for finding b' fails when b = 0. So you can see that this is when the iteration stops and then you have k = a^2, so k is a square.

ah thank you, this is exactly the problem I always seem to have in proofs - I usually have the basic idea which i can convincingly explain usually in person to another person but in writing I struggle to convey myself.

yes the first point makes complete sense, thats why later in the paragraph I kept having to refer to the 'smaller of the pair' because I used both the letters a and b at points to refer to the smaller of a pair. Thanks

With the second point , my main argument was that rather than rigidly setting constraints for every set of solution pairs to be positive, I set k to be rigidly positive . This would mean that there can never be a transition from (positive not 0, positive not 0) to (positive not 0 , negative), since this would make the denominator ab+1 <=0, making k not positive. But if b' never reached a 0 this WOULD happen since we get decreasing solutions . So for any solutions the sequence passes through 0.

Just to check for no violations we test what happens given reaching 0. When a given b' passes through 0 for the first time for a positive a' , b''=- a',a''=0 but his doesn't break our important criteria of k being positive( since ( a'' )( b'' )+1=0+1=1. The fact that a'' is negative isn't too important , it just means we stop before getting to that point (in fact if we kept going we'd just oscillate between (a,0) and (0,-a).The important part was that a 0 was reached

The fact that a given b'=0 means that 0=(b^2-k)/a meaning that k=b^2

was that a little better?

(edited 7 years ago)

Reply 11

Original post by chemphys

was that a little better?

It's better, and it's probably enough to get the marks, but it's still a bit unclear.

FWIW, while keeping your basic argument I'd probably argue something like this:

Claim: Our sequence

(a_1, b_1), ...

must eventually have a pair with

a_n > 0, b_n = 0.

Proof of claim: First note that since

a_n = b_{n-1}

this is equivalent to the claim that

b_{n-1} > 0, b_n = 0

for some n. Since we start with b_1 > 0 and we have shown

b_1 > b_2 > ...

, the only way this could fail is if

b_n > 0, b_{n+1} < 0

for some n. We show this is impossible. For since

a_{n+1} = b_n

(and so is > 0), in this case we would have

a_{n+1}b_{n+1} + 1 \le 0

; but then since

k = (a_{n+1}^2+b_{n+1}^2) / (a_{n+1}b_{n+1}+1)

this contradicts our definition of k as a postiive integer.

To prove that k must be a perfect square, all that remains is to note that if

b_n = 0

then

k = (a_n^2+b_n^2)/(a_n b_n + 1) = a_n^2

.

Reply 12

OP