I was playing around with Fermat's factorization method (https://en.wikipedia.org/wiki/Fermat%27s_factorization_method) where the factors are prime and noticed that either a or b is always divisible by 3. Eg. From that page, N=5959 and a=80 and b=21. This isn't the only example - for every other example I found this was true.
Why is this true? Or can someone provide an example where it's not true? (I never found one.)
You have to assume that $N \bmod 3 \ne 0.$ Otherwise there are counter-examples: $N=15=3\times 5 \rightarrow a=4, b=1$ or $N=21=3\times 7 \rightarrow a=5, b=2$ etc.
Let $N \bmod 3 \ne 0, \; N = a^2-b^2$. Assume both $a,b$ are not divisible by $3.$ So you have $a\equiv\pm 1 \bmod 3$ and $ b\equiv\pm 1 \bmod 3$. Then $a^2\equiv1 \bmod 3,$ $\;b^2 \equiv 1 \bmod 3$ and $N = a^2 - b^2 \equiv 0 \bmod 3$. Contradiction!