integer x  ... -6 -5 -4 -3 -2 -1  0  1  2  3  4  5 ...
mod x 3    ...  0  1  2  0  1  2  0  1  2  0  1  2 ...

The sequence above satisfies the equation mod (x+3) 3 = mod x 3 for any x. Note how 0 1 2 is continuously repeated.

Note that in Haskell we have both

mod (-4) 3 == 2
rem (-4) 3 == -1

where

integer x  ... -6 -5 -4 -3 -2 -1  0  1  2  3  4  5 ...
rem x 3    ...  0 -2 -1  0 -2 -1  0  1  2  0  1  2 ...

mod x y is the "remainder" of div x y where the division is rounded down (towards -infinity). Instead rem x y is the remainder of quot x y where the division is rounded towards zero (so the "remainder" can be negative).

$p \equiv 3 \pmod 4$ means that $p = 4 k + 3$ for some $k$, or in other words that the remainder when you divide $p$ by $4$ is $3$.

Note that if you take an odd number and divide it by 4, you'll either get 1 or 3 as a remainder, because if you got 0 or 2 as a remainder then the original number would have had to have been even.

So every odd number (and hence every prime other than 2) satisfies either $p \equiv 1 \pmod{4}$ or $p \equiv 3 \pmod{4}$.

There is no dearth of primes congruent to 3 (mod 4), so there is no shortage of ways to find them. You can use pretty much any technique you'd use to generate primes and then just check the the resulting prime is congruent to 3 (mod 4).

In fact, $2^{16}$ is a small enough number that you can simply calculate every prime with 16 or fewer bits by brute force and then throw out all the ones that are congruent to 1 (mod 4), with the whole process finishing in a fraction of a second.