Given a = bc, with a known integer a, is it possible to find all b and c values that are integers quickly without testing each b and c value?

As an example a = 194920496263521028482429080527, is it possible to quickly find integer values for b and c?

  • $\begingroup$ In general it is not easy to find all such $b$ and $c$ (basically this is factorization problem). However once we know the prime factorization of $a$, then yes. $\endgroup$ – Anurag A May 12 at 20:15
  • $\begingroup$ Ok thanks, but is there a quicker way than individually testing all integer values of b and c? $\endgroup$ – so64 May 12 at 20:19
  • $\begingroup$ You need to find the prime factors $\endgroup$ – Andrei May 12 at 20:26
  • $\begingroup$ Integer factorization $\endgroup$ – Robert Israel May 12 at 20:46
  • $\begingroup$ For your example, here's Wolfram Alpha. I hope you were not expecting to do it by hand. $\endgroup$ – Robert Israel May 12 at 20:48

This is a problem of integer factorization. From the factorization of an integer, it is mechanical to write every possible pair of two integers whose product is the given integer.

The method you mention in comments, "a quicker way than individually testing all integer values of $b$ and $c$" is similar to, but less efficient than trial division, trying each integer in $[1,\lfloor \sqrt{n} \rfloor ]$ as a candidate for $b$ and determining whether each choice of $b$ makes $a/b$ an integer or not.

There are much faster methods than trial division. There is not a method that one would consider "fast" for integers of unlimited size.

For your particular example, $$ 194920496263521028482429080527 \\ = 289673451203483 \cdot 672897345109469 $$ is the only product giving that number that does not have $b=1$ or $c = 1$.

| cite | improve this answer | |

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.