# Primes as sum of squares in finite field

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.

• 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. – DonAntonio Jan 8 '17 at 11:15
• Updated the statement. – caretaker Jan 8 '17 at 11:18
• 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?. – user25406 Jan 8 '17 at 15:56
• For example, in modular field $4^2 + 1^2 \equiv 3$ $(mod$ $7)$, which is not the case in normal integer system. – caretaker Jan 8 '17 at 16:39