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

[SOLVED]

2 comments

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:

Post a comment

RSS