Let $m,N\in\mathbb{N}$ not necessarily coprime. I'm interested in finding solutions $t,x$ for the modular equation $$tm\equiv x^2 \mod N,$$ where $\gcd(t,N)=1$. Is there always a solution for this equation? This is obviously the case for $(m,N)=1$, but I wasn't successful in finding any general statements.
EDIT: I've been implicitly assuming $N$ to be odd. What's the situation with this additional assumption? (Actually, that's the case I'm most interested in.)
$tm\equiv x^2 \pmod N$
. See also TeX.SE: tex.stackexchange.com/questions/137073/… $\endgroup$