1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding integer solutions logically

  1. Mar 28, 2009 #1
    How would I find values for A and B such that

    [tex]AB-A-B=1673[/tex]

    Where A and B are integers?

    I know the answer (28 and 63), but I want to know how to arrive at that answer without any guessing, or at least with a minimum amount of guessing.

    Are there any other solutions? I just made this question up so there might be.

    If it is not possible or just very very difficult then tell me.
     
  2. jcsd
  3. Mar 28, 2009 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Try to write the LHS in a factored form.
     
  4. Mar 28, 2009 #3

    Redbelly98

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    I would factor the expression on the left, adding/subtracting constants as necessary. It's easier to solve as the product of two integers.


    AB - A - B = 1673
    A(B-1) - B = 1673
    A(B-1) - B +1 = 1674
    A(B-1) - (B-1) = 1674
    (A-1)(B-1) = 1674

    Then search for two integers whose product is 1674.

    To find a solution, A-1=2 or A=3 is an obvious one. Even more obvious is A-1=1.

    To find all solutions, you only need to search up to √1674 ≈ 41, so it shouldn't take too long.
     
  5. Mar 28, 2009 #4
    Good answer, that makes it a lot easier. It still involves 'searching' though.

    Is there a way to do it without any searching? i.e. finding some equations and rearranging them to get A = 28, B = 63 (or any other answer).

    Sorry if I am asking too much. but finding integer solutions is a wide area of maths and if there isn't a purely logical way of finding solutions then I have lost my faith in maths :(
     
  6. Mar 28, 2009 #5

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Searching up to the square root is logical, just difficult (in some cases -- not so much here). Integer programming is one of the difficult areas of math, where linear programming (its real-number equivalent) is easy.

    If you're saying that your faith in math is conditional on its ease, I hate to break it to you -- math can be hard.

    Now in this particular case it's easy to see that solving the problem is essentially just factoring a number. There are asymptotically faster methods of factoring than trial division, fastest of wghich is the number field sieve. But if you're criticizing this method for being too hard, the NFS is certainly thr wrong way to go. It's very difficult to implement.
     
  7. Mar 28, 2009 #6
    Please note that I was only joking about 'loosing my faith' in maths. I know it is hard.

    By 'purely logical' I meant a method that does not result in also finding non-integer solutions and ignoring them.
     
  8. Mar 28, 2009 #7

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    1. Find the prime factorization of 1674 (2 * 3^3 * 31).
    2. Construct from #1 a list of factors dividing 1674. There are 16.
    3. For each divisor d, let a = d + 1 and b = 1674/d + 1.
     
  9. Mar 28, 2009 #8
    Am I right in saying that this would involve at least a little bit of trial and error/guessing/estimation?
     
  10. Mar 28, 2009 #9

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I'm not sure what you'd consider "trial and error/guessing/estimation". Why don't you look at some integer factorization algorithms and tell us? Pollard's rho, Dixon's method, the continued fraction method, S/G NFS, etc.
     
  11. Mar 28, 2009 #10
    1. Pollard's rho algorithm

    quote from wikipedia:
    Output: a non-trivial factor of n, or failure.

    could result in failure. So trial and error.

    2.Dixon's method

    Another Wikipedia quote:
    ...many values of x are tested to see if p(x) factors completely over the factor base. If it does...

    many values tested. So trial and error.

    Do you see what I mean?

    An example of what I mean is trying to find a real-number solution to x²+2x-8=0. You could use a simple trial and error method and factorise it to get (x-2)(x+4)=0 so x=2 or -4. Or you could complete the square and find the solution without any trial and error.

    just a note: I tried to read the Wikipedia articles on the factorisation methods, but I didn't understand them much. So I just picked those quotes because I thought I could interpret them as 'trial and error'. I might be wrong.
     
    Last edited: Mar 28, 2009
  12. Mar 29, 2009 #11

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    No. I see that if an algorithm can output MAYBE or FAILURE or ERROR (or anything but FACTOR IS ___) that you'd consider it trial and error. But I don't understand which of the methods that don't include these other outputs you'd consider trial and error.

    Edit: To put this anther way: I think the answer to your problem has more to do with your definition of trial and error than any real questions about factorization or Diophantine equations, so until I understand that definition well I won't be able to be much use.
     
  13. Mar 30, 2009 #12
    I don't understand the specifics of the algorithms you told me about, so I can't really comment on them. You can ignore anything I said about them in my last comment because they might not have made any sense. Sorry.

    How about this as a definition:

    If the algorithm can find the answer within a predefined number of calculations (that does not depend on the input), then it is not trial and error. If the length of the process does not have a limit with increasingly difficult inputs, then it IS trial and error.

    E.G.

    2a= b (where b is the input and a is the output)

    The non-trial and error version would be to output a=b/2 (one calculation for any input)

    The trial and error version would try every value for a up to b. So as the input increases in size, the amount of calculations increases.

    With this definition, do the algorithms that you mentioned fit in the trial-and-error category?

    Trial-and-error might not be the right word to use, but I couldn't think of another one. So sorry for any confusion from that.

    Am I making any sense? :redface:

    I guess you will want me to define 'a calculation' now
     
  14. Mar 30, 2009 #13
    The algorithm will at the very least have to consider the data by which the input is specified. Now, the size of the bitstring encoding a number will be given by the logarithm of the number (in base 2). Therefore the number of operation will have to grow at least logarithmically with the size of the numbers.
     
  15. Mar 30, 2009 #14

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    That's a fine definition: constant arithmetic time complexity. That's a very limited class! It's inside L and I think NC^1.

    Factorization is believed to be outside L (like most useful algorithms), so it seems likely that all factorization algorithms are "trial-and-error". Other algorithms you'd consider trial-and-error:
    * Any sorting algorithm
    * Any searching algorithm
    * Any matrix multiplication algorithm
    etc.
     
  16. Mar 30, 2009 #15
    BRILLIANT! A solution to my problem :p. I was worried you would pick another hole in my question. I thought of that definition while lying in bed half asleep so I'm glad it does the job.
     
  17. Mar 30, 2009 #16
    So back to my original question.

    Is there a way of finding integer solutions to equations like the one I mentioned without using any algorithms that are "outside L" whatever that means.
     
  18. Mar 30, 2009 #17

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    No, because then you could factor that fast and we don't think it's possible to factor that fast.
     
  19. Apr 3, 2009 #18
    Another reason why there isn't a "trial and error" thing you can avoid is because you have more variables than equations.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook