Why does $\operatorname{null}(A) = \operatorname{null}(A^TA)$, intuitively? It's easy to show that the nullspace of $A$ and the nullspace of $A^TA$ are the same.
But intuitively what does that mean?  Or maybe the better question to ask first is, intuitively how does $A^TA$ relate to $A$?
 A: The most intuition-friendly method is to compare the nullspaces directly.  Remember that if $Ax = b$ is a (possibly overdetermined) system of equations, then $A^TAx = A^Tb$ describes the least-squares solution to that system of equations.  That is, any solution to $A^TAx = A^Tb$ minimizes $\|Ax - b\|$.
Along those lines: if $x$ is in the nullspace of $A$, then it is a solution to $A^TAx = A^T0$, which means it is a least squares solution to $Ax = 0$.  So, $x$ minimizes $\|Ax - 0\| = \|Ax\|$.  However, clearly the minimum of $\|Ax\|$ is $0$, so it must be that $Ax = 0$.  So, if $x$ is in the nullspace of $A^TA$, then it must be in the nullspace of $A$.

There are some nice descriptions of $A^TA$ itself. In particular, polar decomposition tells us that $A = U\sqrt{A^TA}$ for some matrix $U$ satisfying $U^TU = I$.  Since $\sqrt{A^TA}$ is a positive definite matrix, it is a "pure squish/stretch" of space along perpendicular axes.  Since $U^TU = I$, $U$ is a mapping into (possibly higher dimensional) space the rotates or reflects, but doesn't distort.
What we get out of all this is that $A^TA$ encodes all of the streching/squishing that $A$ does.  If a vector $x$ is in the kernel of $A$, then the corresponding axis is "squished to $0$", which means that $A^TAx$ must also be zero.   Conversely, if $A^TAx = 0$, then $A$ squishes $x$ to zero, which means that $Ax = 0$.
A: There are a bunch of different answers to this question. My preference is based on the "four fundamental subspaces" which are the focus of chapter 2 of Gilbert Strang's linear algebra book. Here the relevant relationship is that the null space of $A^T$ is the orthogonal complement of the column space of $A$. This is because the equation $Ax=0$ can be understood as "the vector $x$ is orthogonal to each row of $A$", and the rows of $A$ are the columns of $A^T$.
Once you understand that, it's straightforward: to have $A^T A x=0$ you have to have $Ax$ in the null space of $A^T$. But $Ax$ is in the column space of $A$, and the only vector in common between the column space of $A$ and the null space of $A^T$ is the zero vector. So you must have $Ax=0$.
A shorter but maybe less enlightening answer:


*

*$Ax=0 \Rightarrow A^T Ax=A^T 0 = 0$.

*$A^T A x = 0 \Rightarrow x^T A^T A x = \| Ax \|^2 = 0 \Rightarrow \| Ax \|=0 \Rightarrow Ax=0$.


That first bullet is trivial (it would work if you replaced $A^T$ with any $B$), but that second bullet has some geometric content to it.
