A nice problem

  • Thread starter al-mahed
  • Start date
  • #1
261
0

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?
 

Answers and Replies

  • #2
261
0
come on guys... this is an olympic problem, from the M.O. from Brazil
 
  • #3
CRGreathouse
Science Advisor
Homework Helper
2,820
0
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
261
0
you need to solve by hand
 
  • #5
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
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
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.
 

Related Threads for: A nice problem

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
15
Views
2K
Replies
3
Views
683
Replies
4
Views
662
Top