A nice problem

[al-mahed]

Main Question or Discussion Point

For how many whole numbers c, − 2007 ≤ c ≤ 2007, exists a whole number x such that x^2 + c is multiple of 2^2007?

 

[al-mahed]

come on guys... this is an olympic problem, from the M.O. from Brazil

 

[CRGreathouse]

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.

 

[al-mahed]

you need to solve by hand

 

[huba]

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.

 

[huba]

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.

 

[huba]

Using the form -(4^k)*(8n-1), I can count 333 residues in [-2007,-1]. With 0 also a residue, I get 670.