$$ \overbrace
{2^{2^{...^2}}}^
{\text{جمله}n}
\equiv \overbrace{2^{2^{...^2}}}^
{\text{جمله}n-1}
\quad (mod\ n)$$
قرار میدهیم $ x_{1} =2 $ و $ x_{n} = 2^{ x_{n-1} } $ پس رابطه ی بالا که باید اثبات شود به صورت ${x_{n}} \equiv {x_{n-1}} \quad (mod\ n)$ در می آید. با استقرا حکم معادل زیر که شامل حکم بالا است را ثابت میکنیم:
برای هر $n $ یک $ m < n $ وجود دارد که داریم:
$$ {x_{m}} \equiv {x_{m+1}} \equiv {x_{m+2}} ....\quad (mod\ n) $$
پایه استقرا: اگر $ n=2 $ آنگاه برای $ m =1$ رابطه ی بالا برقرار است چون تک تک جملات دنباله بر $ 2 $ بخش پذیر هستند.
فرض استقرا: فرض حکم برای تمام مقادیر کمتر از $ n$ برقرار باشد نشان می دهیم حکم برای $ n $ برقرار است. فرض کنید $n= 2^{a}b $ که $ b $ عددی فرد است. اگر دو رابطه ی زیر را نشان دهیم حکم ثابت می شود.
وجود دارد $ m < n $ که
$$ {x_{m}} \equiv {x_{m+1}} \equiv {x_{m+2}} ....\quad (mod\ 2^{a})$$
و
$${x_{m}} \equiv {x_{m+1}} \equiv {x_{m+2}} ....\quad (mod\ b) $$
برای رابطه ی اول داریم:
$${x_{m+1}} - {x_{m}} =\overbrace
{2^{2^{...^2}}}^
{\text{جمله}m+1}-\overbrace
{2^{2^{...^2}}}^
{\text{جمله}m}=\overbrace
{2^{2^{...^2}}}^
{\text{جمله}m}( 2^{\overbrace
{2^{2^{...^2}}}^
{\text{جمله}m}-\overbrace
{2^{2^{...^2}}}^
{\text{جمله}m-1}} -1)$$
یعنی $ {x_{m}} \equiv {x_{m+1}} \quad (mod\ \overbrace
{2^{2^{...^2}}}^
{\text{جمله}m}) $
و براحتی ثابت میشود که $2^{a} \leq n < \overbrace
{2^{2^{...^2}}}^
{\text{جمله}n-1} $
لذا با قرار دادن $ m=n-1 $ رابطه ی اول برقرار می شود.
برای رابطه ی دوم توجه کنید که $ \phi(b) < n $ است. که در آن $ \phi(b) $ تابع اویلر است. لذا در فرض استقرا صدق می کند پس $ m < \phi(b) $ موجود است که
$$ {x_{m}} \equiv {x_{m+1}} \equiv {x_{m+2}} ....\quad (mod\ \phi(b) ) $$
اگر نشان دهیم که
$$ {x_{m+1}} \equiv {x_{m+2}} \equiv {x_{m+3}} ....\quad (mod\ b) $$
آنگاه از اینکه $ m +1 \leq \phi(b) < n$ است رابطه ی دوم و حکم ثابت می شود.
نشان میدهیم از رابطه $ {x_{m}} \equiv {x_{m+1}} \quad (mod\ \phi(b) ) $ رابطه ی
$ {x_{m+1}} \equiv {x_{m+2}} \quad (mod\ b) $ نتیجه می شود.
از رابطه $ {x_{m}} \equiv {x_{m+1}} \quad (mod\ \phi(b) ) $ داریم:
$$ \phi(b) \mid {x_{m+1}} - {x_{m}} =\overbrace
{2^{2^{...^2}}}^
{\text{جمله}m+1}-\overbrace
{2^{2^{...^2}}}^
{\text{جمله}m}$$
فرض کنید $\phi(b) \times z ={x_{m+1}} - {x_{m}} $ در اینصورت:
$$\begin{align}
{x_{m+2}} - {x_{m+1}} &=\overbrace
{2^{2^{...^2}}}^
{\text{جمله}m+2}-\overbrace
{2^{2^{...^2}}}^
{\text{جمله}m+1}\\
&=\overbrace
{2^{2^{...^2}}}^
{\text{جمله}m+1}( 2^{\overbrace
{2^{2^{...^2}}}^
{\text{جمله}m+1}-\overbrace
{2^{2^{...^2}}}^
{\text{جمله}m}} -1)=\overbrace
{2^{2^{...^2}}}^
{\text{جمله}m+1}( 2^{{x_{m+1}} - {x_{m}}} -1)\end{align}$$
$(*)$
حال از رابطه ی اویلر داریم $ 2^{\phi(b)} \equiv 1 \quad (mod\ b ) $ پس
$ 2^{\phi(b) \times z} \equiv 1 \quad (mod\ b ) $ یعنی $ 2^{{x_{m+1}} - {x_{m}} } \equiv 1 \quad (mod\ b ) $
پس $ b $ عبارت $ 2^{{x_{m+1}} - {x_{m}} } -1 $ را عاد می کند
یعنی با توجه به رابطه$(*)$،
$ b $ عبارت${x_{m+2}} - {x_{m+1}} $ را عاد میکند پس $ {x_{m+1}} \equiv {x_{m+2}} \quad (mod\ b) $ و حکم ثابت شد.
