هم‌نهشتی و نظریهٔ اعداد (گسسته)

چرا هم‌نهشتی مهم است؟

ساعت ۲ است؛ ۱۷ ساعت بعد چند است؟ $2+17=19$ ادامهٔ فرمول را افقی ببین، ولی ساعتِ ۱۹ نداریم. باقیماندهٔ $19$ ادامهٔ فرمول را افقی ببین بر $12$ ادامهٔ فرمول را افقی ببین برابر $7$ ادامهٔ فرمول را افقی ببین است، پس ساعت ۷. ایدهٔ کل این فصل همین است: فقط باقیمانده اهمیت دارد.

هم‌نهشتی — تعریف و قوانین

تعریف: برای دو عدد صحیح $a,b$ ادامهٔ فرمول را افقی ببین و عدد طبیعی $m$ ادامهٔ فرمول را افقی ببین:
$a \equiv b \pmod{m} \iff m \mid (a - b)$

سه بیان هم‌ارز: $m$ ادامهٔ فرمول را افقی ببین عدد $a-b$ ادامهٔ فرمول را افقی ببین را می‌شمارد؛ $a$ ادامهٔ فرمول را افقی ببین و $b$ ادامهٔ فرمول را افقی ببین باقیماندهٔ یکسان بر $m$ ادامهٔ فرمول را افقی ببین دارند؛ و $a = b + km$ ادامهٔ فرمول را افقی ببین برای یک $k$ ادامهٔ فرمول را افقی ببین صحیح.

دستهٔ هم‌نهشتی $[r]_m$ ادامهٔ فرمول را افقی ببین مجموعهٔ همهٔ اعداد با باقیماندهٔ $r$ ادامهٔ فرمول را افقی ببین است، مثلاً $[1]_3 = \{\ldots,-5,-2,1,4,7,\ldots\}$ ادامهٔ فرمول را افقی ببین.

قوانین طلایی

اگر $a \equiv b$ ادامهٔ فرمول را افقی ببین و $c \equiv d$ ادامهٔ فرمول را افقی ببین (به پیمانهٔ $m$ ادامهٔ فرمول را افقی ببین):

عملیات	قانون
جمع	$a+c \equiv b+d$ ادامهٔ فرمول را افقی ببین ✓ همیشه
تفریق	$a-c \equiv b-d$ ادامهٔ فرمول را افقی ببین ✓ همیشه
ضرب	$ac \equiv bd$ ادامهٔ فرمول را افقی ببین ✓ همیشه
توان	$a^n \equiv b^n$ ادامهٔ فرمول را افقی ببین ✓ همیشه
تقسیم	شرط دارد

نتیجهٔ کاربردی: مضربِ پیمانه را می‌توان آزادانه جابه‌جا کرد: $a \equiv a \pm mk \pmod m$ ادامهٔ فرمول را افقی ببین.

قانون ساده‌سازی — مهم‌ترین استثنا

قضیهٔ حذف: اگر $ac \equiv bc \pmod m$ ادامهٔ فرمول را افقی ببین و $d = \gcd(c,m)$ ادامهٔ فرمول را افقی ببین، آنگاه
$a \equiv b \pmod{\tfrac{m}{d}}$

حالت طلایی: اگر $\gcd(c,m)=1$ ادامهٔ فرمول را افقی ببین باشد، پیمانه عوض نمی‌شود.

اینجاست که بیشترین اشتباه رخ می‌دهد: حذفِ یک عامل مشترک بدون بررسی $\gcd$ ادامهٔ فرمول را افقی ببین، پیمانه را اشتباه باقی می‌گذارد.

تکنیک‌های محاسبهٔ باقیمانده

۱. ساده‌سازی پایه: پایه را اول به کوچک‌ترین معادلش تبدیل کن، بعد توان بزن.

۲. معادل منفی: اگر پایه نزدیک پیمانه است، معادل منفی کار را بسیار ساده می‌کند — مثلاً $1000 \equiv -1 \pmod 7$ ادامهٔ فرمول را افقی ببین، پس $1000^{13} \equiv (-1)^{13} = -1$ ادامهٔ فرمول را افقی ببین.

نکتهٔ طلایی: برای تبدیل منفی به مثبت، پیمانه را اضافه کن: $-2 \equiv 5 \pmod 7$ ادامهٔ فرمول را افقی ببین.

۳. الگویابی: توان‌های متوالی را حساب کن تا الگو تکرار شود، بعد توان را بر طول دوره تقسیم کن.

۴. تجزیهٔ توان: کوچک‌ترین توانی که به $1$ ادامهٔ فرمول را افقی ببین می‌رسد را پیدا کن و توان بزرگ را بر آن بشکن. مثلاً $2^3 \equiv 1 \pmod 7$ ادامهٔ فرمول را افقی ببین، پس $2^{50} = (2^3)^{16} \cdot 2^2 \equiv 4$ ادامهٔ فرمول را افقی ببین.

جدول رقم یکان توان‌ها

پایه	دوره	ارقام یکان
$2$ ادامهٔ فرمول را افقی ببین	۴	$2, 4, 8, 6$ ادامهٔ فرمول را افقی ببین
$3$ ادامهٔ فرمول را افقی ببین	۴	$3, 9, 7, 1$ ادامهٔ فرمول را افقی ببین
$4$ ادامهٔ فرمول را افقی ببین	۲	$4, 6$ ادامهٔ فرمول را افقی ببین
$7$ ادامهٔ فرمول را افقی ببین	۴	$7, 9, 3, 1$ ادامهٔ فرمول را افقی ببین
$8$ ادامهٔ فرمول را افقی ببین	۴	$8, 4, 2, 6$ ادامهٔ فرمول را افقی ببین
$9$ ادامهٔ فرمول را افقی ببین	۲	$9, 1$ ادامهٔ فرمول را افقی ببین
$0,1,5,6$ ادامهٔ فرمول را افقی ببین	۱	همیشه ثابت

وارون ضربی

تعریف: $a^{-1}$ ادامهٔ فرمول را افقی ببین عددی است که $a \cdot a^{-1} \equiv 1 \pmod m$ ادامهٔ فرمول را افقی ببین.

شرط وجود: وارون ضربی وجود دارد اگر و فقط اگر $\gcd(a,m) = 1$ ادامهٔ فرمول را افقی ببین.

اثبات: معادلهٔ $ax \equiv 1 \pmod m$ ادامهٔ فرمول را افقی ببین یعنی $ax - km = 1$ ادامهٔ فرمول را افقی ببین، و طبق قضیهٔ بزوت این معادله جواب صحیح دارد دقیقاً وقتی $\gcd(a,m) \mid 1$ ادامهٔ فرمول را افقی ببین.

برای حل $ax \equiv c \pmod m$ ادامهٔ فرمول را افقی ببین کافی است دو طرف را در $a^{-1}$ ادامهٔ فرمول را افقی ببین ضرب کنی. وارون را می‌توان با آزمون‌وخطا (برای پیمانه‌های کوچک) یا با الگوریتم اقلیدس توسعه‌یافته یافت.

معادلات سیالهٔ خطی

قضیه: معادلهٔ $ax + by = c$ ادامهٔ فرمول را افقی ببین جواب صحیح دارد اگر و فقط اگر $\gcd(a,b) \mid c$ ادامهٔ فرمول را افقی ببین.

اثبات ضرورت: اگر $d = \gcd(a,b)$ ادامهٔ فرمول را افقی ببین آنگاه $d \mid a$ ادامهٔ فرمول را افقی ببین و $d \mid b$ ادامهٔ فرمول را افقی ببین، پس $d \mid ax+by = c$ ادامهٔ فرمول را افقی ببین.

مثلاً $4x + 6y = 11$ ادامهٔ فرمول را افقی ببین اصلاً جواب ندارد، چون $\gcd(4,6)=2$ ادامهٔ فرمول را افقی ببین و $2 \nmid 11$ ادامهٔ فرمول را افقی ببین.

روش حل: معادله را به یک هم‌نهشتی تبدیل کن (به پیمانهٔ یکی از ضرایب)، آن را حل کن، و جواب را در معادلهٔ اصلی بگذار تا متغیر دوم به دست آید.

ساختار کامل جواب: اگر $(x_0,y_0)$ ادامهٔ فرمول را افقی ببین یک جواب خاص باشد، همهٔ جواب‌ها به شکل زیرند:
$x = x_0 + \frac{b}{d}k, \qquad y = y_0 - \frac{a}{d}k, \qquad k \in \mathbb{Z}$

در مسائل کاربردی (که $x,y$ ادامهٔ فرمول را افقی ببین باید نامنفی یا محدود باشند)، شرط‌ها را در آخر روی $k$ ادامهٔ فرمول را افقی ببین اعمال کن تا بازهٔ مجاز $k$ ادامهٔ فرمول را افقی ببین به دست آید.

قضیهٔ فرمای کوچک

قضیه: اگر $p$ ادامهٔ فرمول را افقی ببین اول باشد و $p \nmid a$ ادامهٔ فرمول را افقی ببین:
$a^{p-1} \equiv 1 \pmod{p}$
فرم معادل: برای هر $a$ ادامهٔ فرمول را افقی ببین، رابطهٔ $a^p \equiv a \pmod p$ ادامهٔ فرمول را افقی ببین برقرار است.

