How would you go about finding prime factors of a number like $7999973$? I have trivial knowledge about divisor-searching algorithms.

  • 9
    This is the only context you have to solve the problem. Find a prime factor of 7999973 without a calculator. I got this problem from an old problem book, but there is no explanation or further context. – user523628 Jan 21 at 23:52
  • 4
    Perhaps you didn't read the question carefully... or perhaps you didn't write the question carefully. Finding prime factors (implicitly: all prime factors) of the number, without a calculator, is going to be quite hard. Finding a prime factor (that is: only one asked for), as in your title, is quite easy in this case. – David Jan 21 at 23:57
  • 4
    If ever I could understand what is special with this question and such votes – Guy Fsone Jan 22 at 21:27
  • 2
    Those who don't understand this problem might understand it more if they assumed that it's a problem that is meant to be solvable in a reasonable amount of time. When you take that approach, it's safe to assume there must be some trick or non-linear thinking, as the answer confirms. – Todd Wilcox Jan 22 at 21:34
  • 1
    Possible duplicate of How to factorise large number without calculator? – Rob Jan 23 at 10:55

The thing to notice here is that 7,999,973 is close to 8,000,000. In fact it is $8000000 - 27$. Both of these are perfect cubes. Differences of cubes always factor: $$a^3 - b^3 = (a-b)(a^2+ab+b^2)$$

Here we have $a=200, b=3$, so $a-b= 197$ is a factor.

  • 12
    @Bernard: Also note that this method does not prove that the factors we got are prime. – user21820 Jan 22 at 9:30
  • 12
    @user21820 As clarified in a comment, the original question only required finding a prime factor, and 197 is small enough to check by hand. – Geoffrey Brent Jan 22 at 10:26
  • 6
    @GeoffreyBrent: Yup I know that 197 is prime; I'm just stating for the record that this method in general does not say anything about primality. – user21820 Jan 22 at 10:33
  • 8
    @Rafalon trying to divide by 7, 11 and 13 is enough (for 197). – Will Ness Jan 22 at 20:02
  • 4
    @PeterH Because the original number was suspiciously close to $8\,000\,000$, with all those $9$'s, so he checked to see whether it worked, and it did. It's a standard type of problem, although in my experience, powers of $10$ are more common as starting points for these problems than numbers like eight million. – Arthur Jan 23 at 9:54

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.