Conjectured primality test

This is a partial answer.

This answer proves that if $n$ is an odd prime and $b\ge 2$ is an integer, then $$\sum_{k=1}^{n-1}\left(b^k-1\right)^{n-1}\equiv n \pmod{\frac{b^n-1}{b-1}}$$ Proof :

Let $N:=\frac{b^n-1}{b-1}$.

By the binomial theorem, $$\begin{align}\sum_{k=1}^{n-1}\left(b^k-1\right)^{n-1}&=\sum_{k=1}^{n-1}\sum_{j=0}^{n-1}\binom{n-1}{j}(b^k)^{j}(-1)^{n-1-j}\\\\&=\sum_{j=0}^{n-1}\sum_{k=1}^{n-1}\binom{n-1}{j}(b^k)^{j}(-1)^{n-1-j}\\\\&=\sum_{k=1}^{n-1}\binom{n-1}{0}(b^k)^{0}(-1)^{n-1-0}+\sum_{j=1}^{n-1}\sum_{k=1}^{n-1}\binom{n-1}{j}(b^k)^{j}(-1)^{n-1-j}\\\\&=(n-1)\cdot (-1)^{n-1}+\sum_{j=1}^{n-1}\sum_{k=1}^{n-1}\binom{n-1}{j}(b^k)^{j}(-1)^{n-1-j}\tag1\end{align}$$

Since $n$ is an odd prime, we have $(-1)^{n-1}=1$, so

$$\begin{align}(1)&=n-1+\sum_{j=1}^{n-1}\sum_{k=1}^{n-1}\binom{n-1}{j}(b^k)^{j}(-1)^{n-1-j}\\\\&=n-1+\sum_{j=1}^{n-1}\binom{n-1}{j}(-1)^{n-1-j}\sum_{k=1}^{n-1}(b^j)^{k}\tag2\end{align}$$

By the way,

$$\sum_{k=1}^{n-1}(b^j)^{k}=\frac{(b^n)^{j}-b^j}{b^j-1}=\frac{((b-1)N+1)^j-b^j}{b^j-1}\tag3$$ By the binomial thorem, $$\begin{align}(3)&=\frac{\left(\displaystyle\sum_{m=0}^{j}\binom{j}{m}(b-1)^mN^m\right)-b^j}{b^j-1}\\\\&=\frac{\left(\displaystyle\sum_{m=1}^{j}\binom{j}{m}(b-1)^mN^m\right)+1-b^j}{b^j-1}\\\\&=\frac{1-b^j}{b^j-1}+\frac{\displaystyle\sum_{m=1}^{j}\binom{j}{m}(b-1)^mN^m}{b^j-1}\\\\&=-1+\frac{\displaystyle\sum_{m=1}^{j}\binom{j}{m}(b-1)^mN^m}{b^j-1}\\\\&=-1+\frac{N}{b^j-1}\sum_{m=1}^{j}\binom{j}{m}(b-1)^{m}N^{m-1}\tag4\end{align}$$

Now, we use that if $n$ is an odd prime, then either $\gcd(N,b^j-1)=n$ and $b\equiv 1\pmod n$ or $\gcd(N,b^j-1)=1$ holds for $1\le j\le n-1$. (The proof is written at the end of this answer.)

Case 1 : When $\gcd(N,b^j-1)=n$ with $b\equiv 1\pmod n$, $$\begin{align}(4)&=-1+\frac{N}{(b-1)(b^{j-1}+b^{j-2}+\cdots +b+1)}\sum_{m=1}^{j}\binom{j}{m}(b-1)^{m}N^{m-1}\\\\&=-1+\frac{N}{b^{j-1}+b^{j-2}+\cdots +b+1}\sum_{m=1}^{j}\binom{j}{m}(b-1)^{m-1}N^{m-1}\end{align}$$ Now, since $b^{j-1}+b^{j-2}+\cdots +b+1\equiv j\not\equiv 0\pmod n$, we have that $$\frac{1}{b^j-1}\sum_{m=1}^{j}\binom{j}{m}(b-1)^{m}N^{m-1}=\frac{1}{b^{j-1}+b^{j-2}+\cdots +b+1}\sum_{m=1}^{j}\binom{j}{m}(b-1)^{m-1}N^{m-1}$$ is an integer.

Case 2 : When $\gcd(N,b^j-1)=1$, we have that $$\frac{1}{b^j-1}\sum_{m=1}^{j}\binom{j}{m}(b-1)^{m}N^{m-1}$$ is an integer.

So, in either case, we have $$(4)\equiv -1\pmod N\tag5$$

Therefore, from $(1)(2)(3)(4)(5)$, we have $$\begin{align}(1)&\equiv n-1-\sum_{j=1}^{n-1}\binom{n-1}{j}(-1)^{n-1-j}\qquad\pmod{N}\\\\&\equiv n-\sum_{j=0}^{n-1}\binom{n-1}{j}(-1)^{n-1-j}\cdot 1^j\qquad\pmod{N}\\\\&\equiv n-(1-1)^{j}\qquad \pmod{N}\\\\&\equiv n\qquad\pmod{N}\qquad\blacksquare\end{align}$$

Finally, let us prove that if $n$ is an odd prime and $b\ge 2$ is an integer, then either $\gcd(N,b^j-1)=n$ and $b\equiv 1\pmod n$ or $\gcd(N,b^j-1)=1$ holds for $1\le j\le n-1$ where $N=\frac{b^n-1}{b-1}$.

Proof :

Let $D=\gcd(N,b^j-1)$. Then, we have $b^n\equiv 1\pmod D$ and $b^j\equiv 1\pmod D$. Let $s$ be the smallest $t$ such that $b^t\equiv 1\pmod D$. There exist non-negative integers $u,r$ such that $n=us+r$ with $0\le r\lt s$. Then, $$1\equiv b^n=b^{us}\cdot b^r=(b^s)^u\cdot b^r\equiv b^r\implies r=0$$ So, $n=us$. Similarly, there exists a non-negative integer $v$ such that $j=vs$. Since $\gcd(n,j)=1$, we have $s=1$ and $b\equiv 1\pmod D$.

Now, $$0\equiv N=\frac{b^n-1}{b-1}=b^{n-1}+b^{n-2}+\cdots +b+1\equiv n\pmod D$$ from which we have $D=1$ or $D=n$.$\qquad\blacksquare$

Just a remark which is a little long for a comment:

If we forget about the two and also about the generalization to other numbers for a second and look at polynomials instead, i.e. consider the polynomial $$p_n(x) := \sum_{k=1}^{n-1} (x^k-1)^{n-1}$$ and then reduce this modulo $x^n-1$, the reduced polynomials for $p_n$ when $n$ is prime have a very nice form, namely: $$p_n(x) \equiv n - \sum_{i=0}^{n-1} x^i \mod{x^n-1}.$$ Now it is clear that if we input $2$ (or $b$), the sum will exactly be $2^n-1$ resp $\frac{b^n-1}{b-1}$, so we get $n$ as claimed.

This is, unfortunately, not yet a proof for your claim, but it suggests that there is an even stronger structure behind it, that goes beyond natural numbers. Note that the polynomial $p_9$ does not have this nice structure, meaning that this strange case could be excluded when viewing it in the polynomial world.