به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+3 امتیاز
84 بازدید
سوال شده در دانشگاه توسط

برای $ n\geq 2 $ ثابت کنید: $$ \overbrace {2^{2^{...^2}}}^ {\text{جمله}n} \equiv \overbrace{2^{2^{...^2}}}^ {\text{جمله}n-1} \quad (mod\ n)$$

1 پاسخ

+1 امتیاز
پاسخ داده شده توسط
ویرایش شده توسط
 
بهترین پاسخ
$$ \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) $ و حکم ثابت شد.

دارای دیدگاه توسط
در خط 17 نوشتید:" لذا با قرار دادن رابطه اول نتیجه می شود."با قرار دادن چی؟
به محفل ریاضی ایرانیان خوش آمدید!
کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
حمایت مالی
...