Let n=p*q (p and q are odd prime). Let a mod(p)=(q-p). The numbers a and n are known. Can you find p and q? Thank you.
p^2 + ap - n = 0, which is a quadratic equation in terms of "p". Since the discriminant is a^2 + 4n > 0, this will have a solution via the quadratic equation.
Now this case assumes that a < p. Hence if our given "a" is small enough, we can just check all the prime numbers 2,3,5......that are < a. If we find a prime factor first, then as Nehushtan points out, were already done but if not, we can solve this easily via the quadratic formula above as our initial assumption will have been justified.....
2) FOR GENERAL CASE (ie "a" is too large to be efficiently solved as described above), we have a - kp = q - p for some "unknown" integer k and we have q = a + (k-1)p..........Following along the same lines as before, we get (k-1)p^2 + ap - n = 0.........Since we do not know what "k-1" is we cannot solve directly via quadratic formula, however because we know that "p" is an integer, it follows that a^2 + 4 x (k-1) x n is a square...........From here I'm not sure of any method other than a "brute force" approach that will efficiently solve for p.
Here is an example :
We have to solve the following equation :
It is easy to factorize n in this case.
955 mod 71 = 32
But if n is 400 digit-number it will be a headache.
What is the added information that we need to solve it even if n is a huge number?
I assume that I have found a mathematical way to find the number a.
If a^2 < n / 2, then a < p (where p is the smaller prime factor of n) and the problem can be solved via the quadratic formula.
I don't know how it can be solved more generally, but as the p < q < 2p, the problem does make using the "Fermat factoring method" of n more desirable (keep in mind that for a 400-digit number, this method will still be inefficient).
That would be quite the discovery! However keep in mind that the condition "a mod(p) = q-p" would rarely hold for most composites that are the product of two primes.I assume that I have found a mathematical way to find the number a.