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

DOI10.1016/J.JNT.2018.09.015zbMATH Open1418.11056arXiv1610.04295OpenAlexW2896587918MaRDI QIDQ669241FDOQ669241

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)

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.

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

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

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)

Cites Work

• Faster integer multiplication
• Title not available (Why is that?)
• Fast multiplication of large numbers
• On divisors of a quadratic form
• 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\)
• Counting invertible sums of squares modulo \(n\) and a new generalization of Euler's totient function
• An O(M(n) logn) Algorithm for the Jacobi Symbol

Cited In (4)

• 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\)
• On the number of solutions of the equation \(Rx^2 + Sy^2\equiv 1\pmod 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)