Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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) ?

share|improve this question
7  
Without using a computer? Are you for serious? –  Cocopuffs Jun 22 '12 at 9:56
10  
Here's a challenge: Try to think of a title that would be more broadly applicable to all questions on this site than the one you chose. –  joriki Jun 22 '12 at 10:03
1  
The topic of Project Euler questions has been discussed on meta before. Voting to close (although I don't know what reason to catalog this under). –  Asaf Karagila Jun 22 '12 at 10:28
    
@Asaf I've added the 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, 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.) –  Martin Sleziak Jun 22 '12 at 10:38

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
4  
Use Divisibility Rules instead of brute force division to check for factors, divide and continue... Maybe you have to invent some rules on your own (don't forget to update the Wiki page in this case :-). –  draks ... Jun 22 '12 at 10:28
    
This would work for small prime factors...however, I don't know of any divisibility rules for say the prime $73$. You would have to mess about to derive one. –  fretty Jun 22 '12 at 10:48
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. –  fretty Jun 22 '12 at 10:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.