همباقیمانده: دو عددی که در تقسیم بر m باقیماندهٔ یکسان دارند
تعریف اصلی و مفهوم باقیمانده در تقسیم
هرگاه عدد صحیح a را بر عدد طبیعی m (که m \gt 1) تقسیم میکنیم، خارجقسمت q و باقیماندهٔ r بهگونهای به دست میآید که:
باقیمانده همواره عددی صحیح و نامنفی و کوچکتر از مقسومعلیه m است. دو عدد a و b را «همباقیمانده» گوییم هرگاه باقیماندهٔ تقسیم هر یک بر m با هم برابر باشد. این رابطه با نماد همنهشتی نمایش داده میشود:
مثال ساده: اعداد 17 و 32 را در نظر بگیرید. هر دو را بر 5 تقسیم کنید: 17 = 5 \times 3 + 2 و 32 = 5 \times 6 + 2. باقیماندهٔ هر دو برابر 2 است. بنابراین مینویسیم $ 17 \equiv 32 \pmod{5} $. همچنین تفاوت این دو عدد یعنی 32 - 17 = 15 بر 5 بخشپذیر است. در واقع خاصیت اساسی همنهشتی این است که $ a \equiv b \pmod{m} $ اگر و تنها اگر $ m \mid (a - b) $.
ویژگیهای بنیادین رابطهٔ همباقیماندگی
رابطهٔ همنهشتی یک رابطهٔ همارزی2 روی مجموعهٔ اعداد صحیح است. این بدان معناست که سه ویژگی مهم را دارد:
- بازتابی: برای هر عدد صحیح a داریم $ a \equiv a \pmod{m} $ (تفاوت a - a = 0 بر هر m بخشپذیر است).
- تقارنی: اگر $ a \equiv b \pmod{m} $ آنگاه $ b \equiv a \pmod{m} $.
- تعدی: اگر $ a \equiv b \pmod{m} $ و $ b \equiv c \pmod{m} $ آنگاه $ a \equiv c \pmod{m} $.
به کمک این ویژگیها میتوان مجموعهٔ اعداد صحیح را به m طبقهٔ مجزا (کلاس همنهشتی3) تقسیم کرد. هر کلاس شامل اعدادی است که بر m باقیماندهٔ یکسان دارند. معمولاً این کلاسها را با باقیماندههای 0, 1, 2, ..., m-1 نمایش میدهند.
| باقیمانده | نمونه اعداد صحیح | نماد همنهشتی |
|---|---|---|
| 0 | ...، -8، -4، 0، 4، 8، ... | $ a \equiv 0 \pmod{4} $ |
| 1 | ...، -7، -3، 1، 5، 9، ... | $ a \equiv 1 \pmod{4} $ |
| 2 | ...، -6، -2، 2، 6، 10، ... | $ a \equiv 2 \pmod{4} $ |
| 3 | ...، -5، -1، 3، 7، 11، ... | $ a \equiv 3 \pmod{4} $ |
عملیات جبری روی همباقیماندهها
یکی از توانمندیهای اصلی مفهوم همنهشتی این است که میتوان جمع، تفریق و ضرب را روی باقیماندهها انجام داد. اگر $ a \equiv b \pmod{m} $ و $ c \equiv d \pmod{m} $ آنگاه:
- جمع:$ a + c \equiv b + d \pmod{m} $
- تفریق:$ a - c \equiv b - d \pmod{m} $
- ضرب:$ a \times c \equiv b \times d \pmod{m} $
مثال عملی: فرض کنید $ 7 \equiv 2 \pmod{5} $ و $ 11 \equiv 1 \pmod{5} $. طبق قانون ضرب داریم $ 7 \times 11 = 77 $ که با $ 2 \times 1 = 2 $ همنهشت است. بهراحتی میتوان بررسی کرد $ 77 \equiv 2 \pmod{5} $ زیرا $ 77 - 2 = 75 $ بر 5 بخشپذیر است. این خاصیت پایهٔ بسیاری از روشهای محاسباتی سریع در نظریهٔ اعداد است.
کاربرد عملی: بررسی اعداد بخشپذیر و محاسبهٔ باقیماندهٔ بزرگ
یکی از کاربردهای جذاب همباقیماندهها، یافتن باقیماندهٔ اعداد بسیار بزرگ بدون نیاز به انجام تقسیم کامل است. برای نمونه باقیماندهٔ $ 2^{100} $ را بر 7 محاسبه کنید. به جای محاسبهٔ توان عظیم، از ویژگی همنهشتی توانی استفاده میکنیم:
$ 2^2 = 4 \equiv 4 \pmod{7} $
$ 2^3 = 8 \equiv 1 \pmod{7} $
$ 2^4 = 2^3 \times 2 \equiv 1 \times 2 = 2 \pmod{7} $
الگو با دورهٔ تناوب 3 تکرار میشود. از آنجا که $ 100 = 3 \times 33 + 1 $، داریم $ 2^{100} \equiv 2^1 = 2 \pmod{7} $. بنابراین باقیماندهٔ تقسیم $ 2^{100} $ بر 7 برابر 2 است. این تکنیک در آزمونهای بخشپذیری و رمزنگاری کلید عمومی مانند آراسای4 بسیار کاربردی است.
چالشهای مفهومی در درک همباقیماندهها
بله. تعریف همنهشتی بر اساس تفاضل است و به علامت اعداد کاری ندارد. برای نمونه $ -3 \equiv 2 \pmod{5} $ زیرا $ -3 - 2 = -5 $ بر 5 بخشپذیر است. در تقسیم استاندارد، باقیمانده همواره نامنفی در نظر گرفته میشود، اما رابطهٔ همنهشتی اعداد منفی را نیز دربر میگیرد.
تقسیم بر خلاف جمع و ضرب مستقیم نیست. اگر $ a \equiv b \pmod{m} $ و $ c $ عددی غیرصفر باشد، به طور کلی $ a/c \equiv b/c \pmod{m} $ برقرار نیست مگر آن که $ c $ و $ m $ نسبت به هم اول5 باشند. در آن صورت میتوان ضرب در وارون ضربی6$ c $ را انجام داد.
برابری معمولی حالت خاصی از همنهشتی با مدول $ m = 0 $ (که در تعریف استاندارد مجاز نیست) یا معنی دقیقتر: دو عدد مساوی حتماً همباقیمانده هستند (باقیماندهٔ یکسان دارند)، اما عکس آن لزوماً درست نیست. همنهشتی به ما اجازه میدهد اعداد مختلف را در یک کلاس قرار دهیم و تساوی دقیق را با تساوی در باقیمانده جایگزین کنیم.
جمعبندی
پاورقی
1 همنهشتی (Congruence): رابطهٔ دودویی روی اعداد صحیح که به صورت $ a \equiv b \pmod{m} $ تعریف میشود و نشاندهندهٔ برابری باقیماندهٔ تقسیم a و b بر m است.
2 رابطهٔ همارزی (Equivalence Relation): رابطهای که سه ویژگی بازتابی، تقارنی و تعدی را داشته باشد و مجموعه را به کلاسهای همارزی مجزا افراز کند.
3 کلاس همنهشتی (Congruence Class): مجموعهٔ همهٔ اعداد صحیحی که با یک عدد معین بر مدول ثابت همنهشت هستند؛ یعنی $ [r] = \{ a \in \mathbb{Z} \mid a \equiv r \pmod{m} \} $.
4 آراسای (RSA): یکی از الگوریتمهای رمزنگاری نامتقارن که امنیت آن بر پایهٔ دشواری فاکتورگیری اعداد بزرگ و استفاده از قضایای همنهشتی مانند قضیهٔ اویلر استوار است.
5 نسبت به هم اول (Coprime یا Relatively Prime): دو عدد صحیح که بزرگترین مقسومعلیه مشترک آنها برابر 1 باشد.
6 وارون ضربی (Modular Inverse): عددی مانند $ a^{-1} $ به گونهای که $ a \times a^{-1} \equiv 1 \pmod{m} $. وجود آن به شرط $ \gcd(a,m)=1 $ تضمین میشود.