You are Here: Home >< Maths

# number theory hint (no solution wanted)

Announcements Posted on
TSR's new app is coming! Sign up here to try it first >> 17-10-2016
1. take a ,b to be positive integers (including 0)
i was trying to prove (a^2+b^2)/(ab+1)=integer implies (a^2+b^2)/(ab+1)=square integer

ive come up with two general cases for solutions to form an integer

a=k,b=k^3
AND
a=k^3,b=k^5-k

subbing both these cases clearly makes squares- 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)
2. (Original post by RDKGames)
I'm reluctant to watch cos it might reveal too much at once lol
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
Suppose (a^2+b^2) = k(ab+1) (*) for some integer k. Your general approach will be to show that you can find a "smaller" integer solution (A, B) to (*) unless (A, B) "obviously" require that k must be a square.

(Words in quotes are intentionally vague so to spoil as little as possible).
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:
Show
a=30, b=112 is a solution that doesn't match either of your forms.
5. (Original post by DFranklin)
Spoiler:
Show
a=30, b=112 is a solution that doesn't match either of your forms.
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)
6. 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?
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.
8. (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
9. (Original post by 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.
10. (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?
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 must eventually have a pair with

Proof of claim: First note that since this is equivalent to the claim that for some n. Since we start with b_1 > 0 and we have shown , the only way this could fail is if for some n. We show this is impossible. For since (and so is > 0), in this case we would have ; but then since 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 then .
12. (Original post by DFranklin)
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 must eventually have a pair with

Proof of claim: First note that since this is equivalent to the claim that for some n. Since we start with b_1 > 0 and we have shown , the only way this could fail is if for some n. We show this is impossible. For since (and so is > 0), in this case we would have ; but then since 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 then .
ah thanks a lot for your help, thats a much cleaner solution
13. Basically the method is something called, Vieta Jumping with roots.
Minimal solutions, it is incredibly useful.

Posted from TSR Mobile

## Register

Thanks for posting! You just need to create an account in order to submit the post
1. this can't be left blank
2. this can't be left blank
3. this can't be left blank

6 characters or longer with both numbers and letters is safer

4. this can't be left empty
your full birthday is required
1. Oops, you need to agree to our Ts&Cs to register

Updated: September 28, 2016
TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Today on TSR

### How does exam reform affect you?

From GCSE to A level, it's all changing

Poll
Useful resources

## Make your revision easier

### Maths Forum posting guidelines

Not sure where to post? Read here first

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

Can you help? Study help unanswered threads

## Groups associated with this forum:

View associated groups
Study resources

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.