Problem #3 in Project Euler:
What is the largest prime factor of the number $600851475143$?
I want to solve this by hand. (I am doing this with all problems.) What techniques would allow me to figure this out? (Yes, I checked the prime factors up to $53$, but I got quite tired.)
On
Since you're bored, you might try this: Multiply the first few primes together and call it $M$. Then compute the gcd of $M$ and your number by Euclidean algorithm. Since your number has about 12 digits, use enough primes so that $M$ is 14 or 15 digits. By Lame's theorem, this should take at most 5 times 12 = 60 steps. If the gcd turns out to be different from 1, you've found a factor. If not, then make a new $M$ of 14 or 15 digits by multiplying the next few primes together and repeat.
If I were really doing this by hand, I think I'd make $M$ as large as I could stand (maybe 50 digits), because after the first step in Euclidean algorithm, both numbers would be less than 12 digits. So I could eliminate a lot of candidates at once, at the price of one horrendous long division.
First and foremost: there is no known fast general-case algorithm for factorization (that's the reason RSA encryption exists). Any hope you might have to solve the problem by hand lies in making some lucky guess.
Guess 1 (not lucky): suppose for our $N$, $N=ab$, $|a-b|$ is small. Then we have: $$N = ab = ({a+b \over 2})^2 - ({a-b \over 2})^2 \\ (\lceil \sqrt N \rceil + \delta)^2 - N = m^2$$ where $\delta$ is some small natural number. Testing $\delta$ from $0$ to $10$ fails in our case.
Guess 2 (lucky, but cheating): the method above also works for $pN$ where $p$ is odd. Let $p=55$, then $\lceil \sqrt {pN} \rceil = 5748638$, $(\lceil \sqrt {pN} \rceil + 1)^2 - pN = 19219456 = 4384^2$.