*(This sounds like a fairly natural question, but I couldn't find it asked on this site before…)*

Fix an integer $n$ as the modulus, and consider polynomials (with integer coefficients) modulo $n$.

For any polynomial $f$ and any fixed $k$, we have $f(x) + nx^k \equiv f(x) \pmod n$ for all integers $x$; thus any two polynomials with some coefficient differing by a multiple of $n$ are equivalent in the sense that they give the same value mod $n$ for any integer $x$ as input. So we can assume that each coefficient of $f$ is one of $\{0, 1, 2, \dots, n-1\}$.

When $n$ is prime, we know (from Fermat's little theorem) that $x^n \equiv x \pmod n$ for all integers $x$, which means any polynomial of degree $n$ or greater is equivalent (in the same sense as above) to a polynomial of lower degree. Even when $n$ is not prime, some such relationship probably exists; for example when $n=4$, we can see that $x^4 \equiv x^2 \pmod 4$. (I guess, though this may be wrong and I haven't checked it, that if the prime factorization of $n$ is $n = p\_1^{e\_1}p\_2^{e\_2}\cdots p\_r^{e\_r}$, then $x^n \equiv x^{n/(p\_1p\_2\cdots p\_r)} \pmod n$.)

In any case, whenever $x \equiv y \pmod n$, we have $f(x) \equiv f(y) \pmod n$, so it is enough to consider the polynomial's values at $n$ consecutive integers say $\{0, 1, 2, \dots, n-1\}$. As there are at most $n$ distinct values it can have mod $n$ for each input $n$, there are at most $n^n$ distinct polynomials in this sense.

**The question**: How many distinct polynomials with integer coefficients are there mod $n$? Here, the meaning of "distinct" is that polynomials $f$ and $g$ are "distinct" if there exists at least one integer $x$ at which $f(x) \not\equiv g(x) \pmod n$. Or, using the terminology from what I found later (see below), we want the number of polynomial functions from $\mathbb{Z}$ to $\mathbb{Z}/n\mathbb{Z}$.

---

That is the question, but of course before asking it here I tried a few things to find the answer myself, including writing the following program.

Define the "signature" (just a name I made up for writing this program: is there already a standard term for this?) of a polynomial $f$ as the tuple $(f(0), f(1), f(2), …, f(n-1))$ of its values at all $n$ points. We can count the number of distinct polynomials mod $n$ by keeping track of all the encountered signatures, as we start with the zero polynomial and successively add $ax^k$ for each $a$ from $0$ to $n-1$, for increasing $k$ until $x^k$ has the same signature as some already seen polynomial.

```
#!/usr/bin/env python3

# Adding the signatures of two polynomials mod n
def add(t1, t2):
    n = len(t1)
    assert n == len(t2)
    return tuple((t1[i] + t2[i]) % n for i in range(n))

def count(n):
    szero = tuple([0]*n)  # The signature of the zero polynomial
    seen = {szero}  # Only the zero polynomial has been seen
    k = 0
    sxk = tuple([1]*n)  # The signature of x^k
    while True:
        news = set()  # New signatures, by adding ax^k for some a
        saxk = szero
        for a in range(1, n):
            saxk = add(saxk, sxk)  # The signature of a*(x^k)
            for s in seen:
                newp = add(saxk, s)  # a*(x^k) + (smaller polynomial)
                if newp not in seen: news.add(newp)
        seen.update(news)
        # Now done with all polynomials of degree k
        k += 1
        sxk = tuple((sxk[i]*i) % n for i in range(n))
        if sxk in seen: break
    return len(seen)

print('n', '\t', 'count(n)')
for n in range(1, 11):  # Gets very slow for n=11
    print(n, '\t', count(n))

```

This prints:

```
n    count(n)
1    1
2    4
3    27
4    64
5    3125
6    108
7    823543
8    1024
9    19683
10   12500

```

The good thing about computing these small values is that there is the [OEIS](http://oeis.org/), using which you can, to quote [Donald Knuth](https://youtu.be/BxQw4CdxLr8?t=1190), "compute your way into the literature". And accordingly, searching the OEIS for this sequence $1$, $4$, $27$, $64$, $3125$, $108$, $823543$, $1024$, $19683$ gives [A058067](http://oeis.org/A058067) described as "Number of polynomial functions from Z to Z/nZ" which is exactly our question. We also learn from that page that there's a formula

$$
\prod\_{k=0}^{n-1} \frac{n}{\gcd(n, k!)}
$$

that fits the numbers we computed and (per that page) was first proved by Aubrey J. Kempner in 1921 in a two-part paper called "Polynomials and their residue systems" ([1](https://www.ams.org/journals/tran/1921-022-02/S0002-9947-1921-1501173-4/home.html), [2](https://www.ams.org/journals/tran/1921-022-03/S0002-9947-1921-1501174-6/home.html)), and there's what appears to be a nice paper in 2000 by Manjul Bhargava called ["The Factorial Function and Generalizations"](https://www.maa.org/programs/maa-awards/writing-awards/the-factorial-function-and-generalizations) [PDF](https://www.maa.org/sites/default/files/pdf/upload_library/22/Hasse/00029890.di021346.02p0064l.pdf) that generalizes it (and maybe gives a shorter proof).

But I haven't read either of these papers as I ran out of my time budget for this (well, I exceeded it by writing up this question), and I hope someone can give a clear proof/derivation of the formula either using those papers or independently.

---

**Edit**: I read the latter paper and understood it enough to answer this question (left [an answer](https://math.stackexchange.com/a/4070413/205) below), but I have a follow-up question: [Smallest number of residue classes for a polynomial function mod $n$ that separates $0$](https://math.stackexchange.com/questions/4080417/smallest-number-of-residue-classes-for-a-polynomial-function-mod-n-that-separa).