Lower Bound on the Probability an LWE Matrix is Primitive For positive integers $q, n, m&gt;n$, how do we derive the lower bound $Pr[A\cdot \mathbb Z_q^m = \mathbb Z_q^n] \geq 1 - \frac{1}{q^{m-n}}$ for a uniformly random matrix $A \in \mathbb Z_q^{n \times m}$? 

I know this probability is equivalent to the probability that each row has gcd 1 with q, $gcd(a_{i,1}, \dots, a_{i,m}, q) = 1$. Also, there is a lower bound on the totient function, $\varphi(q) \geq \sqrt q/\sqrt 2$, but this hasn't led me to a solution for the bound we want.
I think you're overthinking it.

Hint

The event in which $A\cdot \mathbb Z_q^m \neq \mathbb Z_q^n$ is the event in which the matrix $A$ has a rank defect, which is "contained" in the event in which (say) the first row is a linear combination of the other rows.
Now, what's the probability of the latter event?