Fast computation of the number of solutions to x₁^2 + + x_k^2 n

DOI10.1016/J.JNT.2018.09.015MaRDI QIDQ669241zbMATH OpenOpenAlexFDO

Authors José María Grau, Antonio M. Oller Marcén

Publication date 20 March 2019

Published in Journal of Number Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.04295

zbMATH Keywords

congruence equationsum of squares

Mathematics Subject Classification ID

Counting solutions of Diophantine equations (11D45) Congruences in many variables (11D79) Computer solution of Diophantine equations (11Y50)

Abstract: In this paper we study the multiplicative function $h{o}_{k,lambda}(n)$ that counts the number of incongruent solutions of the equation $x_1^2+cdots+x_k^{2}equivlambdapmodn$. In particular we give closed explicit formulas for $h{o}_{k,lambda}(p^s)$ with a arithmetic complexity of constant order.

Review text

Let \(k, \lambda \), and \(n\) be positive integers and let \(\rho_{k, \lambda}(n)\) be the number of solutions of the equation \[ x_1^2+\dots+x_k^2 \equiv \lambda \pmod n \] in \( (\mathbb{Z}/n\mathbb{Z})^k\). Identities for \(\rho_{k, \lambda}(n)\) have already been derived using Gauss and Jacobi sums, but they are inefficient because their arithmetic complexity is \( \Theta (n^k)\). More recently, and under some additional restrictions, an efficient algorithm has been provided in [\textit{S. Li} and \textit{Y. Ouyang}, J. Number Theory 187, 41--65 (2018; Zbl 1430.11047)] to compute the number of solutions of the equation \[ \alpha_1x_1^{m_1}+\dots+\alpha_kx_k^{m_k} \equiv \lambda \pmod n \] Using elementary techniques, the authors of the present paper complete the quadratic case considered in the paper above, to give closed explicit formulas for \(\rho_{k, \lambda}(p^s)\) with an arithmetic complexity of constant order. This improves previous work of \textit{L. Tóth} [J. Integer Seq. 17, No. 11, Article 14.11.6, 23 p. (2014; Zbl 1321.11041)].

Recommendations

• scientific article; zbMATH DE number 700544
• The Number of Solutions of a Certain Quadratic Congruence Related to the Class Number of ℚ(√p
• Counting solutions of quadratic congruences in several variables revisited
• scientific article; zbMATH DE number 123855
• scientific article; zbMATH DE number 883122

Cites work

• An O(M(n) logn) Algorithm for the Jacobi Symbol
• Counting invertible sums of squares modulo n and a new generalization of Euler's totient function
• Counting solutions of quadratic congruences in several variables revisited
• Counting the solutions of \(\lambda_1 x_1^{k_1} + \dots + \lambda_t x_t^{k_t} \equiv c \bmod n\)
• Fast multiplication of large numbers
• Faster integer multiplication
• scientific article; zbMATH DE number 1131801 (Why is no real title available?)
• On divisors of a quadratic form

Cited in

(6)

• On the number of solutions of the equation \(Rx^2 + Sy^2\equiv 1\pmod N\)
• Number of solutions of a binary of the equation \(A^2+B^2=C^2+C\)
• Density of solutions to quadratic congruences.
• A new Andrews-Crandall-type identity and the number of integer solutions to x^2 +2y^2 +2z^2 =n
• Linear congruences and a conjecture of Bibak.
• Generalizations of Euler's -function with respect to systems of polynomials of several variables

This page was built for publication: Fast computation of the number of solutions to \(x_1^2 + \cdots + x_k^2 \equiv \lambda \pmod{n}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q669241)