جواب عمومی معادله همنهشتی: نمایش همهٔ جوابها با پارامتر صحیح k
تعریف معادله همنهشتی و مفهوم جواب عمومی
معادله همنهشتی خطی به صورت زیر تعریف میشود:
در این معادله، $a$، $b$ و $m$ اعداد صحیح معلوم هستند ($m \gt 0$) و $x$ مجهول صحیح است. منظور از علامت $\equiv$ این است که $ax$ و $b$ بر $m$ باقیمانده یکسانی داشته باشند؛ یعنی $m \mid (ax - b)$.
جواب عمومی به مجموعهای از همهٔ اعداد صحیح گفته میشود که در معادله صدق میکنند. این جوابها معمولاً با استفاده از یک پارامتر صحیح $k$ (که میتواند هر عدد صحیحی باشد) به صورت یک رابطهٔ خطی نمایش داده میشوند. به عنوان مثال، در معادله $2x \equiv 4 \pmod 6$، جواب عمومی به شکل $x = 2 + 3k$ است که در آن $k$ هر عدد صحیح دلخواهی است.
برای درک بهتر، یک مثال ساده میزنیم: فرض کنید $3x \equiv 1 \pmod 5$ را میخواهیم حل کنیم. عدد $x = 2$ یک جواب است چون $3 \times 2 = 6 \equiv 1 \pmod 5$. اما جوابهای دیگری مانند $x = 7$ نیز وجود دارند. همهٔ این جوابها با الگوی $x = 2 + 5k$ به دست میآیند. در اینجا $k$ پارامتر صحیح است که هر مقدار صحیح را میتواند بگیرد.
شرط وجود جواب و تعداد جوابهای متمایز
همهٔ معادلات همنهشتی جواب ندارند. شرط لازم و کافی برای وجود جواب این است که بزرگترین مقسومعلیه مشترک $a$ و $m$ یعنی $d = \gcd(a, m)$، بر $b$ بخشپذیر باشد ($d \mid b$). اگر این شرط برقرار باشد، آنگاه معادله دقیقاً $d$ جواب متمایز به پیمانهٔ $m$ خواهد داشت. این جوابهای متمایز در بازهٔ $\{0, 1, 2, \dots, m-1\}$ قرار میگیرند.
برای نمایش همهٔ جوابها (چه متمایز و چه نامتناهی) از فرم جواب عمومی با پارامتر $k$ استفاده میکنیم. پس از یافتن یک جواب خاص مانند $x_0$، جواب عمومی به شکل زیر نوشته میشود:
توجه کنید که هرگاه $d = \gcd(a,m)$ باشد، عدد $\frac{m}{d}$ گام بین جوابهای متوالی را نشان میدهد.
| شرط | تعداد جوابهای متمایز (به پیمانهٔ m) | فرم جواب عمومی (با پارامتر k) |
|---|---|---|
| gcd(a,m) = 1 | 1 | $x = x_0 + m \cdot k$ |
| d = gcd(a,m) > 1 و d | b | d | $x = x_0 + \frac{m}{d} \cdot k$ |
| d ∤ b | 0 (بدون جواب) | —— |
روش گامبهگام یافتن جواب عمومی
برای حل یک معادله همنهشتی $ax \equiv b \pmod m$ و یافتن جواب عمومی آن، مراحل زیر را دنبال میکنیم:
گام 1: محاسبهٔ $d = \gcd(a, m)$.
گام 2: بررسی شرط $d \mid b$. اگر برقرار نبود، معادله جواب ندارد.
گام 3: تقسیم دو طرف معادله بر $d$: $\frac{a}{d} x \equiv \frac{b}{d} \pmod{\frac{m}{d}}$.
گام 4: یافتن وارون ضربی4$\frac{a}{d}$ به پیمانهٔ $\frac{m}{d}$ (چون حالا $\gcd(\frac{a}{d}, \frac{m}{d}) = 1$).
گام 5: محاسبهٔ یک جواب خاص $x_0$.
گام 6: نوشتن جواب عمومی: $x = x_0 + \frac{m}{d} \cdot k$، که $k \in \mathbb{Z}$.
برای روشنتر شدن مطلب، مثال زیر را گام به گام حل میکنیم:
مثال: معادله $6x \equiv 4 \pmod{10}$ را حل کنید.
حل: $a = 6$، $b = 4$، $m = 10$.
گام 1: $d = \gcd(6,10) = 2$.
گام 2: $2 \mid 4$، شرط برقرار است.
گام 3: تقسیم بر $2$: $3x \equiv 2 \pmod{5}$.
گام 4: وارون ضربی $3$ به پیمانهٔ $5$ برابر $2$ است چون $3 \times 2 = 6 \equiv 1 \pmod{5}$.
گام 5: $x_0 \equiv 2 \times 2 = 4 \pmod{5}$، بنابراین $x_0 = 4$ یک جواب خاص است.
گام 6: جواب عمومی: $x = 4 + \frac{10}{2} \cdot k = 4 + 5k$.
توجه: جوابهای متمایز به پیمانهٔ $10$ با قرار دادن $k = 0$ و $k = 1$ به دست میآیند: $x = 4$ و $x = 9$.
کاربرد عملی: حل معادلات دیوفانتی خطی
معادلهٔ همنهشتی $ax \equiv b \pmod m$ ارتباط نزدیکی با معادلهٔ دیوفانتی خطی $ax + my = b$ دارد. هر جواب صحیح $x$ برای معادلهٔ همنهشتی، مؤلفهٔ اول یک جواب صحیح $(x, y)$ برای معادلهٔ دیوفانتی است. بنابراین با یافتن جواب عمومی معادلهٔ همنهشتی، میتوان جواب عمومی معادلهٔ دیوفانتی را نیز نوشت.
مثال عینی: فرض کنید میخواهیم تمام جوابهای صحیح معادله $6x + 10y = 4$ را بیابیم. این معادله را به صورت همنهشتی $6x \equiv 4 \pmod{10}$ بازنویسی میکنیم که قبلاً حل کردیم و جواب عمومی $x = 4 + 5k$ به دست آمد. با جایگذاری در معادلهٔ اصلی: $6(4+5k) + 10y = 4 \Rightarrow 24+30k+10y=4 \Rightarrow 10y = -20 -30k \Rightarrow y = -2 -3k$. بنابراین همهٔ جوابهای صحیح معادلهٔ دیوفانتی به صورت $(x, y) = (4+5k, \; -2-3k)$ با $k \in \mathbb{Z}$ هستند.
چالشهای مفهومی
۱) آیا همیشه میتوان جواب عمومی را به صورت $x = x_0 + m \cdot k$ نوشت؟
خیر. این فرم فقط زمانی درست است که $\gcd(a, m) = 1$. در حالت کلی، گام بین جوابها برابر $\frac{m}{d}$ است، نه $m$. به مثال قبل توجه کنید: $x = 4 + 5k$ در حالی که $m = 10$ بود.
۲) چرا پارامتر $k$ فقط اعداد صحیح را شامل میشود؟ آیا میتواند کسری یا حقیقی باشد؟
خیر، زیرا $x$ در معادلهٔ اصلی فقط اعداد صحیح در نظر گرفته میشود (همنهشتی بر روی اعداد صحیح تعریف شده است). اگر $k$ غیرصحیح باشد، عبارت $x_0 + \frac{m}{d}k$ ممکن است صحیح نباشد و در معادله صدق نکند.
۳) چگونه میتوان مطمئن شد که فرم $x = x_0 + \frac{m}{d}k$ همهٔ جوابها را پوشش میدهد و نه فقط برخی از آنها را؟
بر اساس قضیهٔ اصلی معادلات همنهشتی، اگر $x_0$ یک جواب خاص باشد، آنگاه هر جواب دیگری به فرم $x_0 + t \cdot \frac{m}{d}$ است که $t$ صحیح است. با تغییر $k$ روی همهٔ اعداد صحیح، تمام این جوابها تولید میشوند. همچنین جوابهای متمایز به پیمانهٔ $m$ با $k = 0, 1, \dots, d-1$ به دست میآیند.
پاورقی
1 همنهشتی (Congruence): رابطهای بین دو عدد صحیح که تفاوت آنها بر عدد ثابتی بخشپذیر باشد.
2 بزرگترین مقسومعلیه مشترک (Greatest Common Divisor - GCD): بزرگترین عدد صحیحی که بر دو عدد داده شده بخشپذیر است.
3 معادلات دیوفانتی (Diophantine Equations): معادلات چندمتغیره با ضرایب صحیح که جوابهای صحیح (یا گویا) برای آنها خواسته میشود.
4 وارون ضربی (Modular Inverse): عدد صحیح $a^{-1}$ به پیمانهٔ $m$ به گونهای که $a \cdot a^{-1} \equiv 1 \pmod m$.
