MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $f(n)$ be the number of points on the unit sphere $x^2 + y^2 + z^2 = 1\; (\mod n)$ with $x,y,z \in \mathbb{Z}/n\mathbb{Z}$

This is sequence A087784 in the Online Encyclopedia of Integer sequences:

1, 4, 6, 24, 30, 24, 42, 96, 54, 120...

There is a (due to Bjorn Poonen) indicating some regularity to the solutions to this congurence

$$f(n) = n^2* \left\{\begin{array}{cl}3/2&\text{if}\quad\quad 4|n \\ 1 &\text{otherwise} \end{array}\right\}*\prod_{\substack{p|n \\ 1 \mod 4}} \left( 1 + \frac{1}{p}\right)* \prod_{\substack{p|n \\ 3 \mod 4}} \left( 1 - \frac{1}{p}\right)$$

What are some proofs to this identity ?

Sequence A060968 is the number of points on the unit circle $x^2 + y^2 \equiv 1\; (\mod n)$

1, 2, 4, 8, 4, 8, 8, 16, 12, 8, 12,...

with a similar multiplicative formula: $$g(n) = n* \left\{\begin{array}{cl}2&\text{if}\quad\quad 4|n \\ 1 &\text{otherwise} \end{array}\right\}*\prod_{\substack{p|n \\ 1 \mod 4}} \left( 1 + \frac{1}{p}\right)* \prod_{\substack{p|n \\ 3 \mod 4}} \left( 1 - \frac{1}{p}\right)$$

Perhaps there is a tower of such identities.

The multiplicative structure of these formulas could have an algorithmic interpretation. The formula for the Euler phi function

\[ \phi(n) = n \prod_{p|n} \left( 1 - \frac{1}{p} \right) \]

This suggests a sieving algorithm to generate the list of numbers relatively prime to n

  • write down the numbers 1 thru n
  • for reach prime $p|n$ cross out multiples

I'd be especially interested if this type of algorithm existed for $f(n), g(n)$.

share|cite|improve this question
I wonder if these functions have appeared in the "serious" number theory literature and why. I had thought of this while trying to answer on this site. – john mangual Jul 10 '13 at 13:06
The formula must be a multiplicative function, by CRT (since you're counting number of solutions to some congruence). So you need to compute the number of solutions mod prime powers $p^k$. Do this for $k = 1$ and then use Hensel (if $p = 2$, you might have to start with $k = 3$). This sort of "mass" formula is common when you consider representation numbers of quadratic forms. For instance, see the book "Rational quadratic forms" by Cassels. – Abhinav Kumar Jul 10 '13 at 13:28
For the number of solutions mod $p$ to $\sum_{i=1}^n x_i^2 = 1$, see – Noam D. Elkies Jul 10 '13 at 13:40
Typo: the formula for a circle should be $x^2+y^2=1$ (or $\equiv 1$), not $x^2+y^2+z^2=1$. – Noam D. Elkies Jul 10 '13 at 13:41
Yet another MO source for counting solutions of $\sum_{i=1}^n x_i^2 \equiv 1 \bmod p$:… – Noam D. Elkies Jul 10 '13 at 14:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.