, 2013

Solution:

For a positive integer $n$, let $\mathbb{Z} / n \mathbb{Z}$ denote the set of residues modulo $n$ and $(\mathbb{Z} / n \mathbb{Z})^{*}$ denote the set of residues modulo $n$ that are relatively prime to $n$. Then, rephrased, $S_{m}$ is the set of residues modulo $m$ of the form $x+x^{-1}$, where $x \in (\mathbb{Z} / m \mathbb{Z})^{*}$.

For part (a), suppose $a = x + x^{-1} \in S_{m}$ and $b = y + y^{-1} \in S_{n}$. By the Chinese Remainder Theorem, there exists a residue $z \in (\mathbb{Z} / m n \mathbb{Z})^{*}$ such that $m \mid (x-z)$ and $n \mid (y-z)$, and thus $z + z^{-1} \equiv x + x^{-1} \pmod{m}$ and $z + z^{-1} \equiv y + y^{-1} \pmod{n}$. Therefore, all $f(m) f(n)$ residues modulo $m n$ which result from applying the Chinese Remainder Theorem to an element each of $S_{m}$ and $S_{n}$ are in $S_{m n}$. Conversely, given $z + z^{-1} \in (\mathbb{Z} / m n \mathbb{Z})^{*}$, taking $z + z^{-1}$ modulo $m$ and $n$ gives elements of $S_{m}$ and $S_{n}$, so indeed $f(m n) = f(m) f(n)$.

We now proceed to part (b). For each $x \in (\mathbb{Z} / p^{k} \mathbb{Z})^{*}$, denote $q(x)$ to be the largest non-negative integer $i \leq k$ such that $p^{i}$ divides $x^{2}-1$ (this is clearly well-defined). For a given $x$, let $g(x)$ be the number of $y \in (\mathbb{Z} / p^{k} \mathbb{Z})^{*}$ such that $x + x^{-1} \equiv y + y^{-1} \pmod{p^{k}}$. Note that this condition is equivalent to $(x-y)(x y-1) \equiv 0 \pmod{p^{k}}$.

First, consider the case in which $q(x) \geq k / 2$, in which case we have $p^{\lceil k / 2 \rceil} \mid (x-1)(x+1)$, and because $p$ is odd, $x \equiv \pm 1 \pmod{p^{\lceil k / 2 \rceil}}$. Thus, either $(x-1)^{2} \equiv 0 \pmod{p^{k}}$ or $(x+1)^{2} \equiv 0 \pmod{p^{k}}$, and it follows that $x + x^{-1} \equiv \pm 2 \pmod{p^{k}}$ (clearly $2$ and $-2$ are distinct). Conversely, $x + x^{-1} \equiv \pm 2$ implies $(x \pm 1) \equiv 0 \pmod{p^{\lceil k / 2 \rceil}}$, which in turn implies $q(x) \geq k / 2$. It is now clear that there are exactly two elements of $S_{m}$ corresponding to residues of the form $x + x^{-1}$ with $q(x) \geq k / 2$, and all other elements of $S_{m}$ come from $x$ with $q(x) < k / 2$.

Fix $x$ with $q(x) < k / 2$; we will compute $g(x)$. Suppose $(x-y)(x y-1) \equiv 0 \pmod{p^{k}}$, and say $x-y, x y-1$ have $j, j'$ factors of $p$, respectively. If $j \leq j'$, note that $x^{2}-1 \equiv x y-1 \equiv 0 \pmod{p^{j}}$, so $j \leq q(x)$. Similarly, if $j' \leq j$, $x \equiv y \pmod{p^{j'}}$, so $x^{2}-1 \equiv x y-1 \equiv 0 \pmod{p^{j'}}$, and so $j' \leq q(x)$. It follows that $\min(j, j') \leq q(x)$, and thus $\max(j, j') \geq k - q(x)$.

Suppose $p^{k-q(x)} \mid (x-y)$. Then, $x y-1 \equiv x^{2}-1 \equiv 0 \pmod{p^{q(x)}}$ because $q(x) < k / 2$, so any $y$ with $p^{k-q(x)} \mid (x-y)$ satisfies $(x-y)(x y-1) \equiv 0 \pmod{p^{k}}$. Now, suppose $p^{k-q(x)} \mid (x y-1)$, that is, $y \equiv x^{-1} \pmod{p^{k-q(x)}}$. Then, $x y \equiv 1 \pmod{p^{q(x)}}$, and since $x^{2} \equiv 1 \pmod{p^{q(x)}}$, we have $x \equiv y \pmod{p^{q(x)}}$, so again we have $(x-y)(x y-1) \equiv 0 \pmod{p^{k}}$. It follows that the set of $y$ satisfying $(x-y)(x y-1) \equiv 0 \pmod{p^{k}}$ is exactly the set of $y$ with $y \equiv x \pmod{p^{k-q(x)}}$ or $y \equiv x^{-1} \pmod{p^{k-q(x)}}$. $x, x^{-1}$ are distinct residues modulo $p^{k-q(x)}$, because $x^{2}-1$ has fewer than $k / 2$ factors of $p$, so it follows that $g(x) = 2 p^{q(x)}$. In particular, note that these values are distinct for different values of $q(x) < k / 2$, so $x + x^{-1} \equiv y + y^{-1}$ implies $q(x) = q(y)$ or $q(x), q(y) \geq k / 2$.

For each integer $i$ with $0 \leq i < k / 2$, we need to compute the number of $x \in (\mathbb{Z} / p^{k} \mathbb{Z})$ with $q(x) = i$. Clearly, this is the number of $x$ with $p^{i} \mid x^{2}-1$ minus the number of $x$ with $p^{i+1} \mid x^{2}-1$. When $i = 0$, the number of $x$ with $p^{i} \mid x^{2}-1$ is clearly $p^{k-1}(p-1)$, and when $i > 0$, this number is $2 p^{k-i}$, as we have $x \equiv \pm 1 \pmod{p^{i}}$.

We can now count the number of elements of $S_{p^{k}}$ using casework on the value of $q(x)$ where we take $x$ to be such that $x + x^{-1}$ is a particular element of $S_{m}$. Applying the results from the previous two paragraphs, our answer is
$$2 + \frac{p^{k-1}(p-3)}{2} + \sum_{i=1}^{\lceil k / 2 \rceil - 1} \frac{2 p^{k-i} - 2 p^{k-i-1}}{2 p^{i}}$$
where the summand $2$ comes from $\pm 2 \in S_{p^{k}}$, corresponding to all $x$ with $q(x) > k / 2$, the next summand comes from those $x$ with $q(x) = 0$, and each additional summand comes from those $x$ with $q(x) = i$ in the relevant range. We may evaluate the last sum as a geometric series, to obtain the final closed form answer of
$$2 + \frac{p^{k-1}(p-3)}{2} + \frac{p^{k-1} - p^{\frac{1+(-1)^{k}}{2}}}{p+1}$$