افراز مجموعه اعداد صحیح: تقسیم اعداد صحیح به کلاسهای همنهشتی جدا و کامل
رابطه همنهشتی و ایجاد کلاسهای جدا از هم
در ریاضیات، رابطهٔ همنهشتی1 یکی از مهمترین مفاهیم در نظریه اعداد است. فرض کنید $n$ یک عدد صحیح مثبت (پیمانه) باشد. میگوییم دو عدد صحیح $a$ و $b$ به پیمانه $n$ همنهشت هستند، هرگاه تفاوت آنها بر $n$ بخشپذیر باشد. این رابطه را با نماد $a \equiv b \pmod{n}$ نشان میدهیم.
رابطهٔ همنهشتی یک رابطه همارزی2 است، یعنی سه ویژگی زیر را دارد:
- بازتابی: برای هر عدد صحیح $a$ داریم $a \equiv a \pmod{n}$.
- تقارنی: اگر $a \equiv b \pmod{n}$ آنگاه $b \equiv a \pmod{n}$.
- ترایایی: اگر $a \equiv b \pmod{n}$ و $b \equiv c \pmod{n}$ آنگاه $a \equiv c \pmod{n}$.
هر رابطه همارزی، مجموعهٔ مورد نظر (در اینجا اعداد صحیح $\mathbb{Z}$) را به کلاسهای همارزی (یا کلاسهای همنهشتی) افراز میکند. کلاس همنهشتی یک عدد $a$ به پیمانه $n$، مجموعه همه اعدادی است که با $a$ همنهشت هستند.
کلاسهای باقیمانده و افراز کامل اعداد صحیح
به ازای یک پیمانه ثابت $n$، اعداد صحیح دقیقاً به $n$ کلاس همنهشتی تقسیم میشوند. هر کلاس شامل تمام اعدادی است که در تقسیم بر $n$ یک باقیماندهٔ مشخص (از $0$ تا $n-1$) دارند. به این کلاسها، کلاسهای باقیمانده به پیمانه $n$ میگوییم.
ویژگی کلیدی افراز این است که:
- کلاسها جدا از هم هستند (هیچ عضوی در دو کلاس متفاوت قرار ندارد).
- اجتماع همه کلاسها تمام مجموعه اعداد صحیح را میپوشاند (هیچ عضوی بیرون از کلاسها نمیماند).
| کلاس باقیمانده | نماد ریاضی | چند نمونه از اعضا |
|---|---|---|
| باقیمانده $0$ به پیمانه $4$ | $[0]_4$ یا $\overline{0}$ | $\dots, -8, -4, 0, 4, 8, 12, \dots$ |
| باقیمانده $1$ به پیمانه $4$ | $[1]_4$ | $\dots, -7, -3, 1, 5, 9, 13, \dots$ |
| باقیمانده $2$ به پیمانه $4$ | $[2]_4$ | $\dots, -6, -2, 2, 6, 10, 14, \dots$ |
| باقیمانده $3$ به پیمانه $4$ | $[3]_4$ | $\dots, -5, -1, 3, 7, 11, 15, \dots$ |
همانطور که در جدول بالا میبینید، این چهار کلاس هیچ عضوی مشترک ندارند و هر عدد صحیحی (مثلاً $-10$ یا $17$) دقیقاً در یکی از این کلاسها قرار میگیرد. بنابراین $\{ [0]_4, [1]_4, [2]_4, [3]_4 \}$ یک افراز3 برای مجموعه $\mathbb{Z}$ است.
نمایش گامبهگام افراز اعداد صحیح به پیمانهٔ ۵
برای درک بهتر، مراحل افراز مجموعه اعداد صحیح به پیمانه $5$ را گام به گام انجام میدهیم.
- تعیین پیمانه: عدد $n=5$ را انتخاب میکنیم.
- باقیماندههای ممکن: باقیماندههای تقسیم بر $5$ عبارتند از $0,1,2,3,4$.
- تشکیل کلاسها: برای هر باقیمانده $r$، کلاس $[r]_5$ را به صورت $\{ r + 5k \mid k \in \mathbb{Z} \}$ تعریف میکنیم.
- جدایی کلاسها: بررسی میکنیم که اگر $r_1 \neq r_2$ آنگاه $[r_1]_5 \cap [r_2]_5 = \varnothing$.
- پوشش کامل: برای هر عدد صحیح دلخواه مانند $a$، باقیماندهٔ منحصربهفرد آن بر $5$ را مییابیم و بنابراین $a$ عضوی از آن کلاس است.
چالشهای مفهومی در افراز اعداد صحیح
پاسخ: بله. به عنوان مثال، $-3 \equiv 2 \pmod{5}$ زیرا $2 - (-3) = 5$ که بر $5$ بخشپذیر است. همنهشتی به علامت عدد بستگی ندارد، فقط به تفاوت آنها مربوط میشود.
پاسخ: وقتی یک عدد صحیح را بر $n$ تقسیم میکنیم، باقیمانده فقط میتواند یکی از $n$ مقدار $0, 1, 2, \dots, n-1$ باشد. هر کلاس برابر است با مجموعه اعدادی که یک باقیماندهٔ ثابت دارند. از آنجا که باقیماندهها متمایز و تمامشمار هستند، دقیقاً $n$ کلاس خواهیم داشت.
پاسخ: برای $n=1$، همهٔ اعداد صحیح با یکدیگر همنهشت هستند (زیرا تفاوت هر دو عدد بر $1$ بخشپذیر است). بنابراین تنها یک کلاس شامل همهٔ اعداد صحیح خواهیم داشت. این افراز (تککلاسه) درست اما چندان کاربردی نیست، زیرا هیچ تمایزی بین اعداد قائل نمیشود.
جمعبندی
پاورقی
1 همنهشتی (Congruence): رابطهای بین دو عدد صحیح که تفاضل آنها بر یک عدد ثابت (پیمانه) بخشپذیر باشد.
2 رابطه همارزی (Equivalence Relation): رابطهای دوتایی که بازتابی، تقارنی و ترایایی باشد.
3 افراز (Partition): تقسیم یک مجموعه به زیرمجموعههای ناتهی، جدا از هم و پوشای کامل.
4 رمزنگاری (Cryptography): علم و فن نوشتن و شکستن رمزها برای تأمین امنیت اطلاعات.