Is there an algorithm to find integers such that the following holds true : ${a_1}^2 + {a_2}^2 \dots + {a_k}^2 \equiv p $ $(mod $ $n)$, where $p$ is a prime and $n$ is any general integer.

By Lagrange 4 square theorem it is known that value of $k$ will be atmost 4. Also according to this post since, we are working in modular fields, the value of $k$ will be atmost 2, i.e. when it is not a quadratic residue. But I was interested in finding the integers rather than value of $k$. Please suggest an efficient algorithm for the above.

  • $\begingroup$ What do you mean "the maximum value"? Perhaps you meant "at most"? Since if it is true for $\;n=4\;$ then it is true for any $\;m>n\;$ , of course. $\endgroup$ – DonAntonio Jan 8 '17 at 11:15
  • $\begingroup$ Updated the statement. $\endgroup$ – caretaker Jan 8 '17 at 11:18
  • $\begingroup$ can someone please explain how the sum of squares in "modular fields" differ from the regular sum of squares a^2 + b^2 +... c^2 = n?. $\endgroup$ – user25406 Jan 8 '17 at 15:56
  • $\begingroup$ For example, in modular field $4^2 + 1^2 \equiv 3 $ $(mod$ $ 7)$, which is not the case in normal integer system. $\endgroup$ – caretaker Jan 8 '17 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.