Largest Prime Factor
Find the largest prime factor of 6 6 4 − 4 6 4 .
The answer is 1607133116929.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
6 6 4 − 4 6 4 = 2 6 4 ( 3 6 4 − 2 6 4 ) = 2 6 4 ( 3 3 2 + 2 3 2 ) ( 3 3 2 − 2 3 2 )
= 2 6 4 ( 3 3 2 + 2 3 2 ) ( 3 1 6 + 2 1 6 ) ( 3 1 6 − 2 1 6 )
Now, 3 3 2 + 2 3 2 = 1 1 5 3 × 1 6 0 7 1 3 3 1 1 6 9 2 9
Of the other factors in the product, the largest one is 3 1 6 + 2 1 6 = 4 3 1 1 2 2 5 7 . Regardless, of the other factors being prime or composite, it can be said that the largest prime factor in this case would be 1 6 0 7 1 3 3 1 1 6 9 2 9
How do you know that 1607133116929 can't be further factorized?
Log in to reply
Can this be solved efficiently without using a computer?
Log in to reply
Yes, with plenty of time and patience and nothing else better to do.
Log in to reply
@Pi Han Goh – I meant efficiently. I don't consider checking all primes less than the square root of 1607133116929 efficient enough. :D
Log in to reply
@Jesse Nieminen – In that case, I doubt there is an efficient approach. Primality testing is mainly left for computers to do.
Can be solved in more easier way by repeatedly factorizing it
I used a computer program to calculate the prime factors. The prime factors are 2,601,1253279,8097823. So 6 6 4 − 4 6 4 = 2 1 1 3 × 6 0 1 × 1 2 5 3 2 7 9 × 8 0 9 7 8 2 3
I don't really see an easy way to do this. And anyway, the 'correct answer' is definitely wrong.
Edit: as a matter of fact: 2 3 2 + 3 3 2 doesn't equal 1 6 0 7 1 3 3 1 1 6 9 2 9 at all...
Double edit: I'm stupid, ignore my comment
Log in to reply
In my comment, I say that 3 3 2 + 2 3 2 = 1 6 0 7 1 2 2 1 1 6 9 2 9 × 1 1 5 3 . You had mistook it.
Further, I think that your factorization is wrong. The reasoning is thus :
The last digit of 6 6 4 − 4 6 4 : The last digit of any power of 6 would be 6 and the last digit of any even power of 4 would also be 6 . Hence, the last digit of the difference would have to be 0 .
The last digit of the factorization : From the above logic, it is clear that at least one of the prime factors should be 5. But, that is not the case in the proposed factorization.
Log in to reply
You are indeed correct, my apologies. It seems python does not handle divisions with large digits very well, as my program works perfectly for numbers smaller than about 12 digits.
It is not a very good problem.