همنهشتی (همنهشتی): قلب حساب پیمانهای در اعداد صحیح
۱. تعریف بنیادین همنهشتی و پیمانه
فرض کنید $m$ یک عدد صحیح بزرگتر از $1$ باشد. میگوییم دو عدد صحیح $a$ و $b$ نسبت به پیمانهٔ $m$همنهشت هستند هرگاه تفاضل $a-b$ بر $m$ بخشپذیر باشد. به عبارت دیگر:
علامت $\equiv$ و عبارت $\pmod{m}$ را نخستین بار کارل فریدریش گاوس در کتاب «پژوهشهای حسابی» معرفی کرد. عدد $m$ را پیمانه مینامیم. برای نمونه، $17 \equiv 5 \pmod{4}$ چون $17-5=12$ بر $4$ بخشپذیر است. همچنین $-3 \equiv 9 \pmod{6}$ زیرا $-3-9=-12$ بر $6$ بخشپذیر است (توجه کنید که بخشپذیری شامل اعداد منفی نیز میشود).
یک راه ساده برای درک همنهشتی: دو عدد بر پیمانهٔ $m$ همنهشتند اگر باقیماندهٔ تقسیم آنها بر $m$ یکسان باشد. زیرا میدانیم هر عدد صحیح را میتوان به شکل $a = m \cdot q + r$ با $0 \le r \lt m$ نوشت. در این صورت، $a \equiv r \pmod{m}$.
مثال عملی: فرض کنید ساعت دیواری را در نظر بگیرید که پیمانهٔ آن $12$ است. ساعت $15$ همان $3$ را نشان میدهد. مینویسیم $15 \equiv 3 \pmod{12}$. اگر $7$ ساعت بعد از $10$ را محاسبه کنیم: $10+7=17$ و $17 \equiv 5 \pmod{12}$، یعنی ساعت $5$ را نشان میدهد.
۲. ویژگیهای اصلی رابطهٔ همنهشتی
رابطهٔ همنهشتی با پیمانهٔ ثابت $m$ یک رابطهٔ همارزی است، یعنی سه ویژگی زیر را دارد:
- بازتابی: برای هر عدد صحیح $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$ است و هر کلاس شامل اعدادی با باقیماندهٔ یکسان است.
| ویژگی | در رابطهٔ تساوی (=) | در رابطهٔ همنهشتی ($\equiv$) |
|---|---|---|
| بازتابی | $a=a$ | $a \equiv a$ |
| تقارنی | $a=b \Rightarrow b=a$ | $a \equiv b \Rightarrow b \equiv a$ |
| تعدی | $a=b , b=c \Rightarrow a=c$ | $a \equiv b , b \equiv c \Rightarrow a \equiv c$ |
۳. عملیات حسابی با همنهشتیها
یکی از قوتهای حساب پیمانهای این است که میتوانیم همنهشتیها را مانند معادلهها جمع، تفریق و ضرب کنیم. اگر $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}$
بهویژه، اگر $a \equiv b \pmod{m}$، آنگاه برای هر عدد طبیعی $k$ داریم $a^k \equiv b^k \pmod{m}$. این ویژگی ساده به ما امکان میدهد رقم یکان توانهای بزرگ یا باقیماندهٔ تقسیم اعداد بسیار بزرگ را به دست آوریم.
اما در مورد تقسیم باید احتیاط کرد. به طور کلی نمیتوان دو طرف همنهشتی را بر یک عدد دلخواه تقسیم کرد، مگر آنکه آن عدد با پیمانه نسبت به هم اول باشد. اگر $\gcd(c,m)=1$ و $a \times c \equiv b \times c \pmod{m}$ آنگاه $a \equiv b \pmod{m}$.
۴. کاربرد عملی: کد شابک (ISBN) و تشخیص خطا
یکی از کاربردهای جالب همنهشتی در کد بینالمللی کتاب (ISBN)1 است. در نسخهٔ $13$ رقمی شابک، یک رقم کنترلی در انتها قرار دارد که از رابطهٔ زیر محاسبه میشود:
۵. چالشهای مفهومی (پرسش و پاسخ)
پرسش ۱: آیا میتوان دو طرف یک همنهشتی را بر یک عدد بخش کرد؟ مثلاً از $8 \equiv 2 \pmod{6}$ نتیجه گرفت $4 \equiv 1 \pmod{3}$؟
پاسخ: بله، اما باید هم پیمانه را تقسیم کنیم. قاعدهٔ دقیق: اگر $c \neq 0$ و $c \mid a, c \mid b, c \mid m$ آنگاه از $a \equiv b \pmod{m}$ نتیجه میشود $\frac{a}{c} \equiv \frac{b}{c} \pmod{\frac{m}{c}}$. در مثال شما، $c=2$ است و چون $2$ هر سه عدد $8, 2, 6$ را تقسیم میکند، داریم $4 \equiv 1 \pmod{3}$ که درست است.
پرسش ۲: چرا نمیتوانیم همنهشتی $2x \equiv 4 \pmod{6}$ را به $x \equiv 2 \pmod{3}$ ساده کنیم؟
پاسخ: چون $\gcd(2,6)=2 \neq 1$. در چنین حالتی، پس از تقسیم بر $2$، پیمانه نیز باید بر $2$ تقسیم شود: $x \equiv 2 \pmod{3}$. اما دقت کنید که جوابهای معادلهٔ اصلی در پیمانهٔ $6$ عبارتند از $x \equiv 2, 5 \pmod{6}$ که هردو با $x \equiv 2 \pmod{3}$ سازگارند.
پرسش ۳: آیا همنهشتی برای اعداد منفی معنی دارد؟ مثلاً $-7 \equiv ? \pmod{5}$
پاسخ: کاملاً. $-7 \equiv 3 \pmod{5}$ چون $-7-3 = -10$ بر $5$ بخشپذیر است. به طور کلی هر عدد صحیح منفی با باقیماندهٔ نامنفی معادل خود (با جمع مضربی از پیمانه) همنهشت است.
۶. حل معادلات دیوفانتی خطی با همنهشتی
معادلهٔ دیوفانتی2 خطی به شکل $ax + by = c$ که در آن $a,b,c$ اعداد صحیح هستند، با استفاده از همنهشتی قابل حل است. کافی است معادله را به صورت $ax \equiv c \pmod{b}$ بازنویسی کنیم (یا برعکس). این معادله جواب دارد اگر و تنها اگر $\gcd(a,b) \mid c$. سپس با یافتن وارون ضربی3$a$ نسبت به پیمانهٔ $b$ (در صورت موجود بودن) میتوان جواب خاص را به دست آورد.
پاورقی
1 شابک (ISBN): مخفف International Standard Book Number، یک شناسهٔ منحصربهفرد برای کتابها که شامل رقم کنترلی برای تشخیص خطا است.
2 معادله دیوفانتی (Diophantine Equation): معادلهای چندمتغیره با ضرایب صحیح که جوابهای صحیح (یا گاهی گویا) برای آن جستجو میشود.
3 وارون ضربی (Modular Inverse): عدد صحیح $a^{-1}$ به گونهای که $a \times a^{-1} \equiv 1 \pmod{m}$. این عدد وجود دارد اگر و تنها اگر $\gcd(a,m)=1$.