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

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

1 پاسخ

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

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

♥ حمایت مالی

راهنمایی:

  • برای رفتن به سطر بعدی دو بار Enter بزنید.
  •  یک بار Enter یک فاصله محسوب می‌شود.
  •  _ایتالیک_ یا I و **پررنگ** یا B
  •  نقل‌قول با قراردادن > در ابتدای خط یا ❝
  • برای چپ به راست کردن متن کلیدهای Ctrl+Shift سمت چپ کیبورد را فشار دهید
  •  برای تایپ فرمول ابتدا روی ریاضی کلیک کرده و سپس به کمک آیکون‌های موجود فرمول را در بین دو علامت دلار

<math> $ $ </math>

بنویسید.

  •  برای اینکه فرمول در خط بعدی و وسط صفحه قرار گیرد دو علامت دلار اضافی بنویسید

<math> $$ $$ </math>


☑ راهنمایی بیشتر: راهنمای تایپ
61 نفر آنلاین
0 عضو و 61 مهمان در سایت حاضرند
بازدید امروز: 333
بازدید دیروز: 6817
بازدید کل: 4709475
...