2
$\begingroup$

What is the largest prime factor of the number 600851475143 ?
This is the third problem of Project Euler.

How to approach this mathematically (without computer programming) ?

  • 1
    @Asaf I've added the [tag:project-euler] tag, since it is explicitly mentioned in the question. If you don't think this is correct, feel free to remove the tag. (Based on [tag wiki](http://math.stackexchange.com/tags/project-euler/info), I am not sure whether the intended use of this tag is for everything related to PE, or just for question which are directly copied from there. It seems that this question is different from the question at PE, if PE expect program ass a solution.)2012-06-22

2 Answers 2

6

Well the point of Project Euler is to program. This is a problem that you could solve by hand but it would take you quite a while.

Factorisation is not a simple thing to do by hand for numbers this big (unless you have some special insight into divisibility by certain special primes).

Just use the bog standard test, square root and check divisibility of primes upto this. Once you find one, divide out and start again. In the end you will have a number that you cannot do this process to. This will be the largest prime factor.

  • 3
    Most divisibility rules for small numbers depend on nice things about the multiplicative orders of $10$ mod $n$. If $n$ gets bigger then chances are the order gets bigger and so nothing much is gained by using such a divisibility rule.2012-06-22
-2

You can use the free R software for this (using the 'gmp' package)

factorize(600851475143)

Big Integer ('bigz') object of length 4:

[1] 71 839 1471 6857

Hence 600851475143 = 71 * 839 * 1471 * 6857

  • 0
    Welcome to the site ! I do noit think that this answers the question.2016-12-29