Problem 2095

$858$

In this solution, $x \equiv y$ always means that $x-y$ is divisible by $9$. Furthermore, for any integer $x$, we denote by $[x]$ the unique element $x' \in S$ satisfying $x \equiv x'$. Note that for any integers $s$ and $t$, we have $[[s-t]+t] = [s]$ and $[s[t]] = [st]$.

Under this notation, the condition in the problem can be rewritten as
$$f(x)f(y) \equiv f(f([x+y]))$$
for any elements $x, y \in S$. We denote this equation by $P(x, y)$.

Define $T = \{f(x) \mid x \in S\}$. For any elements $s = f(x)$ and $t = f(y)$ in $T$, note that
$$[st] = [f(x)f(y)] = f(f([x+y])) \in T.$$

First, consider the case where $T$ contains a multiple of $3$. Let $a$ be such an element. Then, since $0 = [a^2] \in T$, there exists some $b \in S$ such that $f(b) = 0$. Therefore, we have $f(f(x)) = 0$ for any $x \in S$ since $P([x-b], b)$ gives
$$f(f(x)) \equiv f([x-b])f(b) = 0.$$
Furthermore, $f(x)$ is a multiple of $3$ since $P(x, x)$ gives
$$f(x)^2 \equiv f(f([2x])) = 0.$$
Conversely, suppose that for every $x \in S$, we have $f(f(x)) = 0$ and $f(x)$ is a multiple of $3$. Then such $f$ satisfies the condition because for any $x, y \in S$, both sides of $P(x, y)$ are divisible by $9$.

Since $T$ contains $0$, the condition that $f(x)$ is a multiple of $3$ for all $x \in S$ is equivalent to $T$ being one of $\{0\}$, $\{0, 3\}$, $\{0, 6\}$, or $\{0, 3, 6\}$. Furthermore, the condition that $f(f(x)) = 0$ for all $x \in S$ is equivalent to saying that $f(x) = 0$ for all $x \in T$. In the following, we consider each of the four possible cases for $T$ and count the number of possible functions $f$ in each case.

* When $T = \{0\}$, there is only one function $f$, namely $f(x) = 0$ for all $x$.
* When $T = \{0, 3\}$, the number of such functions $f$ is the number of ways to assign $f(x) = 0$ or $3$ for each $x \in S \setminus T = \{1, 2, 4, 5, 6, 7, 8\}$, such that there is at least one $x$ with $f(x) = 3$. There is exactly one way to assign all values to $0$, so the number of valid functions $f$ is $2^7 - 1 = 127$.
* When $T = \{0, 6\}$, by the same reason, the number of such functions $f$ is also $127$.
* When $T = \{0, 3, 6\}$, the number of such functions $f$ is the number of ways to assign $f(x) = 0, 3$, or $6$ for each $x \in S \setminus T = \{1, 2, 4, 5, 7, 8\}$ such that there is at least one $x$ with $f(x) = 3$ and at least one $y$ with $f(y) = 6$. There are $2^6$ ways where $f(x) \neq 3$ for all $x \in S \setminus T$, and $2^6$ ways where $f(y) \neq 6$ for all $y \in S \setminus T$, and one way where $f(x) \neq 3, 6$ for all $x \in S \setminus T$. So the number of valid functions $f$ in this case is $3^6 - 2^6 - 2^6 + 1 = 602$.

$$1 + 127 + 127 + 602 = 857.$$

Next, we consider the case where $T$ does not contain any multiples of $3$. Since $T$ is nonempty, we can take an element $a$ of $T$. Because $a$ is not divisible by $3$, Euler's theorem gives $a^6 \equiv 1$, so we have $1 = [a^6] \in T$. Thus, there exists some $b \in S$ such that $f(b) = 1$. Therefore, we have $f(0) = f(1)$ since $P(b, 0)$ gives
$$f(0) = f(b)f(0) \equiv f(f(b)) = f(1).$$
Furthermore, for any $x \in S$, from $P(x, [-x])$ and $P([x+1], [-x])$, we obtain
$$f(x)f([-x]) \equiv f(f(0)) = f(f(1)) \equiv f([x+1])f([-x]).$$
Thus, we have
$$f([-x]) (f([x+1]) - f(x)) \equiv 0.$$
Since $f([-x])$ is not divisible by $3$, we conclude that
$$f([x+1]) = f(x)$$
holds for every $x \in S$. Therefore, the set $T$ has exactly one element. Since $1 \in T$, we must have $T = \{1\}$, which does not contain a multiple of $3$. The constant function $f(x) = 1$ is the only function with this property. Conversely, this function satisfies the condition because both sides of $P(x, y)$ equal $1$ for any $x, y \in S$.

Hence, the total number of possible functions $f$ is $857 + 1 = 858$.