Finding integer solutions logically

[Georgepowell]

How would I find values for A and B such that

$$AB-A-B=1673$$

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.

 

[matt grime]

Try to write the LHS in a factored form.

 

[Redbelly98]

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.

 

[Georgepowell]

...
(A-1)(B-1) = 1674

Then search for two integers whose product is 1674
...

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 :(

 

[CRGreathouse]

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 :(

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.

 

[Georgepowell]

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.

 

[CRGreathouse]

By 'purely logical' I meant a method that does not result in also finding non-integer solutions and ignoring them.

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.

 

[Georgepowell]

1. Find the prime factorization of 1674 (2 * 3^3 * 31).

Am I right in saying that this would involve at least a little bit of trial and error/guessing/estimation?

 

[CRGreathouse]

Am I right in saying that this would involve at least a little bit of trial and error/guessing/estimation?

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.

 

[Georgepowell]

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.

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.

 

[CRGreathouse]

Do you see what I mean?

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.

 

[Georgepowell]

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.

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?

I guess you will want me to define 'a calculation' now

 

[Count Iblis]

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.

 

[CRGreathouse]

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.

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.

 

[Georgepowell]

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.

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.

 

[Georgepowell]

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.

 

[CRGreathouse]

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.

No, because then you could factor that fast and we don't think it's possible to factor that fast.

 

[mistermath]

Another reason why there isn't a "trial and error" thing you can avoid is because you have more variables than equations.