2

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.

Arturo Magidin
  • 398,050
12 34
  • 37

2 Answers2

1

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.

Renato Fernandes
  • 537
  • 2
  • 11
0

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\;.$

Angelo
  • 12,328