number theory hint (no solution wanted)

Announcements Posted on
    • Thread Starter
    Offline

    2
    ReputationRep:
    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)
    Offline

    3
    ReputationRep:
    • Thread Starter
    Offline

    2
    ReputationRep:
    (Original post by RDKGames)
    I'm reluctant to watch cos it might reveal too much at once lol
    Offline

    3
    ReputationRep:
    (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).
    Offline

    3
    ReputationRep:
    (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.
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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)
    • Thread Starter
    Offline

    2
    ReputationRep:
    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?
    Offline

    3
    ReputationRep:
    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.
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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
    Offline

    3
    ReputationRep:
    (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.
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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?
    Offline

    3
    ReputationRep:
    (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 &gt; 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} &gt; 0, b_n = 0 for some n. Since we start with b_1 > 0 and we have shown b_1 &gt; b_2 &gt; ..., the only way this could fail is if b_n &gt; 0, b_{n+1} &lt; 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.
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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 (a_1, b_1), ... must eventually have a pair with a_n &gt; 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} &gt; 0, b_n = 0 for some n. Since we start with b_1 > 0 and we have shown b_1 &gt; b_2 &gt; ..., the only way this could fail is if b_n &gt; 0, b_{n+1} &lt; 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.
    ah thanks a lot for your help, thats a much cleaner solution
    Offline

    3
    ReputationRep:
    Basically the method is something called, Vieta Jumping with roots.
    Minimal solutions, it is incredibly useful.


    Posted from TSR Mobile
 
 
 
Write a reply… Reply
Submit reply

Register

Thanks for posting! You just need to create an account in order to submit the post
  1. this can't be left blank
    that username has been taken, please choose another Forgotten your password?
  2. this can't be left blank
    this email is already registered. Forgotten your password?
  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
  2. Slide to join now Processing…

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.

Today on TSR
Poll
How are you feeling about doing A-levels?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read here first

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

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

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