خاصیت تعدی همنهشتی: اگر a ≡ b و b ≡ c، آنگاه a ≡ c
۱. تعریف همنهشتی و رابطهٔ تعدی در ریاضیات
در ریاضیات، میگوییم دو عدد صحیح a و b به پیمانهٔ n همنهشت1 هستند، اگر اختلاف آنها بر n بخشپذیر باشد. به زبان ریاضی:
به بیان دیگر، a و b هنگام تقسیم بر n باقیماندهٔ یکسانی دارند. خاصیت تعدی (تراگذر)2 میگوید: اگر a ≡ b (mod n) و b ≡ c (mod n)، آنگاه a ≡ c (mod n). برای درک بهتر این قاعده، یک مثال عددی ساده میآوریم.
مثال عملی: فرض کنید معلمی از دانشآموزان میخواهد اعدادِ دارای باقیماندهٔ ۲ بر پیمانهٔ ۵ را تشخیص دهند. عدد ۷ با ۱۲ همنهشت است (زیرا ۱۲-۷=۵ بر ۵ بخشپذیر است). همچنین ۱۲ با ۱۷ همنهشت است (۱۷-۱۲=۵). آنگاه خاصیت تعدی نتیجه میدهد که ۷ با ۱۷ نیز همنهشت است، و راستیآزمایی میکند ۱۷-۷=۱۰ که بر ۵ بخشپذیر است.
۲. اثبات گامبهگام خاصیت تعدی در همنهشتی
برای اثبات این ویژگی از تعریف همنهشتی استفاده میکنیم. فرض کنید:
- $a \equiv b \pmod{n}$ یعنی $a - b = n \cdot k_1$ برای یک عدد صحیح $k_1$.
- $b \equiv c \pmod{n}$ یعنی $b - c = n \cdot k_2$ برای یک عدد صحیح $k_2$.
حال دو تساوی را جمع میکنیم:
$\Rightarrow a - c = n (k_1 + k_2)$
چون $k_1 + k_2$ عددی صحیح است، پس $n \mid (a-c)$ و در نتیجه $a \equiv c \pmod{n}$. اثبات کامل شد. این گامها نشان میدهد که خاصیت تعدی به طور خودکار از تعریف همنهشتی پیروی میکند.
| ویژگی | تعریف ریاضی | مثال در اعداد (پیمانه ۴) |
|---|---|---|
| بازتابی3 | $a \equiv a$ | ۵ ≡ ۵ (mod ۴) |
| تقارن4 | اگر $a \equiv b$ آنگاه $b \equiv a$ | ۸ ≡ ۱۲ ⇒ ۱۲ ≡ ۸ (mod ۴) |
| تعدی (تراگذر) | اگر $a \equiv b$ و $b \equiv c$، آنگاه $a \equiv c$ | ۲ ≡ ۶ و ۶ ≡ ۱۰ ⇒ ۲ ≡ ۱۰ (mod ۴) |
۳. کاربرد عملی: بررسی تساوی در ساعت و تقویم
یکی از سادهترین کاربردهای خاصیت تعدی در زندگی روزمره، نمایش ساعت ۱۲ ساعته است. در ساعت، عدد ۱۳ با ۱ همنهشت است (پیمانه ۱۲). فرض کنید a=۱۳، b=۱ و c=۲۵. میدانیم $13 \equiv 1 \pmod{12}$ و $1 \equiv 25 \pmod{12}$ (چون ۲۵-۱=۲۴ بر ۱۲ بخشپذیر است). با خاصیت تعدی نتیجه میگیریم ۱۳ و ۲۵ روی ساعت یکسان نشان داده میشوند. به بیان دیگر، هر سه در یک «کلاس همارزی»5 قرار دارند.
مثال دیگر در نظریه اعداد: فرض کنید در یک مسئله، باقیماندهٔ عددی بر ۷ را جستجو میکنیم. اگر بدانیم x ≡ ۵ (mod ۷) و ۵ ≡ ۱۲ (mod ۷)، آنگاه بدون محاسبهٔ مجدد میتوانیم بگوییم x ≡ ۱۲ (mod ۷). این ویژگی در حل معادلات همنهشتی و رمزنگاری (مانند الگوریتم آراسای6) بسیار مهم است.
۴. چالشهای مفهومی: پرسش و پاسخ
سؤال ۱: آیا خاصیت تعدی برای هر رابطهای صادق است؟ مثلاً رابطهٔ «دوست داشتن» در زندگی واقعی تعدی دارد؟
پاسخ: خیر. خاصیت تعدی فقط برای روابط همارزی و برخی روابط خاص مانند «بزرگتر بودن» ($>$) یا «مساوی بودن» ($=$) صادق است. رابطهٔ «دوست داشتن» لزوماً تعدی نیست؛ ممکن است الف با ب دوست باشد و ب با ج، اما الف با ج دوست نباشد. در ریاضیات، وجود تعدی برای رابطهای الزامی نیست مگر آنکه اثبات شود.
سؤال ۲: اگر a ≡ b و b ≡ c نباشد، باز هم میتوان تعدی را نتیجه گرفت؟
پاسخ: خیر. تعدی به صراحت هردوی این فرضها را نیاز دارد. اگر تنها یکی از آنها برقرار باشد یا هیچکدام، نمیتوان نتیجهٔ a ≡ c را گرفت. به عبارت دیگر، تعدی یک شرط «اگر ... آنگاه ...» است و مقدم آن باید کاملاً برآورده شود.
سؤال ۳: آیا خاصیت تعدی برای همنهشتی در پیمانههای مختلف نیز کار میکند؟ مثلاً اگر a ≡ b (mod m) و b ≡ c (mod n) با m \neq n، آنگاه a ≡ c بر کدام پیمانه؟
پاسخ: خیر. تعدی زمانی معنی دارد که پیمانه یکسان باشد. در غیر اینصورت ممکن است نتیجه نادرست شود. مثلاً ۸ ≡ ۲ (mod ۶) و ۲ ≡ ۵ (mod ۳)، اما ۸ با ۵ نه به پیمانهٔ ۶ و نه به پیمانهٔ ۳ همنهشت نیست (۸-۵=۳ بر ۶ بخشپذیر نیست، بر ۳ بخشپذیر است اما به طور همزمان پیمانهها متفاوتند). بنابراین شرط یکسانی پیمانه ضروری است.
خاصیت تعدی در همنهشتی یکی از پایههای استدلال در نظریه اعداد است. این ویژگی تضمین میکند که اگر دو جفت عدد با یک عدد میانی مشترک همنهشت باشند، میتوان آن دو را مستقیماً برابر در نظر گرفت. همراه با بازتابی و تقارن، رابطهٔ همارزی را میسازد که در طبقهبندی اشیاء، حل معادلات همنهشتی، طراحی الگوریتمها و حتی ساختار ساعت و تقویم کاربرد دارد. درک این مفهوم، گامی اساسی برای مطالعهٔ پیشرفتهتر جبر مجرد و رمزنگاری است.
پاورقی
1 همنهشتی (Congruence): رابطهای بین دو عدد صحیح که بر اساس بخشپذیری اختلاف آنها بر یک عدد ثابت (پیمانه) تعریف میشود.
2 تعدی یا تراگذر (Transitivity): ویژگی یک رابطه که در آن از R(a,b) و R(b,c) بتوان R(a,c) را نتیجه گرفت.
3 بازتابی (Reflexivity): خاصیتی که میگوید هر عنصر با خودش در رابطه است: a ≡ a.
4 تقارن (Symmetry): اگر a ≡ b آنگاه b ≡ a، که در همنهشتی به راحتی از تعریف برقرار است.
5 کلاس همارزی (Equivalence Class): مجموعه همه اعضایی که با یک عضو مشخص رابطهٔ همارزی (مانند همنهشتی) دارند.
6 آراسای (RSA): الگوریتم رمزنگاری نامتقارن که از عملیات همنهشتی و ویژگی تعدی برای صحتسنجی استفاده میکند.