If p is a real prime that is 3 mod 4, and it is divisible by a+bi, then it is also divisible by a-bi, and by a2+b2. Reduce mod p to show a2 = -b2. Now -1 is the square of a/b, but -1 cannot be a square when p is 3 mod 4. Therefore primes like 71 remain prime in the gaussian integers. These are called inert primes.
If p is 1 mod 4 then there is some x whose square is -1 mod p. Thus p divides x2+1, divides (x+i)×(x-i). Since p cannot divide either factor, some prime a+bi divides p and x+i, and a-bi, a different prime, divides p and x-i. The product a2+b2 divides p, and since p is a prime integer, a2+b2 = p. Thanks to unique factorization, there are no other complex primes lying over p; just these two.
In fact we can calculate a+bi, even when p is huge. Find x by glomming onto a primitive root mod p, and raising it to the (p-1)/4 power. Then run the gcd algorithm on p and x+i.
Since 2 is the product of the prime 1+i and its associate 1-i, all the gaussian primes have been characterized.
Euclid's gcd algorithm applies here, in fact that's how we proved unique factorization. Thus the gaussian integers form a euclidean domain, which is also a pid. In such a ring, prime elements and prime ideals correspond.
Let s and t be different complex primes dividing m, hence they are relatively prime to each other, with a gcd of 1. Use bezout's identity to show that s and t span 1. Thus the ideals generated by s and t span the entire ring.
This holds for any pair of distinct primes s and t dividing m. The same would be true if we used s2 and t3, since these elements are also relatively prime. In fact it holds for any power of s, and power of t, dividing m.
Apply the chinese remainder theorem, and the gaussian integers R, mod m, becomes the direct product of rings, each of the form R/sa, where sa is a factor of m. It is sufficient to characterize these simpler rings.
If s is prime then s generates a maximal ideal, and R/s is a field. When s is a real prime p the resulting field has order p2. When s is a complex prime the gaussian integers mod s fall into a box of area s2 = p. In other words, we have a finite field of order p. We know all about the structure of finite fields, so these component rings are well understood.
Of course one of the components might be R/sa. This is easier to understand when s is a real prime p, but the structure is the same for a complex prime. Every element in this finite ring can be written as a multiple of s, plus a value mod s, and the representation is unique. Each multiple of s is then a multiple of s2, plus s times something mod s, and the representation is unique. Continue this process, writing elements of the ring in base s. Each "digit" admits p possibilities, so the size of the finite ring is pa. Ring elements are added and multiplied just like multi-digit numbers.
Build such a finite ring for each distinct prime factor of m, and take their direct product to describe the gaussian integers mod m.
Note that m need not be real. All of this can be done if m is a complex number.