I’m turning in my thesis right now, and there’s one piece that should be fairly straightforward using quadratic reciprocity, but it seems so obvious I don’t want to bother (and not straightforward enough to actually do). So I thought I’d throw it out to fluther, and see if anyone wants to help me finish this thing out, because it feels like a bit of a chore for me, but I thought some folks here might enjoy it. I don’t know if it’s technically homework, but I thought you all might humor me here.

Here’s the problem: given some positive integer N, can you choose an integer M > N such that ±N is not a perfect square modulo M?

Clearly it can be done. I’d love to see a swift argument that says so.