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."