How many n x n matrices are there with entries chosen from the numbers 0,1,...,q-1? How do I prove this?
a)
How many n x n matrices are there with entries chosen from the numbers 0,1,...,q-1?
b)
Let q be a prime. How many matrices as in (a) have a determinant that is not divisible by q? (In other words how many nonsingular matrices over the q-element field are there?)

Hint (Part 1): If we were to construct such a matrix entry-by-entry, we would select one out $q$ possibilities for every entry.  That is, we can uniquely construct each matrix by making $n^2$ independent choices of one out of $q$ different possibilities.
For example: convince yourself that with $q = 3$ and $n = 2$, there are $3^{2^2}$ possible matrices.
Hint (Part 2): This part is a lot trickier.  Note that for $i = 1,\dots,n$, the $i$th column must be outside the span of the first $i-1$ columns.  That is, we must choose an $i$th column that lies outside of an $(i-1)$-dimensional subspace of $\Bbb F_q^n$.
