شرط وجود جواب در همنهشتی خطی: معادلهٔ $ax \equiv b \pmod{m}$ هنگامی جواب دارد که $\gcd(a,m) \mid b$
۱. تعریف همنهشتی خطی و مسئلهٔ وجود جواب
همنهشتی خطی به معادلهای از شکل $ax \equiv b \pmod{m}$ گفته میشود که در آن $a$، $b$ و $m$ ($m \gt 0$) اعداد صحیح هستند و $x$ مجهول صحیح است. عبارت $ax \equiv b \pmod{m}$ به این معناست که $m$ تفاوت $ax$ و $b$ را عاد میکند؛ یعنی $m \mid (ax - b)$.
سؤال اساسی این است: برای چه مقادیری از $a$، $b$ و $m$ این معادله دستکم یک جواب صحیح دارد؟ پاسخ را قضیهٔ زیر میدهد.
مفهوم کلیدی: ب.م.م مجموع اطلاعات مربوط به رابطهٔ $a$ و پیمانه $m$ را در خود دارد. اگر این مقدار، $b$ را عاد نکند، هیچ عدد صحیحی نمیتواند همنهشتی را برقرار کند.
۲. اثبات شهودی شرط با استفاده از ترکیب خطی
فرض کنید $d = \gcd(a,m)$. میدانیم اعداد صحیحی مانند $u$ و $v$ وجود دارند به طوری که $au + mv = d$ (قضیهٔ بزو4). حال اگر $d \mid b$، یعنی $b = d \cdot k$ برای یک عدد صحیح $k$. با ضرب کردن رابطهٔ بزو در $k$ داریم:
$a(uk) + m(vk) = dk = b$
از این رو $a(uk) = b - m(vk)$، یعنی $a(uk) \equiv b \pmod{m}$. بنابراین $x_0 = uk$ یک جواب خاص است. برعکس، اگر جوابی مثل $x_0$ وجود داشته باشد، آنگاه $ax_0 - b = mq$ برای یک $q$. از آنجا که $d \mid a$ و $d \mid m$، نتیجه میشود $d \mid (ax_0 - mq) = b$. به این ترتیب شرط $d \mid b$ هم لازم و هم کافی است.
مثال عملی: معادلهٔ $6x \equiv 4 \pmod{10}$ را در نظر بگیرید. در اینجا $a=6$، $m=10$ و $b=4$. مقدار $d = \gcd(6,10) = 2$. از آنجا که $2 \mid 4$ شرط برقرار است، پس جواب دارد (مثلاً $x=4$ چون $6 \times 4 = 24 \equiv 4 \pmod{10}$). اما معادلهٔ $6x \equiv 3 \pmod{10}$ جواب ندارد زیرا $2 \nmid 3$.
۳. جدول مقایسهٔ حالتهای مختلف (وجود یا عدم وجود جواب)
| معادله (مثال) | $d = \gcd(a,m)$ | شرط $d \mid b$ | تعداد جوابها (پیمانهٔ $m$) |
|---|---|---|---|
| $3x \equiv 6 \pmod{9}$ | $\gcd(3,9)=3$ | برقرار است (3|6) | $3$ جواب |
| $4x \equiv 5 \pmod{8}$ | $\gcd(4,8)=4$ | برقرار نیست (4∤5) | هیچ جوابی |
| $2x \equiv 0 \pmod{6}$ | $\gcd(2,6)=2$ | برقرار است (2|0) | $2$ جواب |
توجه داشته باشید که «تعداد جوابها» منظور جوابهای ناهمنهشت (یعنی متمایز به پیمانهٔ $m$) است. اگر شرط برقرار باشد، دقیقاً $d$ جواب در بازهٔ $\{0,1,\dots,m-1\}$ وجود خواهد داشت.
۴. روش گامبهگام یافتن جوابها در حالت کلی
وقتی شرط $d \mid b$ برقرار شد، برای یافتن جوابهای معادلهٔ $ax \equiv b \pmod{m}$ مراحل زیر را طی میکنیم:
- گام اول: محاسبهٔ $d = \gcd(a,m)$ و اطمینان از اینکه $d \mid b$.
- گام دوم: تقسیم سه عدد $a$، $b$ و $m$ بر $d$ تا به یک معادلهٔ سادهتر برسیم:
$a' = a/d$، $b' = b/d$، $m' = m/d$. اکنون $\gcd(a',m') = 1$. - گام سوم: حل معادلهٔ $a' x \equiv b' \pmod{m'}$. چون وارون ضربی5$a'$ به پیمانهٔ $m'$ وجود دارد، میتوان $x_0 \equiv (a')^{-1} \cdot b' \pmod{m'}$ را یافت.
- گام چهارم: جوابهای اصلی به صورت $x \equiv x_0 + k \cdot m' \pmod{m}$ برای $k = 0, 1, \dots, d-1$ هستند.
مثال گامبهگام: معادلهٔ $18x \equiv 12 \pmod{30}$ را حل کنید. $d = \gcd(18,30)=6$ و $6 \mid 12$ پس شرط برقرار است. تقسیم بر ۶: $a'=3$، $b'=2$، $m'=5$. معادلهٔ جدید: $3x \equiv 2 \pmod{5}$. وارون ۳ به پیمانهٔ ۵ برابر با ۲ است ($3 \times 2 = 6 \equiv 1 \pmod{5}$). بنابراین $x_0 \equiv 2 \times 2 = 4 \pmod{5}$. جوابهای اصلی: $x \equiv 4 + k \cdot 5 \pmod{30}$ برای $k=0,1,2,3,4,5$ (چون $d=6$). یعنی جوابها: $4, 9, 14, 19, 24, 29$ پیمانهٔ ۳۰.
۵. کاربرد عملی در رمزنگاری و کدهای تشخیص خطا
شرط وجود جواب معادلات همنهشتی در الگوریتمهای رمزنگاری مانند آراسای (RSA) نقشی اساسی دارد. در مرحلهٔ رمزگشایی باید معادلهٔ $ed \equiv 1 \pmod{\phi(n)}$ حل شود که در آن $d$ تنها زمانی وجود دارد که $\gcd(e, \phi(n)) = 1$ (یعنی شرط $1 \mid 1$ بدیهی است). همچنین در محاسبات مربوط به چکسامانه6 و کدهای خودپالا (self-checking codes) از معادلات همنهشتی برای تشخیص و تصحیح خطا استفاده میشود. به عنوان یک مثال ساده، در سامانهٔ شناسایی رقم خطا در شمارهٔ حساب بانکی، از همنهشتی خطی با پیمانهٔ $m$ خاص استفاده میشود و قابلیت حل بودن معادله تضمین میکند که الگوریتم صحیح عمل کند.
کاربرد دیگر در تقسیم عادلانهٔ منابع (fair division) است. فرض کنید میخواهیم $b$ شیء را بین $a$ نفر به گونهای تقسیم کنیم که پس از برداشتن مداوم پیمانهٔ $m$ دستنوشتهای باقی نماند. شرط $\gcd(a,m) \mid b$ نشان میدهد که آیا این تقسیمبندی بدون باقیماندهٔ ناهماهنگ شدنی است یا خیر.
۶. چالشهای مفهومی (پرسش و پاسخ)
پرسش ۱: آیا شرط $(a,m) \mid b$ برای هر معادلهٔ همنهشتی الزامی است؟ حتی وقتی $m$ عدد اول باشد؟
پاسخ: بله، این شرط همیشه برقرار است. وقتی $m$ اول باشد، دو حالت داریم: یا $a$ مضرب $m$ نیست که در این صورت $\gcd(a,m)=1$ و شرط $1 \mid b$ همیشه برقرار است (هر معادله جواب دارد). یا $a$ مضرب $m$ است که در آن صورت $d=m$ و شرط میشود $m \mid b$. اگر $b$ مضرب $m$ نباشد، جوابی وجود ندارد که با شهود سازگار است (سمت چپ مضرب $m$ ولی سمت راست نه).
پرسش ۲: اگر شرط برقرار باشد، چگونه میتوانیم بگوییم دقیقاً $d$ جواب وجود دارد؟ مگر جوابها بیشمار نیستند؟
پاسخ: اگر تمام اعداد صحیح را در نظر بگیریم، بیشمار جواب وجود دارد (چون اگر $x_0$ جواب باشد، $x_0 + m$ نیز جواب است). اما منظور از «تعداد جوابها» در نظریهٔ اعداد، تعداد جوابهای ناهمنهشت (یافت شده در بازهٔ $0,1,\dots,m-1$) است. با این تعریف دقیقاً $d$ جواب متمایز (به پیمانهٔ $m$) داریم.
پرسش ۳: چرا در شرط وجود جواب از $\gcd(a,m)$ استفاده میشود نه چیز دیگر مانند $\gcd(a,b)$؟
پاسخ: به دلیل ساختار معادله. در واقع معادلهٔ $ax \equiv b \pmod{m}$ معادل معادلهٔ دیوفانتی7$ax - my = b$ است. این معادله طبق قضیهٔ بزو جواب دارد اگر و فقط اگر $\gcd(a,m) \mid b$. نقش $\gcd(a,b)$ در اینجا تعیین کننده نیست؛ بلکه ارتباط $a$ و $m$ مهم است، زیرا پیمانه مقسومعلیه اختلاف $ax$ و $b$ میشود.
پاورقی
1 همنهشتی (Congruence): دو عدد صحیح $a$ و $b$ به پیمانهٔ $m$ همنهشت نامیده میشوند اگر $m$ اختلاف آنها را عاد کند، یعنی $m \mid (a-b)$.
2 بزرگترین مقسومعلیه مشترک (Greatest Common Divisor - gcd): بزرگترین عدد صحیح مثبتی که هر دو عدد داده شده بر آن بخشپذیر باشند.
3 پیمانه (Modulus): عدد صحیح مثبتی که مبنای مقایسه در همنهشتی قرار میگیرد و معمولاً با $m$ نمایش داده میشود.
4 قضیهٔ بزو (Bézout's identity): برای هر دو عدد صحیح $a$ و $b$ اعداد صحیحی مانند $u$ و $v$ وجود دارند که $au + bv = \gcd(a,b)$.
5 وارون ضربی (Modular Inverse): عدد صحیح $a^{-1}$ به پیمانهٔ $m$ به گونهای که $a \cdot a^{-1} \equiv 1 \pmod{m}$. وارون تنها زمانی وجود دارد که $\gcd(a,m)=1$.
6 چکسامانه (Checksum): مقداری محاسباتی که برای تشخیص خطا در انتقال داده استفاده میشود و اغلب از معادلات همنهشتی به دست میآید.
7 معادلهٔ دیوفانتی (Diophantine equation): معادلهای با ضرایب صحیح که جوابهای صحیح (یا گاهی طبیعی) برای آن خواسته میشود.