1
$\begingroup$

Given the factors of $2$ integers $a$ and $b$, can you find the factors of the sum of $a$ and $b$ without first multiplying the factors to get $a$ and $b$? This is just something I recently thought of and became curious about. If it is possible, how would one go about doing it?

Example: factors of $a: 3,7$ and factors of $b : 2,2,3 $. What are factors of $a + b$ without first doing $3 \cdot 7$ and $2 \cdot 2 \cdot 3$ and then adding them together and then factoring it?

EDIT: I slightly mis-worded my question and I think I fixed the wording.

$\endgroup$
  • 1
    $\begingroup$ $6$ isn't a prime factor. You can reduce your work by finding common factors ($3$ in your case), but from there it's... tricky. When $a+b=c$, statements about factors of $a$, $b$ and $c$ are usually something related to abc conjecture. $\endgroup$ – Abstraction Dec 4 '15 at 14:38
  • $\begingroup$ @Abstraction Woops, that 6 was supposed to be a 3. I fixed it. $\endgroup$ – EnderShadow Dec 4 '15 at 15:14
  • 1
    $\begingroup$ 3*(7+2*2). Don't know that you'll find an easier way. $\endgroup$ – Morgan Rodgers Dec 4 '15 at 15:17
  • $\begingroup$ @MorganRodgers I realized I slightly misworded the question. $\endgroup$ – EnderShadow Dec 4 '15 at 17:04
2
$\begingroup$

You won't find an easier way. If you could, then you'd have an efficient factorisation algorithm, since any odd integer $n$ is $\frac{n+1}{2} + \frac{n-1}{2}$; inductively, we'd be able to factor $\frac{n \pm 1}{2}$ efficiently, and hence $n$ efficiently. But integer factorisation is a notoriously hard problem (on which the security of the Internet still rests, in many places!), so if there were an easy way like this, we'd have heard about it already.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.