\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) و حکم ثابت شد.
