The real reason it works is actually deep magic. Dirichlet's theorem states: given any two positive coprime integers $a$ and $d$, there are infinitely many primes of the form $a + nd$ where $n$ is a positive integer.

This result is one of the deeper facts of analytic number theory. I have no clue in hell how to prove it other than "look it up in Hardy and Littlewood."

Haha. Actually, Hardy and Littlewood in 'An Introduction...' don't prove this result, stating that it is too difficult!

They do prove some subcases, though!