Since the interval is symmetric about 0, you're just asking for how many numbers in [-2007, 2007] are quadratic residues mod 2^2007.
sum(n=-2007,2007,issquare(Mod(n,2^2007))) = 670 (15ms in Pari)
Now if you actually want to solve it by hand, you'll need to look over quadratic reciprocity more carefully.
#4
al-mahed
262
0
you need to solve by hand
#5
huba
32
0
Wikipedia, under "quadratic residue", says that a number is a residue mod 2^m (m any natural number) if and only if it is of the form (4^k)*(8n+1).
I counted 336 integers in [1,2007] that are of that form. I thought an equal number might be in [-2007,-1], but that would give me 672, not 670.
Last edited:
#6
huba
32
0
Is it at this point that quadratic reciprocity should be applied? But how if it applies to odd primes?
Something else (in my previous post): m any natural number > 2.
Last edited:
#7
huba
32
0
Using the form -(4^k)*(8n-1), I can count 333 residues in [-2007,-1]. With 0 also a residue, I get 670.