There is a hint to this problem which I don't know how to interpret. The hint is
$$ \text{Hint: Show that} \quad A | \phi \rangle = 0 \leftrightarrow A^{\dagger}A=0. $$
Attempted solution(without using the hint): If $A^{\dagger}A$ is a projector we must have $$(A^{\dagger}A)(A^{\dagger}A)= A^{\dagger}A$$ which implies $$ AA^{\dagger}=I$$ I could say the identity is a projector and I would be done, what am I doing wrong?
Since $A^*A$ is a projector, we have $\sigma(A^*A) = \{0,1\}$. Then also $\sigma(AA^*) = \{0,1\}$.
$AA^*$ is self-adjoint and hence diagonalizable. This implies that the minimal polynomial of $AA^*$ splits into linear factors over $\mathbb{C}$. Its possible zeroes are $0$ and $1$ so the only possible candidates are $x, x-1, x(x-1)$.
Hence $x(x-1)$ annihilates $AA^*$ so $(AA^*)^2 =AA^*$. $AA^*$ is also self-adjoint so we conclude it is an orthogonal projector.
This assumes that we are dealing with matrices. If these are operators on a Hilbert space, then notice that again $B$ self-adjoint and $\sigma(B) = \{0,1\}$ implies that $B^2 = B$. Indeed, the polynomial $p(x) = x(x-1)$ annihilates $\sigma(B)$ so the spectral mapping theorem implies $$\{0\} = p(\sigma(B)) = \sigma(p(B)) = \sigma(B^2 - B)$$ Hence $B^2 - B$ is a normal operator with zero spectrum, so it is $0$.