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