1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A nice problem

  1. May 26, 2008 #1
    For how many whole numbers c, − 2007 ≤ c ≤ 2007, exists a whole number x such that x^2 + c is multiple of 2^2007?
  2. jcsd
  3. Jun 3, 2008 #2
    come on guys... this is an olympic problem, from the M.O. from Brazil
  4. Jun 3, 2008 #3


    User Avatar
    Science Advisor
    Homework Helper

    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.
  5. Jun 3, 2008 #4
    you need to solve by hand
  6. Jun 3, 2008 #5
    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: Jun 3, 2008
  7. Jun 3, 2008 #6
    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: Jun 3, 2008
  8. Jun 4, 2008 #7
    Using the form -(4^k)*(8n-1), I can count 333 residues in [-2007,-1]. With 0 also a residue, I get 670.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: A nice problem
  1. No problem (Replies: 2)

  2. Nice Identity (Replies: 2)

  3. Density Problems (Replies: 10)

  4. Inversion problem (Replies: 1)