Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Generalizations of a classical theorem in number theory

Author: Richard H. Hudson
Journal: Math. Comp. 30 (1976), 649-656
MSC: Primary 10A10
MathSciNet review: 0404112
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A classical theorem conjectured by Jacobi asserts that for an odd prime p, the sum of the quadratic residues in the interval (0, p) is less than the sum of the quadratic nonresidues if and only if $ p \equiv 3 \pmod 4$. We generalize Jacobi's problem to kth powers $ \pmod p,k > 2$, and we consider in some detail a generalization of Jacobi's conjecture to quadratic residues and nonresidues $ \pmod n$, n an arbitrary integer $ > 2$. From the set of least positive residues $ \pmod n$, let $ {c_0}$ denote the subgroup of quadratic residues $ \pmod n$ and let $ {c_1},{c_2}, \ldots ,{c_t}$ be the cosets which can be formed with respect to this subgroup. Computer data supports the following generalized Jacobi conjecture: The sum of the elements in $ {c_0}$ is less than or equal to the sum in any of the other cosets for every integer $ n > 2$, a surprising conjecture, especially in view of the fact that counterexamples are easily obtained for $ k = 4,6,8,10$, etc. (The coset sums are identical for odd k and prime modulus.) We resolve the generalized Jacobi conjecture in the affirmative when, for example, n is an integer admitting a primitive root, or $ n = {2^\alpha },\alpha \geqslant 3$. (Here we give explicit formulae for the four coset sums.) For $ n = 2{p^\alpha }$, our proof that the quadratic residues and the quadratic nonresidues $ \pmod n$ have the same sum for odd prime p if and only if $ p \nequiv 3 \pmod 8$ is purely, elementary. On the other hand, we need Dirichlet's class number formula for quadratic number fields with discriminant $ - p \equiv 5 \pmod 8$ to show that the sum of the quadratic nonresidues strictly exceeds the sum of the quadratic residues $ \pmod {2p^\alpha }$ if $ p \equiv 3 \pmod 8$. Computer data gives rise to a host of interesting problems we are unable to resolve. For example, if $ n = 2p_1^{{\alpha _1}}p_2^{{\alpha _2}} \cdots p_r^{{\alpha _r}},1 \leqslant i \leqslant r$, we conjecture that a sufficient condition that the coset sums not be identical is that we have $ {p_i} \equiv 3 \pmod 8$ for every i. It is not hard to show that the coset sums are identical if every $ {p_i} \equiv 1 \pmod 4$. However, the problem of finding a necessary condition is very difficult since, e.g., the coset sums are not identical for $ n \leqslant 1146$ when $ n = 2 \cdot 3 \cdot p$ if $ p \equiv 23 \pmod {24}$, but the sums are identical if $ p \equiv 7 \pmod {24}$.

References [Enhancements On Off] (What's this?)

  • [1] RAYMOND AYOUB, An Introduction to the Analytic Theory of Numbers, Math. Surveys, no. 10, Amer. Math. Soc., Providence, R. I., 1963. MR 28 #3954. MR 0160743 (28:3954)
  • [2] L. E. DICKSON, History of the Theory of Numbers. Vol. 3, Washington, 1919.
  • [3] WILLIAM JUDSON LEVEQUE, Topics in Number Theory. Vol. 1, Addison-Wesley, Reading, Mass., 1956. MR 18, 283. MR 0080682 (18:283d)
  • [4] LEO MOSER, "A theorem on quadratic residues," Proc. Amer. Math. Soc., v. 2, 1951, pp. 503-504. MR 12, 804. MR 0041159 (12:804g)
  • [5] K. K. NORTON, "Upper bounds for k-th power coset representatives modulo n," Acta Arith., v. 15, 1968/69, pp. 161-179. MR 39 #1419. MR 0240065 (39:1419)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 10A10

Retrieve articles in all journals with MSC: 10A10

Additional Information

Article copyright: © Copyright 1976 American Mathematical Society

American Mathematical Society