How many whole numbers c make x^2 + c a multiple of 2^2007?

  • Context: Graduate 
  • Thread starter Thread starter al-mahed
  • Start date Start date
Click For Summary
SUMMARY

The problem of determining how many whole numbers c, within the range of -2007 to 2007, make the expression x^2 + c a multiple of 2^2007 has been solved to yield a total of 670 valid integers. This conclusion is reached by analyzing quadratic residues modulo 2^2007, specifically identifying numbers that fit the form (4^k)*(8n+1). The calculations were efficiently executed using the Pari tool, which confirmed the count in a matter of milliseconds. Further exploration into quadratic reciprocity is suggested for a deeper understanding of the underlying principles.

PREREQUISITES
  • Understanding of quadratic residues and their properties.
  • Familiarity with the concept of modular arithmetic, specifically mod 2^m.
  • Knowledge of quadratic reciprocity and its applications.
  • Experience with the Pari tool for computational number theory.
NEXT STEPS
  • Study the properties of quadratic residues mod 2^m in detail.
  • Learn about the application of quadratic reciprocity in number theory.
  • Explore the Pari tool for advanced computational techniques in number theory.
  • Investigate the classification of integers based on their forms, such as (4^k)*(8n+1) and -(4^k)*(8n-1).
USEFUL FOR

Mathematicians, number theorists, and students preparing for mathematical olympiads who are interested in modular arithmetic and quadratic residues.

al-mahed
Messages
262
Reaction score
0
For how many whole numbers c, − 2007 ≤ c ≤ 2007, exists a whole number x such that x^2 + c is multiple of 2^2007?
 
Physics news on Phys.org
come on guys... this is an olympic problem, from the M.O. from Brazil
 
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.
 
you need to solve by hand
 
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:
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:
Using the form -(4^k)*(8n-1), I can count 333 residues in [-2007,-1]. With 0 also a residue, I get 670.
 

Similar threads

MHB Number of solutions for system of equations
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Proving Convexity of the Set X = {(x, y) E R^2; ax + by <= c} in R^2
  • · Replies 5 ·
Replies
5
Views
2K
MHB For which c is there 1/0 solution?
  • · Replies 2 ·
Replies
2
Views
1K
Undergrad Understanding the Results of gcd(x,n)
  • · Replies 8 ·
Replies
8
Views
2K
MHB Smallest subfield of C that contains i
  • · Replies 4 ·
Replies
4
Views
2K
MHB Proof the set with the multiplication is a group
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Show that ##\mathbb{C}## can be obtained as 2 × 2 matrices
  • · Replies 14 ·
Replies
14
Views
3K
Graduate Anti-dual numbers and what are their properties?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Is there a Whole Number Multiple of Pi Closest to a Whole Number?
  • · Replies 5 ·
Replies
5
Views
12K
Undergrad Dfns group action & group, written in terms of the other
  • · Replies 26 ·
Replies
26
Views
911