This problem was proposed independently (!) by Ashwin and Yang.

Now that some time has passed, here is the official solution draft, hidden for length. (Really, it's four solutions.)

Here is another way to do the computation. The cool part is that in the above post, we only need to take $k = p-1$. In particular, we can show that \[ \text{if } p|n \text{ then } 0^{p-1} + 1^{p-1} + 2^{p-1} + \cdots + {n-1}^{p-1} \not\equiv 0 \pmod{p}. \]To show this, write $x^{p-1}$ in its binomial/falling factorial basis. Specifically, it is know that $x^k = \sum_{t = 0}^k t! \binom{x}{t} S_{k, t}$ where $S_{k, t}$ are Stirling numbers of the second kind. We instead consider the sum $(p-1)! \sum_{x = 0}^{n-1} x^{p-1}.$ Now \[ (p-1)! \sum_{x = 0}^{n-1} x^{p-1} = (p-1)! \sum_{t = 0}^{p-1} t! S_{p-1, t} \sum_{x = 0}^{n-1} \binom{x}{t} = \sum_{t = 0}^{p-1} (p-1)! t! S_{p-1, t} \binom{n}{t+1} \]by the Hockey-stick identity. It is easy to check that for any $0 \le t < p-1$ we have that $n | (p-1)! t! \binom{n}{t+1}$ as $p | n.$ For $t = p-1$, we get the term $(p-1)!^2 \binom{n}{p}$. One can easily check that if $p | n$, then this is not a multiple of $n$, which completes the proof.

Here is an alternative solution which makes use of Lagrange's Theorem (NT).

Edit: 101st post

If $\boxed{\gcd(n,101!)=1}$, then $g(x)=x$ works. We claim that if $g(x),\ldots,g(x)+mx$ are all bijections over $\mathbb{Z}/n\mathbb{Z}$, then $\gcd(n,(m+1)!)=1$. We proceed by induction, with the case $m=0$ being obvious. The case $m=100$ implies the problem. Suppose the statement is true for all $m'<m$, and we're trying to show it for $m$. If $p=m+1$ isn't prime, then $\gcd(n,(m+1)!)=1$ if and only if $\gcd(n,m!)=1$, so we will assume WLOG that $p=m+1$ is prime. Again, we know that $\gcd(n,q)=1$ for all primes $q<p$. Since $g(x)$ and $g(x)+kx$ are both bijections for $1\le k\le m$, we have \[\sum_{x=0}^{n-1} g(x)^m\equiv\sum_{x=0}^{n-1}(g(x)+kx)^m\pmod{n}.\]Expanding, we get that \[\binom{m}{0}k^m\sum x^m +\binom{m}{1}k^{m-1}\sum g(x)x^{m-1} + \cdots+\binom{m}{m-1}k\sum g(x)^{m-1}x\equiv 0\pmod{n}\]for all $1\le k\le m$. Let $X_r=\binom{m}{r}\sum x^{m-r}g(x)^r$ for $0\le r\le m-1$. Thus, $M(X_0,\ldots,X_{m-1})^T\equiv 0\pmod{n}$ where $M$ is a matrix such that $M_{ij}=i^{m+1-j}$. Let $M^{-1}$ be it's inverse over $\mathbb{Q}$. It's well known that $(\det M)M^{-1}$ has entries in $\mathbb{Z}$. We see that \[D:=|\det M|=\prod_{1\le i<j\le m}(j-i),\]so over the rationals, \[(X_0,\ldots,X_{m-1})^T= (DM^{-1})(C_0 n/D,\ldots,C_{m-1} n/D)\]for some integers $C_0,\ldots,C_{m-1}$. We see that all the prime factors of $D$ are prime factors of $m!$, so $\gcd(n,D)=1$. Since $DM^{-1}$ is an integer matrix, we thus have \[X_r\equiv 0\pmod{n}\]for all $0\le r\le m-1$. The interesting case is $r=0$, which implies that \[\sum_{x=0}^{n-1} x^{p-1}\equiv 0\pmod{n}.\]If $p=2$, then $n\mid n(n-1)/2$, so $n$ odd, as desired. We may now assume $p\ge 3$. The key claim is that \[\nu_p\left(\sum_{x=1}^{p^e-1} x^{p-1}\right)<e.\]Let $S_\ell\subset[p^e-1]$ be the set of numbers $x$ with $\nu_p(x)=\ell$. Letting $g$ be a primitive root mod $p^{e-\ell}$, we see that \[\sum_{x\in S_\ell}x^{p-1}=p^{(p-1)\ell}\sum_{b=0}^{p^{e-\ell-1}(p-1)-1}g^{b(p-1)}=p^{(p-1)\ell}\frac{g^{p^{e-\ell-1}(p-1)^2}-1}{g^{p-1}-1}.\]We see that $p\mid g^{p-1}-1$, so the $\nu_p$ of this is \[\ell(p-1)+e-1-\ell\ge 2\ell+e-1-\ell=e+(\ell-1).\]For $\ell\ge 1$, this is at least $e$, and for $\ell=0$, it is $e-1$. Thus, the $\nu_p$ of the total sum is $e-1<e$, as desired. Say $\nu_p(n)=e$ with $e\ge 1$ and $n=p^ek$ where $\gcd(k,p)=1$. Then, \[\sum_{x=0}^{n-1} x^{p-1}\equiv 0\pmod{p^e},\]so \[k\sum_{x=1}^{p^e-1} x^{p-1}\equiv 0\pmod{p^e}.\]The $\nu_p$ of the left side is $e-1$, so we have the desired contradiction. Thus, $\gcd(n,p)=1$, and the induction is complete.

A version of this problem with $100$ replaced by $2$ was on Serbia National Olympiad 2012. (It is much easier than this problem, though.)

The answer is all $n$ with no prime factors less than or equal to $101$. To see that $g$ exists for such $n$, just take $g(x)=x$. Let $p$ be the smallest prime factor of $n$, and assume that $p\le101$. We will show \[g(x),\quad g(x)+x,\quad g(x)+2x,\quad\ldots,\quad g(x)+(p-1)x\]cannot all be bijections on $\mathbb Z/n\mathbb Z$. Claim: We can eliminate $n$ even; i.e.\ henceforth assume $n$ is odd and $p\ge3$. Proof. Assume for contradiction $g(x)$ and $g(x)+x$ are bijective. Note that \[\sum_{x=0}^{n-1}g(x)\equiv\sum_{x=0}^{n-1}\Big(g(x)+x\Big)\implies0\equiv\sum_{x=0}^{n-1}x\equiv\frac{n(n-1)}2\pmod n,\]thus $n$ is odd. $\blacksquare$ Lemma 1: If $e=\nu_p(n)$, then \[\nu_p\left(\sum_{x=0}^{n-1}x^{p-1}\right)=e-1.\] Proof. Note that \[\sum_{x=0}^{n-1}x^{p-1}\equiv\frac n{p^e}\sum_{x=0}^{p^e-1}x^{p-1}\pmod{p^e},\]so we prove $\nu_p\left(\sum_{x=0}^{p^e-1}x^{p-1}\right)=e-1$. Define \[T_k:=\sum_{\nu_p(x)=k}x^{p-1},\quad\text{so that}\quad\sum_{x=0}^{p^e-1}x^{p-1}\equiv\sum_{k=0}^eT_k\pmod{p^e}.\]If $g$ denotes a primitive root mod $p^{e-k}$, then \[T_k\equiv p^{k(p-1)}\sum_{i=0}^{\varphi(p^{e-k}-1)}g^{i(p-1)}\equiv\frac{g^{(p-1)\varphi(p^{e-k})}-1}{g^{p-1}-1}p^{k(p-1)}\pmod{p^e}.\]By Lifting the Exponent, \[\nu_p\left(g^{(p-1)\varphi(p^{e-k})}-1\right)=\nu_p\left(g^{p-1}-1\right)+e-k-1,\]so $\nu_p(T_k)=e-k-1+k(p-1)=e-1+k(p-2)$, which equals $e-1$ when $k=0$ and is at least $e$ otherwise. Thus \[\nu_p\left(\sum_{k=0}^eT_k\right)=\nu_p(T_0)=e-1,\]as desired. $\blacksquare$ Lemma 2: If such a function $g$ exists, then \[\sum_{x=0}^{n-1}x^{p-1}\equiv0\pmod{p^e}.\] Proof. Consider the polynomial in $k$ \[f(k):=\sum_{k=0}^{n-1}\Big(g(x)+kx\Big)^{p-1}-\sum_{x=0}^{n-1}x^{p-1}.\]Note that $f$ has degree $p-1$, but $p^e\mid f(x)$ for $x=0,\ldots,p-1$. I claim that if $f$ is a polynomial with degree at most $p-1$ and $p^e\mid f(x)$ for $x=0,\ldots,p-1$, then all coefficients of $f$ are divisible by $p^e$. This proves the lemma by looking at the leading coefficient. We proceed by induction on $e$. The base case $e=1$ is as follows: in $\mathbb F_p$, $f$ has $p$ roots but degree at most $p-1$, so it is the zero polynomial. For the inductive step, if $p^e\mid f(x)$ for all $x=0,\ldots,p-1$, by the inductive hypothesis, the coefficients of $f(x)$ are divisible by $p^{e-1}$. But $g(x):=f(x)/p$ is still always divisible by $p^{e-1}$, so by the inductive step, the coefficients of $g$ are all divisible by $p^{e-1}$. Thus the coefficients of $f$ are all divisible by $p^e$, as desired. $\blacksquare$ We conclude by combining Lemma 1 and Lemma 2.

The answer is all $n$ such that all prime factors of $n$ is greater than $101$. For such $n$, it suffices to take $g(x)=x$. Now we will show that if $p$ is a prime, and $n$ is an integer such that $n=p^{\alpha}k$, where all prime factors of $k$ is greater than $p+1$, then there exists no bijections $g:\mathbb Z/n\mathbb Z\to\mathbb Z/n\mathbb Z$ such that all the $p$ functions $$g(x), g(x)+x, g(x)+2x,..., g(x)+(p-1)x $$are all bijections. Suppose on the contrary that such bijections exists. The key idea is to consider the quantity $$S=\sum_{x=1}^nx^{p-1}=\sum_{x=1}^ng(x)^{p-1}=\sum_{x=1}^n(g(x)+x)^{p-1}=\sum_{x=1}^n(g(x)+2x)^{p-1}=...=\sum_{x=1}^n(g(x)+(p-1)x)^{p-1}\qquad (1)$$CLAIM. $v_p(S)=\alpha-1$, in particular this implies $S\not\equiv 0\pmod n$. Proof. Since $S\equiv k\sum_{x=1}^{p^{\alpha}}x^{p-1}\pmod{p^{\alpha}}$, it suffices to show $$v_p(\sum_{x=1}^{p^{\alpha}}x^{p-1})=\alpha-1$$This is very standard, let $g$ be a primitive root modulo $p^{\alpha}$, then the summand becomes $$\sum_{x=1}^{p^{\alpha-1}(p-1)}g^{p-1}x=(p-1)\frac{g^{p^\alpha(p-1)}-1}{g^{p-1}-1}$$By LTE, the p-valuation of the right hand side is precisely $$v_p(p^{\alpha-1})+v_p(g^{p-1}-1)-v_p(g^{p-1}-1)=\alpha-1$$as desired. $\blacksquare$ Now let $a_i=\sum_{x=1}^ng(x)^{p-1-i}x^{i}$ for each $1\leq i\leq p-2$. From $(1)$ and binomial theorem we have $$\left(\sum_{i=1}^{p-2}k^i\binom{p-1}{i}a_i\right)+k^{p-1}S\equiv 0 \pmod n \qquad (2)$$for every $1\leq k\leq p-1$. Let $b_{ki}=k^i\binom{p-1}{i}$ and $c_k=\left(\sum_{k=1}^{p-2}b_ka_k\right)+k^{p-1}S$ Now, we apply Cramer's rule to the system $(2)$, then $$S=\frac{\begin{vmatrix}b_{11}&b_{12}&...&b_{1(p-2)}&c_1\\ b_{21}&b_{22}&...&b_{2(p-2)}&c_2\\...&...&...&...&...\\b_{(p-1)1}&b_{(p-1)2}&...&b_{(p-1)(p-2)}&c_{p-1}\end{vmatrix}}{\begin{vmatrix}b_{11}&b_{12}&...&b_{1(p-2)}&1^{p-1}\\ b_{21}&b_{22}&...&b_{2(p-2)}&2^{p-1}\\...&...&...&...&...\\b_{(p-1)1}&b_{(p-1)2}&...&b_{(p-1)(p-2)}&(p-1)^{p-1}\end{vmatrix}}$$Now since $c_k\equiv 0\pmod n$, the nominator of $S$ is divisible by $n$. Meanwhile, the denominator of $S$ is equal to $$(p-1)!\prod_{i=1}^{p-1}\binom{p-1}{i}\begin{vmatrix}1^1&1^2&...&1^{p-1}\\2^1&2^2&...&2^{p-1}\\...&...&...&...\\(p-1)^1&(p-1)^2&...&(p-1)^{p-1}\end{vmatrix}=(p-1)!\sum_{i=1}^{p-1}\binom{p-1}{i}\prod_{1\leq i<\leq j\leq p-1}(i-j)$$since all prime factors of $n$ is greater than $p$, this number is coprime with $n$, therefore $S$ is divisble by $n$, contradiction. This completes the proof.

Remark: disgusting. I claim that our answer is all $n \geq 2$ without prime factors $\leq 101$. To see that these work, we can just take the function $g(x) = x$. Then, the $101$ functions are $x, 2x, \ldots 101x$ modulo $n$. Clearly each is injective since all numbers less than or equal to $101$ are relatively prime to such $n$, and each is surjective since $ax$ ranges through all nonzero residues mod $n$ as $x: 1 \to n-1$ if $(a, n)$ are relatively prime. We first prove even $n$ do not work. This is clear:\[\sum_{x = 1}^{n - 1} g(x) = \sum_{x = 1}^{n - 1} (g(x) + x) \implies 0 \equiv \frac12n(n + 1) \pmod n\]which would then imply that clearly, $n$ is odd, a contradiction to $n$ being even. Now we consider $n$ with some odd prime divisor $p \leq 101$. I claim that in fact, there do not even exist $p$ bijections of the form $g(x) + ix$ where $i : 0 \to p-1$. Suppose otherwise. Then it follows that\[Q = \sum_{x = 1}^{n-1} x^{p-1} \equiv \sum_{i = 1}^{n-1} g(x)^{p-1} \equiv \ldots \equiv \sum_{i = 1}^{n-1} (g(x) + (p-1)x)^{p-1} \pmod n.\] Claim: If $v_p[n] = e$, then $v_p[Q] = e - 1$. Proof: We reduce $Q$ modulo $p^e$. Note that\[Q \equiv \frac{n}{p^e} \sum_{x = 1}^{p^e - 1} x^{p - 1} \pmod {p^e} \implies v_p[Q] = v_p\left[\sum_{x = 1}^{p^e - 1} x^{p - 1}\right].\]Note that if we write\[a_i = \sum_{v_p[x] = i}^{p^e - 1} x^{p-1}\]for all $i$ from $0 \to e-1$ then we can write $Q = a_0 + a_{1} + \ldots + a_{e-1}$ which is slightly easier to evaluate. We may find the $v_p$ of each individual summand $a_{i}$ as follows:\[a_i = p^{i(p-1)}\left(\sum_{v_p[x] = 1}^{p^{e - i} - 1} x^{p - 1}\right) \implies v_p[a_i] = i(p - 1) + v_p\left[\sum_{v_p[x] = 1}^{p^{e - i} - 1} x^{p - 1}\right]\]and since primitive roots modulo $p^{e - i}$ generate all $\phi(p^{e - i})$ residues relatively prime to $p$, for some primitive root modulo $p^{e - i}$ say $g$, we may write\begin{align*} \sum_{v_p[x] = 1}^{p^{e - i} - 1} x^{p - 1} &\equiv g^{p - 1} + g^{2(p - 1)} + \ldots + g^{(p^{e - i} - p^{e - i - 1})(p - 1)}\\&\equiv \frac{g^{(p - 1)}(g^{p^{e - i} - p^{e - i - 1} - 1})}{g^{p - 1} - 1} \end{align*}modulo $p^e$ and upon lifting the exponent, we find that $v_p$ of this is $e - i - 1$ and hence\[v_p[a_i] = i(p - 1) + e - i - 1 = (e - 1) + i(p - 2) \geq e - 1\]where equality occurs at only $i = 0$. Hence, among the terms $a_0, a_1, \ldots , a_{e - 1}$, all of them have $v_p$ at least $e$ except for the first term, hence the $v_p$ of the sum must be $v_p[a_0] = e - 1$ and thus $v_p[Q] = e - 1$ as desired. $\square$ Next, we will prove a directly contradictory claim that will finish the problem. Claim: If $v_p[n] = e$, then $v_p[Q] = e$. Proof: Consider the polynomial\[P(k) = \sum_{x = 1}^{n - 1} ((g(x) + kx)^{p - 1} - x^{p - 1})\]in variable $k$. It has degree $p-1$ and becomes $0$ modulo $p^e$ for values $k: 0 \to p - 1$. I claim for any polynomial $T$ satisfying this property that $\deg(T) = p-1$ and $T(0) = T(1) = \ldots = T(p - 1) \equiv 0 \pmod{p^e}$, all coefficients of $T$ are divisible by $p^e$. This would finish as the coefficient of $k^{p - 1}$ term is our desired $Q$. We will prove this via induction on $e$. The base case of $e = 1$ is easy as this is just the well known fact that if $T$ with degree $p - 1$ has $p$ roots modulo $p$, then it is always $0$ modulo $p$. The inductive step is not much harder. Suppose the result is true for $e = t$. Then $T'(x) = \frac{1}{p}T(x)$ has coefficients divisible by $p^{t - 1}$ and hence $T$ has coefficients divisible by $p^t$, as desired, completing our induction. Hence $v_p[Q] = e$, as desired. $\square$ We cannot have $v_p[Q] = e = e - 1$ at the same time by the two claims, so we have our desired contradiction. Hence $n$ with odd prime divisors $p \leq 101$ do not work. $\blacksquare$

Does this work? Replace $101$ with any odd prime $p,$ and let $S_i=1^i+2^i+\dots+n^i$ for all positive integers $i.$ $\textbf{Claim: }$ $$\sum_{i=0}^{p-1}\left[(-1)^{i}\binom{p-1}{i}(g(x)+ix)^{p-1}\right]=x^{p-1}(p-1)!.$$$\emph{Proof: }$ Fix a positive integer $a\in[0,p-1].$ By the Binomial Theorem, the coefficient of $g(x)^{p-1-a}x^a$ in the sum is \begin{align*} \sum_{i=0}^{p-1}\left[ (-1)^{i}\binom{p-1}{i}\binom{p-1}{a}i^a\right] &= \binom{p-1}{a}\sum_{i=0}^{p-1}\left[(-1)^{i}\binom{p-1}{i}i^a\right] \end{align*}Note that the sum on the RHS is simply the PIE expression for the number of ways to distribute $a$ distinguishable objects to $p-1$ people such that every person gets at least one object. If $a<p-1,$ then this number is $0,$ and if $a=p-1,$ then this number is $(p-1)!.$ Therefore, the original sum evaluates to $x^{p-1}(p-1)!,$ as desired. $\blacksquare$ $\textbf{Claim: }$ If $p$ is the smallest prime divisor of $n,$ then $n\nmid S_{p-1}.$ $\emph{Proof: }$ The claim is obvious when $p=2,$ so assume $p>2.$ Write $n=p^{k}m,$ where $p\nmid m,$ and let $\omega$ be a primitive root modulo $p^k.$ It suffices to show that $\nu_p(S_{p-1}<k.$ We have \begin{align*} S_{p-1} &\equiv\sum_{i=0}^{p^{k}m-1}(i^{p-1})\\ &\equiv m\left[\sum_{i=0}^{p^k-1}(i^{p-1})\right]\\ &\equiv mp^{p-1}\left[\sum_{i=0}^{p^{k-1}-1}i^{p-1}\right]+m\left[\sum_{i=0}^{\varphi(p^k)-1}(\omega^i)^{p-1}\right]\pmod{p^k}. \end{align*}Let $A,B$ denote the first and second sums in the above expression. By LTE, $\nu_p(B)=k-1.$ Moreover, we can show that $\nu_p(A)=k-2$ by induction on $k.$ Hence, $\nu_p(S_{p-1})=\min(k+p-3,k-1)<k,$ as desired. $\blacksquare$ Now suppose $g(x)+ix$ is a bijection for all $i\in\{0,1,\dots,p-1\}.$ Then, we must have \begin{align*} \sum_{x=0}^{n-1}\sum_{i=0}^{p-1}\left[(-1)^{i}\binom{p-1}{i}(g(x)+ix)^{p-1}\right] &\equiv\sum_{i=0}^{p-1}\sum_{x=0}^{n-1}\left[(-1)^{i}\binom{p-1}{i}(g(x)+ix)^{p-1}\right]\\ &\equiv\sum_{i=0}^{p-1}\left[(-1)^{i}\binom{p-1}{i}S_{p-1}\right]\\ &\equiv 0\pmod{n} \end{align*}Therefore, by our first claim, $S_{p-1}(p-1)!\equiv 0\pmod{n}.$ Now it follows from our second claim that all prime factors of $n$ must be greater than $p.$ To show these work, just take the identity function.

Solved with nprime06 and HYP135peppers The answer is all odd n that are relatively prime to $\text{lcm}(1,2,\dots,101).$ Claim: All even $n$ fail Proof. \[\sum_{x} g(x) = \sum_{x} g(x)+x \pmod n \implies 0 = \sum_{x} x = {n+1 \choose 2}=\sum_x g(x) \pmod n \implies \text{n is odd}\] Claim: All odd $n$ that are relatively prime to $\text{lcm}(1,2,...,101)$ work. Proof. Take $g$ as the identity, and assume for contradiction there exists $i$ such that \[g(x)+ix = g(y)+iy \implies (i+1)x = (i+1)y \pmod n\]Since $n$ is relatively prime to $i+1,$ we can multiply both sides by the modular inverse of $i+1,$ to get $x = y$ a contradiction. Claim: All odd $n$ that share a common factor with $\text{lcm}(1,2,\dots, 101)$ fail. Proof. We have $\sum_x g(x) \equiv \sum_x g(x)+xi \equiv 0 \pmod n. $ Now, take some $p \mid n,$ with $p \le 101,$ to get $\sum_x x^k = 1^k+\cdots+(n-1)^k\equiv c(1^k+\cdots+(p-1)^k) \equiv \begin{cases} -c, \quad p-1 \mid k \\ 0, \qquad p-1 \cancel{\mid} k \end{cases}\pmod p$ for a constant $c.$ But $c = \frac{n}{p}$ so it must be that $\nu_p(n)>1,$ which gives $\nu_p\left[\sum_{x=1}^{n-1} x^{p-1}\right] =e-1$ when $\nu_p(n) = e.$ Lemma: $\nu_p\left(\sum_{x=1}^{n} (g(x)+ix)^{p-1}\right) > e-1$ when $\nu_p(n) = e$ and $i > 0,$ which gives an obvious contradiction. Proof. We will prove that the polynomial $\sum_{x=1}^{n} (g(x)+ix)^{p-1}-x^{p-1}$ has coefficients divisible by $p^e$ by induction on $e,$ which would prove the claim. For $e = 1,$ the polynomial has degree $p-1,$ but $p$ roots, hence it is the zero polynomial. For the inductive step, if $\sum_{x=1}^{n} (g(x)+ix)^{p-1}-x^{p-1}$ has coefficients divisible by $p^e,$ (since $n$ is scaled by $p$ when going from $p^e$ to $p^{e+1}$) then $p\left(\sum_{x=1}^{n} (g(x)+ix)^{p-1}-x^{p-1}\right)$ obviously has coefficients divisible by $p^{e+1}.$ Finally, we have achieved a contradiction due to our Lemma, so we are done.

Solved with rama1728. All $n$ where $\gcd(n, 101!)=1$ work. For a construction take $g(x) = x.$ Otherwise, take the minimal prime $p \mid n;$ suppose $p < 102.$ We get $$\sum_{x=0}^{n-1} (g(x) + ix)^{p-1} \equiv \sum_{x=0}^{n-1} x^{p-1} \pmod{n}.$$for all $0 \le i \le p-1.$ Claim: for any $0 \le x \le p-1,$ $$\sum_{i=0}^{p-1}\left((-1)^{i}\binom{p-1}{i}(g(x)+ix)^{p-1}\right) = x^{p-1} (p-1)!.$$Proof: Take any integer $0 \le j \le p-1.$ The coefficient of the $g(x)^{p-1-j}x^j$ term in the sum is $$\binom{p-1}{j}\sum_{i=0}^{p-1}(-1)^{i}\binom{p-1}{i}i^j.$$Note $(-1)^{i}\binom{p-1}{i}i^j$ is the number of ways to choose a subcommittee of size $i$ out of a total committee of size $p-1,$ then give each of $j$ things to a member of the subcommittee. So by PIE, $\sum_{i=0}^{p-1}(-1)^{i}\binom{p-1}{i}i^j$ is the number of ways to give each of $j$ things to the members of a committee of size $p-1$, so that each member gets at least one thing. This number is $0$ for all $j$ unless $j = p-1,$ where it equals $(p-1)!.$ $\square$ This means $$0 \equiv \sum_{x=0}^{n-1}\sum_{i=0}^{p-1}\left((-1)^{i}\binom{p-1}{i}(g(x)+ix)^{p-1}\right) \equiv \sum_{x=0}^{n-1}(p-1)!x^{p-1} \pmod{n}. $$Since $\gcd((p-1)!, n) = 1,$ we have $\sum_{x=0}^{n-1}x^{p-1} \equiv 0 \pmod{n}.$ Claim: If $v_{p}(n) = e$ where $e > 1,$ then $v_{p}\left(\sum_{x=0}^{n-1}x^{p-1}\right) = e-1.$ Proof: It suffices to show $v_{p}\left(\sum_{x=0}^{p^{e}-1}x^{p-1}\right) = e-1,$ which we prove with induction on $e$ with base case trivial. Now see \begin{align*} \sum_{x=0}^{p^{e}-1}x^{p-1} &\equiv \sum_{x=0}^{p^{e-1}-1}\left(x^{p-1}+(x+p^{e-1})^{p-1} + \dots + (x+(p-1)p^{e-1})^{p-1}\right) \\ &\equiv \sum_{x=0}^{p^{e-1}-1}\left(x^{p-1}+(x+p^{e-1})^{p-1} + \dots + (x+(p-1)p^{e-1})^{p-1}\right) \\ &\equiv \sum_{x=0}^{p^{e-1}-1}x^{p-1} \pmod{p^{e}}. \end{align*}as desired. $\square$ This contradicts $\sum_{x=0}^{n-1}x^{p-1} \equiv 0 \pmod{n},$ so we're done. $\blacksquare$

The answer is all $n$ such that $\gcd(n,101!)=1$.For a construction $g(x)=x$ works whenever $\gcd(n,101!)=1$.Let $p=q(n)$.AFTSOC,we can have $p<102$. Claim:-If all of the functions $f_0(x)=g(x),..........,f_{p-1}(x)=g(x)+(p-1)x$ are bijections modulo $p$ then $$k! \sum_{x \in {\mathbb Z}/n{\mathbb Z}} x^k \equiv 0 \pmod{n}$$Proof:- Note that $$\sum_{x \in {\mathbb Z}/n{\mathbb Z}} f_0(x)^k \equiv ..............\equiv \sum_{x \in {\mathbb Z}/n{\mathbb Z}} f_{p-1}(x)^k \equiv \sum_{i=1}^n i^k \pmod n - (1)$$for any $i<p$.Note that $\Delta_h^n=\sum_{i=1}^n \left(-1 \right)^{n-i} \binom{n}{i} f_k(x+in)$ by finite differences.So applying this to $(1)$ we must have $$k! \sum_{x \in {\mathbb Z}/n{\mathbb Z}} x^k \equiv 0 \pmod{n}$$Since $p=q(n)$,$\gcd(k!,n)=1$ for all $1 \le k \le p-1$ so $A(X):=\sum_{{\mathbb Z}/n{\mathbb Z}} x^k \equiv 0 \pmod n$ for all $k \in \{1,2,.......,p-1 \}$. Let $v_p(n)=e$. Claim:- $v_p(A(p^e-1)) \le e-1$. Proof:- Sum up using primitive roots. This finishes since $n \nmid A(p-1)$

The answer is all $n$ such that all prime factors are greater than $101$. Assume some $p \leq 101$ divides $n$. Notice that $\sum_x \left((kx+g(x))^{p-1} - g(x)^{p-1} \right) = 0$. Notice that the coefficients of this expression for each $1 \leq k \leq p - 1$ forms a $p - 1 \times p - 1$ matrix. By Laplace expansion, the determinant of this matrix is the same (up to sign) as $ \textrm{det} \left[(i-1)^{j-1} {p-1 \choose j - 1} \right]_{p \times p}$ in $GL(p, \mathbb{F}_p)$, which is just a bunch of binomial coefficients that are not multiples of $p$ times $\textrm{det} [(i-1)^{j-1}]_{p \times p}$, which is a Vandermonde matrix so it's determinant is $\pm \prod_{i \neq j} (i-j) \neq 0 \pmod p$, hence the original $p-1 \times p-1$ matrix is invertible. Thus $0 + (p-1) = \sum_x x^{p-1} = 0 \pmod p$ which is impossible so this is impossible by contradiction. For all other numbers, simply choose $g(x) = x$ to finish.

Solved with lrjr24. The answer is all $n$ with prime factors greater than $101$. Claim: If you replace $101$ with general $r \le 101$, $n$ must satisfy $r! \cdot \sum_{x \in \mathbb{Z}/n\mathbb{Z}} x^r \equiv 0 \pmod n$ Observe the sum \begin{align*} \sum_{x \in \mathbb{Z}/n\mathbb{Z}} \left[\sum_{k = 0}^{r} \left ( \left[g(x) + (r-k)x \right]^r \cdot (-1)^k \cdot {r \choose k} \right ) \right ] \\ = \sum_{k = 0}^{r} \left[ \sum_{x \in \mathbb{Z}/n\mathbb{Z}} \left( \left[g(x) + (r-k)x \right]^r \cdot (-1)^k \cdot {r \choose k} \right ) \right ] \\ = \sum_{k = 0}^{r} \left[ \sum_{x \in \mathbb{Z}/n\mathbb{Z}} \left( x^r \cdot (-1)^k \cdot {r \choose k} \right ) \right ] \\ = \sum_{x \in \mathbb{Z}/n\mathbb{Z}} \left[ \sum_{k = 0}^{r}\left( x^r \cdot (-1)^k \cdot {r \choose k} \right ) \right ] \\ = 0 \end{align*} Now we evaluate the double summation in a different way. Notice that the inner sum in \begin{align*} \sum_{x \in \mathbb{Z}/n\mathbb{Z}} \left[\sum_{k = 0}^{r} \left ( \left[g(x) + (r-k)x \right]^r \cdot (-1)^k \cdot {r \choose k} \right ) \right ] \end{align*}can be represented using finite differences. In advance, we define $P(x) = x^r$, and $\frac{g(x)}{x} = y$. Notice that \begin{align*} \sum_{x \in \mathbb{Z}/n\mathbb{Z}} \left[\sum_{k = 0}^{r} \left ( \left[g(x) + (r-k)x \right]^r \cdot (-1)^k \cdot {r \choose k} \right ) \right ] \\ = x^r \cdot \sum_{x \in \mathbb{Z}/n\mathbb{Z}} \left[\sum_{k = 0}^{r} \left ( \left[\frac{g(x)}{x} + (r-k) \right]^r \cdot (-1)^k \cdot {r \choose k} \right ) \right ] \\ = x^r \cdot \sum_{x \in \mathbb{Z}/n\mathbb{Z}} \left[\sum_{k = 0}^{r} \left (P(y+r-k) \cdot (-1)^k \cdot {r \choose k} \right ) \right ] \\ = x^r \cdot \sum_{x \in \mathbb{Z}/n\mathbb{Z}} \left[\sum_{k = 0}^{r} \Delta^r P(y) \right ] \\ = \sum_{x \in \mathbb{Z}/n\mathbb{Z}} x^r \cdot r! \end{align*} Therefore we have proved the claim. $\square$ Now, if the smallest prime divisor of $n$ is less than or equal to $101$, take the functions \[g(x), \quad g(x) + x, \quad g(x) + 2x, \quad \dots, \quad g(x) + (p-2)x\]and apply the above claim. We receive that $(p-1)! \cdot (p-1) \equiv 0 \pmod n$, which is absurd. Therefore all $n$ that have a prime divisor less than $101$ fail. For all $n$ that have all prime factors above $101$, simply take $g(x) = x$. $\blacksquare$

All equalities are assumed to be in $\mathbb{Z}/n\mathbb{Z}$. The answer is all $n$ with all prime factors greater than $101$. For such $n$, we can simply take $g(x) = x$. Now suppose $n$ has a prime factor $p \le 101$. Since $f(x)$, $f(x)+x$, $\dots$, $f(x)+(p-1)x$ are all bijections, we have $$0 = \sum_{x=0}^{n-1}\left(\sum_{i=0}^{p-1}\left((-1)^i\binom{p-1}{i}(f(x)+ix)^{p-1}\right)\right)$$ $$= \sum_{x=0}^{n-1}\left(\sum_{i=1}^{p-1}\left((-1)^i\binom{p-1}{i}\sum_{j=0}^{p-1}\left(\binom{p-1}{j}i^jx^jf(x)^{p-1-j}\right)\right)\right)$$ $$=\sum_{x=0}^{n-1}\left(\sum_{j=0}^{p-1}\left(\binom{p-1}{j}x^jf(x)^{p-1-j}\sum_{i=0}^{p-1}\left((-1)^i\binom{p-1}{i}i^j\right)\right)\right).$$ We claim that for $0\le j\le p-2$, the inner sum is $0$. Indeed, this just represents the $(p-1)^{\text{th}}$ finite difference at $0$ of the function $f(t) = t^j$, where the finite difference operation maps functions as $\Delta: f(t)\to f(t+1)-f(t)$. Since the degree decreases after each application of $\Delta$, the $(p-1)^{\text{th}}$ application of $\Delta$ should take $f(t) = t^j$ to the zero function when $j\le p-2$. Hence, these terms all disappear, and we are left with $$0 = \sum_{x=0}^{n-1}\left(\binom{p-1}{p-1}x^{p-1}f(x)^0\sum_{i=0}^{p-1}\left((-1)^i\binom{p-1}{i}i^{p-1}\right)\right) = \left(\sum_{i=0}^{p-1}\left((-1)^i\binom{p-1}{i}i^{p-1}\right)\right)\left(\sum_{x=0}^{n-1}x^{p-1}\right).$$. Write $n = p^k\cdot m$ with $k = v_p(n)$. Note that $$\sum_{i=0}^{p-1}\left((-1)^i\binom{p-1}{i}i^{p-1}\right)\equiv \sum_{i=1}^{p-1}\left((-1)^i\binom{p-1}{i}\right)\equiv -1\pmod{p}.$$ Moreover, one can show with induction on $k$ (see 2019 EGMO TST/3) that $$v_p\left(\sum_{i=0}^{p^k-1}i^{p-1}\right) = k-1$$ so we can write $$\sum_{x=0}^{n-1}\left(x^{p-1}\sum_{i=0}^{p-1}\left((-1)^i\binom{p-1}{i}i^{p-1}\right)\right)\equiv mc\sum_{x=0}^{p^k}x^{p-1}\pmod{p^k}$$ for some constant $c$ not divisible by $p$. But this sum should be divisible by $p^k$, so we have a contradiction, as desired.