How to factor 5671? The other day I wanted to factor 5671 in my head. (It turns out to be $53\cdot107$, but I did not know this at the time.)  I quickly ruled out the easy divisors, 2, 3, 5, 7, 11, and 13. At this point I saw no obvious way to proceed short of a very tedious trial division.
But I did notice that 5671 has a residue of 1 modulo 2, 3, 5, and 7. Is there any way to use this coincidence to reduce or simplify the problem of finding a factorization of 5671, perhaps by ruling out certain types of divisors?

As two comments have already pointed towards the Fermat factorization method, let's spell out how one might employ it here in a way suitable for mental operation.
We observe that $49<56<81$, so $\sqrt{5671}\approx 70$ (very roughly).
More precisely, we have $5671 = 70^2-0^2+771$ and start with the triple $(a,b,c)=(70,0,771)$.
Now repeatedly do the following with the current triple $(a,b,c)$:


*

*If $c>0$, subtract $a$ from $c$, increase $a$ by one, subtract the new $a$ from $c$ (using two substractions, we avoid computation of $2a+1$).

*If $c<0$, add $b$ to $c$, increase $b$ by one, add the new $b$ to $c$

*If $c=0$, terminate; we have found factors $a+b$ and $a-b$.


In our case the sequence of computation runs like this:
$$(70,0,771)\\(71,0,630)\\(72,0,487)\\(73,0,342)\\(74,0,195)\\(75,0,46)\\(76,0,-106)$$
Note that the steps until now were only necessary because we started with an awfully rough estimate for $\sqrt N$.
Next we use a littel shortcut as we step immediately to $b=\sqrt{|c|}$ and replace $c$ with $c+b^2$
$$(76,10,-6)\\(77,11,15)\\(78,11,-140)\\(78,12,-117)\\(78,13,-92)\\(78,14,-65)\\(78,15,-36)\\(78,16,-5)\\(78,17,27)\\(79,17,-130)\\\vdots\\(80,27,0)$$ 
Admittedly, it does take a while until one reaches a factorization (I left out eleven more steps here), but at least the single steps are very trivial (only addition and subtractions). One can devise some speed-ups for cases when $|c|\gg a,b$, but I'll leave that as an exercise. Depending on your memorizing capabilities, all this may not be suitable for actually doing a mental factorization, but it is sure good enough for doing it on a paper napkin. Of course, fastest results are obtained when $b$ is small, i.e. the factors are close to $\sqrt N$.
