قاعده حذف: حذف عامل نسبت به پیمانهٔ اول
۱. مفهوم همنهشتی و شرط اول بودن نسبت به پیمانه
پیش از پرداختن به قاعده حذف، باید مفهوم «همنهشتی»3 را مرور کنیم. دو عدد صحیح مانند x و y را نسبت به پیمانهٔ m همنهشت مینامیم، هرگاه اختلاف آنها بر m بخشپذیر باشد. این رابطه را به شکل زیر نشان میدهیم:
به عنوان مثال، $17 \equiv 5 \pmod{6}$ زیرا $17-5=12$ بر $6$ بخشپذیر است. اکنون فرض کنید یک همنهشتی به فرم $a \times c \equiv b \times c \pmod{m}$ داریم. آیا میتوانیم عامل $c$ را حذف کنیم و به $a \equiv b \pmod{m}$ برسیم؟ پاسخ مثبت است، اما تنها در صورتی که $c$ و $m$ نسبت به هم اول باشند.
شرط اول بودن نسبت به پیمانه به این معناست که بزرگترین مقسومعلیه مشترک4 (ب.م.م) بین $c$ و $m$ برابر با $1$ باشد. در این شرایط میتوانیم مانند معادلههای معمولی، عامل مشترک را از دو طرف حذف کنیم، بدون آنکه تغییری در پیمانه ایجاد شود.
۲. اثبات گام به گام قاعده حذف
فرض کنیم $a \times c \equiv b \times c \pmod{m}$ و $\gcd(c,m)=1$. هدف ما رسیدن به $a \equiv b \pmod{m}$ است.
گام اول: از تعریف همنهشتی داریم:
و این اختلاف بر $m$ بخشپذیر است. یعنی:
$m \mid (a-b) \times c$
گام دوم: از آنجا که $\gcd(c,m)=1$ است، طبق قضیهٔ اقلیدس5، اگر عددی بر $m$ بخشپذیر باشد و آن عدد حاصلضرب $(a-b)$ در $c$ باشد، آنگاه $m$ باید $(a-b)$ را عاد کند. به عبارت دیگر:
گام سوم: بخشپذیری $(a-b)$ بر $m$ دقیقاً همان معنی همنهشتی $a \equiv b \pmod{m}$ است. پس حذف عامل بدون تغییر پیمانه مجاز است.
اگر شرط اول بودن برقرار نباشد، حذف عامل ممکن است پیمانه را تغییر دهد یا نتیجهٔ نادرست بدهد. مثلاً در $2 \times 3 \equiv 4 \times 3 \pmod{6}$، با اینکه $2 \times 3 = 6$ و $4 \times 3 = 12$ هر دو بر $6$ بخشپذیرند، اما $2 \equiv 4 \pmod{6}$ نادرست است (چون $2-4=-2$ بر $6$ بخشپذیر نیست). در اینجا $\gcd(3,6)=3 \neq 1$ و شرط نقض شده است.
۳. مقایسه حالتهای مجاز و غیرمجاز حذف عامل
| رابطهٔ همنهشتی | ب.م.م (عامل، پیمانه) | امکان حذف عامل |
|---|---|---|
| $4 \times 2 \equiv 1 \times 2 \pmod{3}$ | $\gcd(2,3)=1$ | مجاز |
| $5 \times 3 \equiv 2 \times 3 \pmod{4}$ | $\gcd(3,4)=1$ | مجاز |
| $6 \times 4 \equiv 2 \times 4 \pmod{8}$ | $\gcd(4,8)=4 \neq 1$ | غیرمجاز |
۴. کاربرد عملی در حل معادلههای همنهشتی
فرض کنید میخواهیم معادلهٔ $5x \equiv 15 \pmod{7}$ را حل کنیم. در اینجا پیمانه $m=7$ و عامل $c=5$ است. چون $7$ عددی اول است و $5$ بر $7$ بخشپذیر نیست، داریم $\gcd(5,7)=1$. طبق قاعدهٔ حذف، میتوانیم $5$ را از دو طرف حذف کنیم:
بدین ترتیب جواب معادله را بدون تغییر پیمانه به دست آوردیم. این روش در رمزنگاری برای یافتن کلیدهای خصوصی در الگوریتمهایی مثل آر.اس.ای بسیار کاربرد دارد.
۵. چالشهای مفهومی
پاسخ: لزوماً نتیجه همیشه نادرست نیست، اما قابل اعتماد نیست. در برخی موارد خاص ممکن است تصادفاً تساوی برقرار بماند، اما قاعده تضمینی برای درستی حذف ندارد. به همین دلیل شرط اول بودن، شرط لازم و کافی برای حذف ایمن است.
پاسخ: بله، اگر پیمانه $m$ عدد اول باشد، آنگاه هر عاملی که بر $m$ بخشپذیر نباشد با $m$ نسبت به هم اول است. بنابراین میتوان هر عاملی که مضرب پیمانه نیست را حذف کرد. این ویژگی در بسیاری از مسابقات ریاضی استفاده میشود.
پاسخ: بله. اگر $\gcd(c,m)=d \gt 1$، میتوانیم عامل را حذف کنیم، اما پیمانه به $m/d$ تبدیل میشود. به این ترتیب قاعدهٔ حذف با تغییر پیمانه داریم: $a \times c \equiv b \times c \pmod{m} \Rightarrow a \equiv b \pmod{m/d}$ که در آن $d=\gcd(c,m)$.
۶. جمعبندی
پاورقی
2 رمزنگاری (Cryptography): علم و هنر رمز کردن و رمزگشایی اطلاعات برای برقراری ارتباط امن.
3 همنهشتی (Congruence): رابطهای بین دو عدد صحیح که اختلاف آنها بر عدد ثابتی (پیمانه) بخشپذیر باشد.
4 بزرگترین مقسومعلیه مشترک (Greatest Common Divisor - GCD): بزرگترین عدد صحیحی که بر دو عدد داده شده بخشپذیر باشد.
5 قضیهٔ اقلیدس (Euclid's Lemma): اگر عدد اولی حاصلضرب دو عدد را عاد کند، حداقل یکی از آن دو عدد را عاد میکند. تعمیم آن برای اعداد نسبت به هم اول نیز صادق است.
