3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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)$$

$\endgroup$
1
$\begingroup$

Hint:

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

$\endgroup$
1
$\begingroup$

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).$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.