# Prove $n$ is prime. (Fermat's little theorem probably)

Let $x$ and $n$ be positive integers such that $1+x+x^2\dots x^{n-1}$ is prime. Prove $n$ is prime

My attempt:

Say the above summation equal to $p$ $$1+x+x^2\dots x^{n-1}\equiv 0\text{(mod p)}\\ {x^n-1\over x-1}\equiv0\\ \implies x^n\equiv1\text{ (as p can't divide x-1)}$$

How to proceed?

This does not involve any Fermat's little theorem type tricks. Indeed, it follows from a very simple factorization trick.

In some sense, if $n = pq$, then we arrange the $n$ powers $x^0,...,x^{pq-1}$ in a $p \times q$ box fashion, and then collect terms.

So, write $n = pq$ for some $1 < p,q < n$ if $n$ is not prime. Then: $$1 + ... + x^{pq-1} = (1 + ... + x^{p-1}) + (x^{p} + ... + x^{2p-1}) + ... + (x^{p(q-1)} + ... + x^{pq - 1}) \\ = (1 + ... + x^{p-1}) (1 + x^p + x^{2p} + ... + x^{p(q-1)})$$

for example, if $n = 6 = 2 \times 3$ then $$1 + ... + x^5 = (1+x)(1 + x^2 + x^4)$$, and if $n = 9 = 3 \times 3$ then $$1 + ... + x^8 = (1+x+x^2)(1+x^3+x^6)$$

Hint:

$$x^{ab}-1=(x^a-1)(x^{a(b-1)}+x^{a(b-2)}+\dots+x^a+1)$$

If $n$ is not prime, you can write it as $ab$; with $a,b\in\mathbb N\setminus\{1\}$. Then$$x^n-1=x^{ab}-1=(x^a)^b-1^b=(x^a-1)\left(x^{a(b-1)}+x^{a(b-2)}+\cdots+1\right)$$and therefore$$1+x+\cdots+x^{n-1}=\frac{x^n-1}{x-1}=(x^{a-1}+a^{a-2}+\cdots+1)\left(x^{a(b-1)}+x^{a(b-2)}+\cdots+1\right).$$

If $x = 1$, it's obvious.

For $x>1$, let $n$ be composite, say $n = pq$ with $p, q>1$. In that case, we have $$(1+x+\cdots+x^{n-1})(x-1) = x^n-1 = x^{pq}-1\\ = (x^p)^q-1\\ = (1+x+x^p+x^{2p}+\cdots + x^{(q-1)p})(x^p-1)$$ Thus $x^p-1$ divides $x^n-1$, but is not equal to it. In other words, $\frac{x^n-1}{x^p-1}$ is an integer greater than $1$. We get $$\frac{x^n-1}{x^p-1} =\frac{(1+x+\cdots+x^{n-1})(x-1)}{(1+x+\cdots +x^{p-1})(x-1)}\\ = \frac{1+x+\cdots+x^{n-1}}{1+x+\cdots +x^{p-1}}$$ That final fraction is an integer greater than $1$, and the denominator is an integer greater than $1$, which means that the numerator must be composite.