Let A be a matrix with entries in Z/nZ. (n is not assumed to be prime.) Then the size of the row span is the size of the column span. All computations are mod n, so both these numbers are finite. 


I believe you can prove this using Smith normal form: both the size of the row span and the size of the column span will be the same after passing to the Smith normal form (lift the matrix entries to Z to compute the Smith normal form). When A is in Smith normal form, these quantities can be easily computed. 


I would like to find a reference for this fact, and would be grateful to anyone who could provide one. 



"Linear algebra" over Z/nZ - reference please!
Your idea of using Smith normal form leads directly to a solution: But you need to verify that for every matrix $M$ with entries in $\mathbb{Z}/n\mathbb{Z}$ there are invertible matrices $A$ and $B$ with entries in $\mathbb{Z}/n\mathbb{Z}$ such that $AMB$ is in Smith normal form. It is essential that $A$ and $B$ be invertible as matrices over $\mathbb{Z}/n\mathbb{Z}$, otherwise the row and column spaces of $AMB$ won't necessarily be the same size as those of $M$.


A ring with the property that every matrix is equivalent to one in Smith normal form is called an elementary divisor ring. In the book "Matrices over Commutative Rings" by William Brown (Marcel Dekker 1993) it is shown (Theorem 15.8 and 15.9) that every principal ideal ring is an elementary divisor ring. It is simple to check that the rings $\mathbb{Z}/n\mathbb{Z}$ are principal ideal rings. So there's the reference you asked for. If you can't find the book by Brown the article by Kaplansky mentioned in the comments has the same material in a more general setting.


