## Powers of ten

How many positive integers n are there such that $$10^{10^{10^{n}}} + 10^{10^{n}} + 10^{n} - 1$$ is prime?

[SOLVED]

#### quasi solved this puzzle:

None.

Let $$x = 10^{10^{10^n}} + 10^{10^n} + 10^n - 1$$. Let $$k$$ be such that $$2^k \Vert n$$ and let $$d = 10^{2^k} + 1$$. Then $$1 \lt 10^{2^k} + 1 \le 10^n + 1 \lt x$$, hence $$1 \lt d \lt x$$.

By definition of $$d$$, $$10^{2^k} \equiv -1 \pmod{d}$$. By choice of $$k$$,

$10^{2^k} \equiv -1 \pmod{d} \implies 10^n \equiv -1 \pmod{d}.$

On the other hand

\begin{align*} 10^{2^k} \equiv -1 \pmod{d} & \implies 10^{2^{k+1}} \equiv 1 \pmod{d} \\ & \implies 10^m \equiv 1 \pmod{d}. \end{align*}

if $$m$$ is a positive integer such that $$2^{k + 1} \mid m$$.

Now $$k + 1 \le 2^k$$, hence $$k + 1 \le n$$. Then

\begin{align*} k + 1 \le n & \implies 2^{k + 1} \mid 2^n \\ & \implies 2^{k + 1} \mid 10^n \\ & \implies 10^{10^n} \equiv 1 \pmod{d}. \end{align*}

Similarly,

\begin{align*} k + 1 \le n & \implies k+1 \lt 10^n \\ & \implies 2^{k + 1} \mid 2^{10^n} \\ & \implies 2^{k + 1} \mid 10^{10^n} \\ & \implies 10^{10^{10^n}} \equiv 1 \pmod{d}. \end{align*}

Thus,

\begin{align*} & 10^{10^{10^n}} + 10^{10^n} + 10^n - 1 \\ & \equiv 1 + 1 + (-1) - 1 \pmod{d} \\ & \equiv 0 \pmod{d}. \end{align*}

Therefore, $$d \mid x$$, hence $$x$$ is composite.

#### Gabriel Elpers solved this puzzle:

None. Every such number is composite for any positive integer $$n$$.

Let $$n = 2^k m$$, where $$k \geq 0$$ and $$m \gt 0$$ is odd (any positive integer can be written like this due to prime factorization), and let

$f(n) = 10^{10^{10^n}} + 10^{10^n} + 10^n - 1.$

I will show that $$10^{2^k} + 1 \mid f(n)$$.

First, note that $$10^{2^k} \equiv -1 \pmod{10^{2^k} + 1}$$. Squaring this result further yields $$10^{2^{k+1}} \equiv 1 \pmod{10^{2^k} + 1}$$.

Thus,

\begin{align*} 10^n & = 10^{2^k m} \\ & = (10^{2^k})^m \\ & \equiv (-1)^m \pmod{10^{2^k} + 1} \\ & \equiv -1 \pmod{10^{2^k} + 1}, \end{align*}

since $$m$$ is odd.

Next, since $$k+1 \leq 2^k m$$, we have $$2^{k+1} \mid 2^{2^k m} \mid 10^{2^k m} = 10^n$$. Hence, there is some positive integer $$q$$ such that

\begin{align*} 10^{10^n} & = 10^{2^{k+1}q} \\ & = (10^{2^{k+1}})^q \\ & \equiv (1)^q \pmod{10^{2^k}+1} \\ & \equiv 1 \pmod{10^{2^k}+1}. \end{align*}

Finally, since $$k+1 \lt 10^{2^k m}$$, we have $$2^{k+1} \mid 2^{10^{2^k m}} \mid 10^{10^{2^k m}} = 10^{10^n}$$. Hence, there is some positive integer $$r$$ such that

\begin{align*} 10^{10^{10^n}} & = 10^{2^{k+1}r} \\ & = (10^{2^{k+1}})^r \\ & \equiv (1)^r \pmod{10^{2^k}+1} \\ & \equiv 1 \pmod{10^{2^k}+1}. \end{align*}

Therefore, $$f(n) \equiv 1 + 1 - 1 - 1 = 0 \pmod{10^{2^k}+1}$$. Since $$10^{2^k} + 1$$ is strictly less than $$f(n)$$, it follows that $$f(n)$$ is composite.

### Credit

This puzzle is based on: