This is an interesting question which can be solved by applying Burnside's lemma (as suggested by Qiaochu Yuan in a comment) and some knowledge of the group of units modulo $n$. The relevant facts about the groups of units mostly derive from the Chinese remainder theorem, quadratic reciprocity, and the knowledge that the group of units modulo a power of an odd prime is cyclic. This is all rather elementary group theory and number theory, but I found it to be a very instructional exercise. I have written the details below, partly for my own benefit.$\newcommand{\totient}{\varphi}$$\newcommand{\congruent}{\equiv}$$\newcommand{\To}{\longrightarrow}$$\newcommand{\ZZ}{\mathbb{Z}}$$\newcommand{\ZZmod}[1]{\ZZ/ #1 \ZZ}$$\newcommand{\set}[1]{\lbrace #1 \rbrace}$$\newcommand{\units}[1]{U(#1)}$$\newcommand{\size}[1]{\mathopen{}\mathclose{\left\lvert #1 \right\rvert}}$
I will first describe the final answer. Let $n > 2$ be an integer. The number $\psi(n)$ of distinct homeomorphism classes of $3$-dimensional lens spaces whose fundamental group has order $n$ is
$$ \psi(n) = \frac14 \bigl( \totient(n) + 2^{l(n) + \epsilon(n)} \bigr) $$
where $\totient$ is Euler's totient function. Moreover, $\epsilon(n)$ is $1$ if $-1$ is a quadratic residue modulo $n$, and zero otherwise. As will be shown below, $\epsilon(n) = 1$ if and only if $4$ does not divide $n$ and each of the odd prime divisors of $n$ is congruent to $1$ modulo $4$. Finally, describing $l$ requires the prime factorization of $n$:
$$ n = {p_1}^{\alpha_1} \cdots {p_k}^{\alpha_k} $$
where the numbers $p_i$ are distinct primes, and the $\alpha_i$ are positive integers. Assume further that $p_1$ is the smallest prime divisor of $n$. Then $l(n)$ is given by
$$ l(n) = \begin{cases}
k & \text{if }\ p_1 \neq 2 \\
k + \min\set{\alpha_1 - 2 , 1} & \text{if }\ p_1 = 2
\end{cases} $$
Notation.
To maintain a clear distinction between rings and groups, $\ZZmod{n}$ will denote the ring of integers modulo $n$, where $n$ is a positive integer. On the other hand, $C_n$ will denote a cyclic group with $n$ elements. The group of units in the ring $\ZZmod{n}$ is denoted by $\units{\ZZmod{n}}$. I will generally use multiplicative notation for the groups appearing in this answer.
Applying Burnside's lemma.
We follow here the suggestion of Qiaochu Yuan in a comment below the question. Fix an integer $n > 2$. Consider the group $G = C_2 \times C_2$, where $C_2 = \set{-1,1}$ with generator $-1$. Make $G$ act on $\units{\ZZmod{n}}$ in the following way: the generator $(-1,1)$ of the first copy of $C_2$ acts by taking a number to its negative (the additive inverse in $\ZZmod{n}$), and the generator $(1,-1)$ of the second copy of $C_2$ takes a number to its multiplicative inverse. From Brody's classification mentioned in the question, the set of homeomorphism classes of lens spaces with fundamental group of order $n$ is in bijection with the set of orbits for the action of $G$ on $\units{\ZZmod{n}}$. Let $\psi(n)$ denote the size of the quotient set $\units{\ZZmod{n}}/G$.
The so-called Burnside's lemma implies that
$$ 4\, \psi(n) = \size{G} \cdot \psi(n) = \sum_{g\in G} \size{\units{\ZZmod{n}}^g} \tag{1a} $$
where $\units{\ZZmod{n}}^g$ denotes the set of fixed points of the action of $g$ on $\units{\ZZmod{n}}$, and $\size{\bullet}$ returns the size of a set. The fixed point sets corresponding to the first copy of $C_2$ are quickly determined. The unit $(1,1)\in G$ fixes everything in $\units{\ZZmod{n}}$ and thus contributes
$$ \size{\units{\ZZmod{n}}^{(1,1)}} = \size{\units{\ZZmod{n}}} = \totient(n) $$
The fixed points for the generator $(-1,1)\in G$ of the first copy of $C_2$ are the units $x \in \units{\ZZmod{n}}$ such that $2x = 0$ in $\ZZmod{n}$. The existence of such an invertible $x$ entails that $2 \congruent 0 \mod n$. Since $n>2$,
$$ \size{\units{\ZZmod{n}}^{(-1,1)}} = 0 $$
Square roots modulo $n$.
The fixed points for the remaining elements of $G$ are related to the number of square roots modulo $n$. For each $a\in\units{\ZZmod{n}}$, define the set of square roots of $a$:
$$ R(n,a) = \set{ x\in\units{\ZZmod{n}} \mid x^2 = a } $$
In particular, the set $R(n,a)$ is non-empty if and only if $a$ is a quadratic residue modulo $n$. Now, the fixed point set for the elements $(1,-1)$ and $(-1,-1)$ in $G$ consist precisely of the units which square to $1$ and $-1$, respectively:
$$ \begin{align*}
\units{\ZZmod{n}}^{(1,-1)} &= R(n,1) \\
\units{\ZZmod{n}}^{(-1,-1)} &= R(n,-1)
\end{align*} $$
Replacing everything back into (1a):
$$ 4\, \psi(n) = \totient(n) + \size{R(n,1)} + \size{R(n,-1)} \tag{1b} $$
More generally, for any abelian group $A$ and an element $a\in A$, define the set:
$$ R(A,a) = \set{ x \in A \mid x^2 = a } $$
Then the sets of square roots modulo $n$ are an instance of this general definition: $R(n,a) = R\bigl(\units{\ZZmod{n}},a\bigr)$. Consider the squaring homomorphism $\sigma : A\to A$ on an abelian group $A$ which sends an element $x \in A$ to its square $x^2$ — we are using multiplicative terminology here. Then $R(A,a)$ is the fibre of $\sigma$ over $a \in A$: $R(A,a) = \sigma^{-1}(a)$. In particular, if $1 \in A$ denotes the identity element of $A$, $R(A,1)$ is the kernel of the squaring homomorphism, and is therefore an abelian group. The fibres of a group homomorphism are always torsors over the kernel, so $R(A,a)$ is a torsor over the group $R(A,1)$ for any $a\in A$. Hence, $\size{R(A,a)} = \size{R(A,1)}$ whenever $R(A,a)$ is non-empty. We conclude from equation (1b):
$$ 4\, \psi(n) = \totient(n) + \size{R(n,1)}(1 + \epsilon(n)) \tag{1c} $$
where $\epsilon(n) = 1$ if $R(n,-1)\neq\emptyset$ and $\epsilon(n) = 0$ if $R(n,-1)=\emptyset$. In other words, $\epsilon(n) = 1$ if and only if $-1$ is a quadratic residue modulo $n$.
Square roots and the Chinese remainder theorem.
As before, set the prime factorization of $n$ to $n = {p_1}^{\alpha_1} \cdots {p_k}^{\alpha_k}$, where the numbers $p_i$ are distinct primes, and the $\alpha_i$ are positive integers. According to the Chinese remainder theorem, there is an isomorphism of rings
$$ \ZZmod{n} = (\ZZmod{{p_1}^{\alpha_1}}) \times \cdots \times (\ZZmod{{p_k}^{\alpha_k}}) $$
determined by the canonical projections from $\ZZmod{n}$ onto each of the factors in the target. Consequently, we deduce an isomorphism between the groups of units:
$$ \units{\ZZmod{n}} = \units{\ZZmod{{p_1}^{\alpha_1}}} \times \cdots \times \units{\ZZmod{{p_k}^{\alpha_k}}} $$
Since $R\bigl(A\times B,(a,b)\bigr) = R(A,a) \times R(B,b)$, taking the set of square roots of $a\in\units{\ZZmod{n}}$ on each side of the previous expression produces:
$$ R(n,a) = R({p_1}^{\alpha_1},a) \times \cdots \times R({p_k}^{\alpha_k},a) \tag{2} $$
In each term above, $a$ really stands for the projection of $a$ in the corresponding group.
Determining when $-1$ is a quadratic residue.
Recall that $a$ is a quadratic residue modulo $m$ if and only if $R(m,a) \neq \emptyset$. As a consequence of the isomorphism (2), $a \in \units{\ZZmod{n}}$ is a quadratic residue modulo $n$ if and only if $a$ is a quadratic residue modulo ${p_i}^{\alpha_i}$ for every $i\in\set{1,\ldots,k}$. The following claim reduces the case of a prime power modulus to the case of a prime modulus.
Proposition: Let $p$ be an odd prime, and $\alpha$ a positive integer. A unit $a \in \units{\ZZmod{p^\alpha}}$ is a quadratic residue modulo $p^\alpha$ if and only $a$ is a quadratic residue modulo $p$.
Proof:
Consider the projection map $\pi : \ZZmod{p^\alpha} \to \ZZmod{p}$, which is a ring map. Then $\pi^{-1}\bigl(\units{\ZZmod{p}}\bigr) = \units{\ZZmod{p^\alpha}}$: an integer $m$ becomes invertible in $\ZZmod{p^\alpha}$ if and only if it is coprime to $p^\alpha$, which happens precisely when $m$ is not divisible by $p$ and thus invertible in $\ZZmod{p}$. Hence, we obtain a short exact sequence of groups:
$$ 1 \To \pi^{-1}(1) \To \units{\ZZmod{p^\alpha}} \To \units{\ZZmod{p}} \To 1 \tag{ES} $$
The group $\pi^{-1}(1) = 1 + p(\ZZmod{p^\alpha})$ has order $p^{\alpha-1}$, which is odd. Therefore, the squaring homomorphism on $\pi^{-1}(1)$ is necessarily a self-bijection, and so every element in $\pi^{-1}(1)$ is a square. Chasing around the preceding short exact sequence, it follows that when $a \in \units{\ZZmod{p^\alpha}}$ is a quadratic residue modulo $p$, it is also a quadratic residue modulo $p^\alpha$. ■
The first supplement to the law of quadratic reciprocity now implies the following result.
Corollary: If $p$ is an odd prime, and $\alpha$ is a positive integer, then $-1$ is a quadratic residue modulo $p^\alpha$ if and only $p \congruent 1 \mod 4$.
It remains to deal with the case of powers of the prime two. Observe that $-1$ is a quadratic residue modulo $2$. However, $-1$ is not a quadratic residue modulo $4$, and thus cannot be a quadratic residue modulo $2^\alpha$, for any $\alpha > 1$. The following proposition collects what we have learned in this section.
Proposition: Given an integer $n > 1$, $-1$ is a quadratic residue modulo $n$ — i.e. $\epsilon(n) = 1$ — if and only if:
- each odd prime divisor of $n$ is congruent with $1$ modulo $4$,
- and $4$ does not divide $n$.
Counting square roots of unity.
To finish the proof, we need to find the number of square roots of the unit in the ring $\ZZmod{n}$, that is, the size of $R(n,1)$. By (2), this is reduced to calculating the size of $R({p_i}^{\alpha_i},1)$ for each $i$. We will use the fact that $R(C_m,1) \cong C_1$ (where $1 \in C_m$ is the identity element) is trivial if $m$ is odd, and $R(C_m,1) \cong C_2$ if $m$ is even.
Claim: For $p$ an odd prime, and $\alpha$ a positive integer, $R(p^\alpha,1) \cong C_2$.
Proof: This follows from the fact that $\units{\ZZmod{p^\alpha}}$ is a cyclic group of even order equal to $p^{\alpha-1}(p-1)$ (stated on the relevant wikipedia page). Alternatively, it may be deduced from two results stated in the proof of the first proposition from the previous section: the short exact sequence (ES), and the observation that the squaring homomorphism is a bijection on the kernel of that exact sequence. ■
Claim: For $\alpha > 2$, $R(2^\alpha,1) \cong C_2 \times C_2$. Moreover, $R(4,1) \cong C_2$ and $R(2,1) \cong C_1$. In particular, $\size{R(2^\alpha,1)} = 2^{\min\set{\alpha-1,2}}$ for each positive integer $\alpha$.
Proof: This is a consequence of the following facts (see the wikipedia page):
- $\units{\ZZmod{2}} \cong C_1$, so that $R(2,1) \cong C_1$;
- $\units{\ZZmod{4}} \cong C_2$, so that $R(4,1) \cong C_2$
- for $\alpha > 2$, $\units{\ZZmod{2^\alpha}} \cong C_2 \times C_{2^{\alpha-2}}$, so that $R(2^\alpha,1) \cong C_2 \times C_2$.
For reference, section 4.5 of Helmut Hasse's book Number theory proves the results, identifying the groups $\units{\ZZmod{p^\alpha}}$, which were used in this proof and in the previous one. ■
Using the isomorphism (2), these two claims prove that $R(n,1)$ is the product of a certain number of cyclic groups of order $2$. We calculate:
$$ \size{R(n,1)} = \prod_{i=1}^k \size{R({p_i}^{\alpha_i},a)} = 2^{l(n)} $$
Here, $l(n) = l({p_1}^{\alpha_1} \cdots {p_k}^{\alpha_k})$ is as defined at the beginning:
$$ l(n) = \begin{cases}
k & \text{if }\ p_1 \neq 2 \\
k + \min\set{\alpha_1 - 2 , 1} & \text{if }\ p_1 = 2
\end{cases} $$
where we assume that $p_1$ is the smallest prime number which divides $n$.
Finally, equation (1c) implies
$$ 4\, \psi(n) = \totient(n) + 2^{l(n)}(1+\epsilon(n)) = \totient(n) + 2^{l(n) + \epsilon(n)} $$
since $\epsilon(n)$ only takes the values $0$ and $1$.