ایدهٔ اثبات: مجموعهٔ $\{a, 2a, \ldots, (p-1)a\}$ ادامهٔ فرمول را افقی ببین به پیمانهٔ $p$ ادامهٔ فرمول را افقی ببین همان مجموعهٔ $\{1,2,\ldots,p-1\}$ ادامهٔ فرمول را افقی ببین است (فقط با ترتیب متفاوت). ضرب همهٔ اعضا می‌دهد $a^{p-1}(p-1)! \equiv (p-1)!$ ادامهٔ فرمول را افقی ببین، و چون $\gcd((p-1)!,p)=1$ ادامهٔ فرمول را افقی ببین می‌توان $(p-1)!$ ادامهٔ فرمول را افقی ببین را حذف کرد.

این قضیه، توان‌های بسیار بزرگ را در یک خط رام می‌کند.

قضیهٔ اویلر — تعمیم فرما

تابع فی اویلر $\varphi(n)$ ادامهٔ فرمول را افقی ببین: تعداد اعداد $1$ ادامهٔ فرمول را افقی ببین تا $n$ ادامهٔ فرمول را افقی ببین که با $n$ ادامهٔ فرمول را افقی ببین نسبت به هم اول‌اند.

\varphi(n) = n \left(1 - \frac{1}{p_1}\right)\cdots\left(1 - \frac{1}{p_k}\right)

$n$ ادامهٔ فرمول را افقی ببین	$\varphi(n)$ ادامهٔ فرمول را افقی ببین
$p$ ادامهٔ فرمول را افقی ببین (اول)	$p-1$ ادامهٔ فرمول را افقی ببین
$p^k$ ادامهٔ فرمول را افقی ببین	$p^{k-1}(p-1)$ ادامهٔ فرمول را افقی ببین

قضیهٔ اویلر: اگر $\gcd(a,m)=1$ ادامهٔ فرمول را افقی ببین آنگاه $a^{\varphi(m)} \equiv 1 \pmod{m}$ ادامهٔ فرمول را افقی ببین.

قضیهٔ فرما حالت خاصِ این قضیه برای $m=p$ ادامهٔ فرمول را افقی ببین است. وقتی پیمانه مرکب است، اویلر ابزار درست است نه فرما.

قضیهٔ باقیماندهٔ چینی (CRT)

قضیه: اگر $m_1, \ldots, m_k$ ادامهٔ فرمول را افقی ببین دوبه‌دو نسبت به هم اول باشند، دستگاهِ
$x \equiv a_1 \pmod{m_1}, \quad \ldots, \quad x \equiv a_k \pmod{m_k}$
جواب یکتا به پیمانهٔ $M = m_1 m_2 \cdots m_k$ ادامهٔ فرمول را افقی ببین دارد.

روش عملی (جایگذاری پیاپی): از معادلهٔ اول $x$ ادامهٔ فرمول را افقی ببین را برحسب پارامتر بنویس، در معادلهٔ دوم بگذار، پارامتر جدید بگیر، و همین‌طور تا آخر. این روش برای دستگاه‌های ۲ و ۳ معادله‌ای سریع‌تر از فرمول است.

فرمول مستقیم:

x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}, \qquad M_i = \frac{M}{m_i}, \qquad y_i \equiv M_i^{-1} \pmod{m_i}

خلاصهٔ طلایی — کدام ابزار، کِی؟

موقعیت	ابزار مناسب
باقیماندهٔ توان بزرگ	ساده‌سازی پایه + الگو
پایه نزدیک به پیمانه	معادل منفی
رقم یکان	الگوی دوره‌ای به پیمانهٔ ۱۰
پیمانهٔ اول	قضیهٔ فرما
پیمانهٔ مرکب	قضیهٔ اویلر
دستگاه با پیمانه‌های نسبی اول	CRT
$ax \equiv c \pmod m$ ادامهٔ فرمول را افقی ببین	وارون ضربی
$ax + by = c$ ادامهٔ فرمول را افقی ببین	هم‌نهشتی + جواب عمومی

چهار توصیهٔ پایانی:
۱. پیمانهٔ کوچک‌تر را انتخاب کن.
۲. اعداد بزرگ را فوراً ساده کن.
۳. همیشه معادل منفی را هم بررسی کن.
۴. شرط نامنفی بودن را در آخر اعمال کن.

مطالب فراتر از کتاب

درسنامهٔ کامل این‌ها را هم پوشش می‌دهد: الگوریتم اقلیدس توسعه‌یافته با جدول گام‌به‌گام برای یافتن وارون ضربی، اثبات کامل قضایای فرما و اویلر، فرمول مستقیم CRT با مثال حل‌شده، کاربرد در رمزنگاری RSA (که مستقیماً روی قضیهٔ اویلر و وارون ضربی بنا شده)، و مسائل ترکیبی مثل یافتن دو رقم آخر $7^{999}$ ادامهٔ فرمول را افقی ببین.

خلاصه‌ی درسنامه