Polynomial that indicates whether or not $x = 1 \pmod n$.

Question

For each $n$, is there a polynomial that takes representatives $x \in \Bbb{Z}$ for $\bar{x} \in \Bbb{Z}_n$, and returns whether or not $x = 1 \pmod n$?

For example, $n = 2$. Then $x \mapsto x \pmod{2}$ works. Is there a general formula for the $n$th modulus?

I'm stuck on case $n= 3$.

Let's loosen the criteria, we can use any of the classical elementary functions. So exponentiation will work:

$$ n = 3: \\ f(x) = 2^x - 1 \pmod 3\\ 0 \to 2^0 - 1 = 1 - 1 = 0 \pmod 3\\ 1 \to 2^1 - 1 = 1 \pmod 3\\ 2 \to 2^2 - 1 = 3 = 0 \pmod 3 $$

Answer 1

From what I understand, you are asking if for all $n\in\mathbb{N}$ there exists a polynomial $P_n(x)$ such that

$$x\equiv 1\ (\text{mod }n)\Rightarrow P_n(x)\equiv 1\ (\text{mod }n)$$

$$x\not\equiv 1\ (\text{mod }n)\Rightarrow P_n(x)\equiv 0\ (\text{mod }n)$$

This is only a partial answer, as I will prove it is possible if $n$ is a prime number. To begin, since you have already provided an answer for $n=2$, we may as well assume $n$ is an odd prime from here on out. Now, note that for any polynomial with integer coefficients $P(x)$, the sequence

$$\{\text{mod}(P(1),n),\text{mod}(P(2),n),\text{mod}(P(3),n),\cdots\}$$

is periodic with period $n$ (or some divisor of $n$). This is obvious as

$$(x+n)^k=\sum_{i=0}^k\binom{k}{i}x^in^{k-i}=x^k+n\left(\sum_{i=0}^{k-1}\binom{k}{i}x^in^{k-1-i}\right)\equiv x^k\ (\text{mod }n).$$

Thus, for any $n\in\mathbb{N}$, it suffices to find a polynomial with

$$\text{mod}(P_n(1),n)=1$$

$$\text{mod}(P_n(2),n)=0$$

$$\vdots$$

$$\text{mod}(P_n(n),n)=0$$

In fact, we may as well shift the indices by introducing $Q_n(x)=P_n(x+1)$. Then a sufficient condition is

$$\text{mod}(Q_n(0),n)=1$$

$$\text{mod}(Q_n(1),n)=0$$

$$\vdots$$

$$\text{mod}(Q_n(n-1),n)=0$$

However, we may even further simplify this problem and get rid of most of the the modular arithmetic in the above conditions. Then the sufficient conditions are

$$Q_n(0)\equiv 1\ (\text{mod }n)$$

$$Q_n(1)=0$$

$$\vdots$$

$$Q_n(n-1)=0$$

Now, consider the polynomial defined

$$Q_n(x)=-\prod_{i=1}^{n-1}(x-i)$$

We know that

$$Q_n(0)=-\prod_{i=1}^{n-1}(0-i)=(-1)^n (n-1)!=-(n-1)!$$

as $n$ is odd. However, by Wilson's Theorem, this is

$$-(n-1)!\equiv 1\ (\text{mod }n).$$

as $n$ is prime. For $1\leq x\leq n-1$, it is obvious that

$$Q_n(x)=-\prod_{i=1}^{n-1}(x-i)=0$$

as somewhere in the product $x-i$ is $0$. Shifting $x$ back to get $P_n(x)$, we find that

$$P_n(x)=-\prod_{i=1}^{n-1}(x-i-1)$$

satisfies the conditions above for all prime $x$ (we can manually check that $P_2(x)=2-x$ works). The first few of these are

$$P_2(x)=-x+2$$

$$P_3(x)=-x^2+5 x-6$$

$$P_5(x)=-x^4+14 x^3-71 x^2+154 x-120$$

$$P_7(x)=-x^6+27 x^5-295 x^4+1665 x^3-5104 x^2+8028 x-5040$$

$$\vdots$$

Answer 2

One definition of indicate is $P(x) \equiv 0 \bmod n$ iff $x \not\equiv 1 \bmod n$.

With this definition, $x^3+x^2$ works for $n=4$.

$x(x-2)(x-3)$ from @QC_QAOA's answer also works for $n=4$.

However, @QC_QAOA's construction fails for $n=6$. In fact, it fails for every composite number $n>4$.

In fact, no polynomial works for $n=6$ because $x^3-x$ induces the zero function and no polynomial of degree at most $2$ works. (I've tried all of them.)