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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook