Show that $x + 1, x^x + 1, x^{x^x} + 1, \dots$ is divisible by $n$ I am doing the pratice in the Junior Problem Seminar by Dr. David A. SANTOS. I came across a question in chapter 2.4 that i had no idea how to do it. This is the question:
Shew that for any natural number n, there is another natural number x
such that each term of the sequence
$x + 1, x^x + 1, x^{x^x} + 1, ....$
is divisible by n
Link of the book : https://www.rotupitti.it/materiali/Santos_Jiunior%20problem%20seminar_2008.pdf
So, $x \equiv x^x \equiv x^{x^x} \equiv -1$ mod n, maybe i can substitute x with 2n - 1, but how should i proof that $ 2n - 1 ^{2n-1} \equiv -1 $ mod n.
 A: As you already notice that if $x = 2n-1$, then $x \equiv -1 \pmod n$.
Now, as $x$ is odd, $x^x \equiv (-1)^x \pmod n \equiv (-1) \pmod n$, since $(-1)^x$ is product of an odd number of terms $(-1)$.
For the same reason, $x^{x^x} \equiv (-1)^{x^x} \pmod n \equiv (-1) \pmod n$, since $x^x$ is an odd number, and so on.
So you just to need to prove (by induction) that  $x^{x^{\unicode{x22F0}^{x}}}$ is an odd number for any number of iterations.
A: Let $\,n,x,y\,$ be any three natural numbers.
First of all we will prove the following property.
Property 1 :
If $\;2n\mid x+1\;$ and $\;2n\mid y+1\;$ then $\,2n\mid x^y+1\,.$
Proof :
$x=2\lambda n-1\quad$ where $\;\lambda\in\mathbb N\;,$
$y=2\mu n-1\quad$ where $\;\mu\in\mathbb N\;.$
$\begin{align}\displaystyle x^y&=\!\big(2\lambda n-1\big)^{2\mu n-1}=\!\sum_\limits{h=0}^{2\mu n-1}\binom{2\mu n-1}h\big(2\lambda n\big)^h\big(\!-1\big)^{2\mu n-1-h}=\\
&=\big(\!-1\big)^{2\mu n-1}\!+2\lambda n\!\sum_\limits{h=1}^{2\mu n-1}\!\!\binom{2\mu n\!-\!1}h\big(2\lambda n\big)^{h-1}\big(\!-1\big)^{2\mu n-1-h}=\\
&=-1+2\alpha n\quad,\end{align}$
where $\;\alpha=\lambda\sum_\limits{h=1}^{2\mu n-1}\binom{2\mu n-1}h\big(2\lambda n\big)^{h-1}\big(\!-1\big)^{2\mu n-1-h}\in\mathbb Z\;.$
Since $\;x^y+1=2\alpha n\;,\;$ it follows that $\;\alpha\in\mathbb N\;$ and
$2n\mid x^y+1\;.\qquad$ Q.E.D.

By applying repeatedly the Property 1, we get that, for any natural number $\,n\,$, there exists another natural number $\,x=2n-1\,$ such that
$2n\mid x+1\quad,$
$2n\mid x^x+1\quad,$
$2n\mid x^{x^x}+1\quad,$
$2n\mid x^{x^{x^x}}+1\quad,$
$2n\mid x^{x^{x^{x^x}}}+1\quad,$
…………………..$\quad.$
Hence ,
$x+1\;,\;x^x+1\;,\;x^{x^x}+1\;,\;x^{x^{x^x}}+1\;,\;x^{x^{x^{x^x}}}+1\;,\;\ldots\;,\;$ are all divisible by $\;2n\;.$
