Yes, it can be done. Yes….
Done.

ah, yes, I remember asking myself the same question, good old times…

Sorry, I just saw this question, but what if N is itself a perfect square?

It seems that if N is not a perfect square then the statement is true.

I am claiming that we can find M to be a prime number satisfying what you want. Assume for now that N is odd.

Using Legendre symbol we need to have (-1/M) = 1 & (N/M) = -1 since Legendre symbol is multiplicative.

To have (-1/M) =1 for a prime number M, it is enough to have M = 1 (mod 4).

Because Legendre symbol is multiplicative we may assume N is square free with at least one prime factor. Say N = p1 * p2…. pn.

I construct a prime number M such that (p1/M) = -1 and (pi/M) = 1 for any i >1.

By reciprocity law we have (pi/M) (M/pi) = 1, since M = 1 mod 4. So we should have (M/pi) = 1 for i>1 and (M/p1) = -1. For the first one we only need to take M = 1 mod pi.

To have the second equality just take M to be ANY non-square number (say a) mod p1. Now we have a series of equations mod different primes and 4. By Chinese Remainder Theorem there is a number b such that any M satisfying this system of equations equals b mod (4* p1 * p2…*pn)

M = 1 mod 4
M = 1 mod pi i>1
M = a mod p1

Now by Dirichlet’s Theorem this has a solution in prime numbers and we are done.

Now if N is square free but even with at least 2 prime factors, the argument remains the same. You just need to make sure p1 is not 2.

If N=2 then we need to have (2/M) = -1 and (-1/M)=1. But we know that (2/M) = -1 when M = 3 or 5 mod 8. So it is enough to take M to be a prime number with M = 5 mod 8.

@BonusQuestion to the rescue! This is precisely what I was looking for.

I’d like to encourage anyone who checks out this question to give some lurve to the answer above.