This was a fun problem. There may be a simpler answer, but this is what I came up with (eventually). And yeah, it's induction on r.

Suppose n is a quadratic residue mod , i.e. there exist integers a,k such that . If k is even, then k=2c and then and we're done, so assume k odd.

Then

Since k+a is even and if , we have that mod .

That just leaves the base case, which is trivial: is a quadratic residue mod 8.