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

DOI10.1016/J.JNT.2018.09.015MaRDI QIDQ669241zbMATHOpenAlexFDO

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

sum of squarescongruence equation

Mathematics Subject Classification ID

Congruences in many variables (11D79) Counting solutions of Diophantine equations (11D45) 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.

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

• scientific article; zbMATH DE number 1131801 (Why is no real title available?)
• 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
• On divisors of a quadratic form

Cited in

(4)

• On the number of solutions of the equation \(Rx^2 + Sy^2\equiv 1\pmod N\)
• Density of solutions to quadratic congruences.
• Number of solutions of a binary of the equation \(A^2+B^2=C^2+C\)
• A new Andrews-Crandall-type identity and the number of integer solutions to \(x^2 +2y^2 +2z^2 =n\)

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)