48
$\begingroup$

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

$\endgroup$
8
  • 11
    $\begingroup$ 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. $\endgroup$
    – user523628
    Commented Jan 21, 2018 at 23:52
  • 4
    $\begingroup$ 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. $\endgroup$
    – David
    Commented Jan 21, 2018 at 23:57
  • 4
    $\begingroup$ If ever I could understand what is special with this question and such votes $\endgroup$
    – Guy Fsone
    Commented Jan 22, 2018 at 21:27
  • 3
    $\begingroup$ 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. $\endgroup$ Commented Jan 22, 2018 at 21:34
  • 1
    $\begingroup$ Possible duplicate of How to factorise large number without calculator? $\endgroup$
    – Rob
    Commented Jan 23, 2018 at 10:55

1 Answer 1

212
$\begingroup$

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.

$\endgroup$
9
  • 13
    $\begingroup$ @Bernard: Also note that this method does not prove that the factors we got are prime. $\endgroup$
    – user21820
    Commented Jan 22, 2018 at 9:30
  • 14
    $\begingroup$ @user21820 As clarified in a comment, the original question only required finding a prime factor, and 197 is small enough to check by hand. $\endgroup$
    – G_B
    Commented Jan 22, 2018 at 10:26
  • 7
    $\begingroup$ @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. $\endgroup$
    – user21820
    Commented Jan 22, 2018 at 10:33
  • 9
    $\begingroup$ @Rafalon trying to divide by 7, 11 and 13 is enough (for 197). $\endgroup$
    – Will Ness
    Commented Jan 22, 2018 at 20:02
  • 6
    $\begingroup$ @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. $\endgroup$
    – Arthur
    Commented Jan 23, 2018 at 9:54

You must log in to answer this question.