Is every number mod N almost a square?

Question

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.)

Answer 1

You already know $tm\equiv x^2\pmod{N}$ is always solvable for $t,x$ when $\gcd(t,N)=\gcd(m,N)=1$.

It's because $(t,x)=(m^{-1}x^2\bmod N,x)$ is a solution, for any integer $x$.

You're asking if $tm-x^2=Nk$ is always solvable for $t,x,k$, where every letter is an integer and $\gcd(t,N)=1$ and $\gcd(m,N)>1$.

The answer is no. Take a prime divisor $p$ of $\gcd(m,N)$. Then

$$p\mid tm-Nk\implies p\mid x^2\implies p^2\mid x^2\implies p^2\mid tm-Nk$$

This gives a contradiction when $p^2\mid N$ and $p^2\nmid m$ (since $\gcd(p^2,t)=1$).

So for example: $tp\equiv x^2\pmod{p^2}$ with $p$ any prime, $\gcd(t,p^2)=1$, is not solvable.

Concerning your edit, it's irrelevant whether $p$ is even or not.

Answer 2

There are no solutions to $x^2 \equiv 2t \pmod 8$ where $t$ is odd.

Answer 3

Let $m=2,N=4$. We have no solution to $tm\equiv x^2\bmod $ since $tm\equiv t2\equiv 2$ which is $4$ is $(t,N)=1$.