تبدیل معادله سیاله به همنهشتی: از ax + by = c تا ax ≡ c (mod |b|)
1. معادله سیاله چیست و چرا به همنهشتی نیاز داریم؟
معادله سیاله (یا دیوفانتی1) خطی به فرم $ax + by = c$ که در آن $a,b,c$ اعداد صحیح معلوم و $x,y$ مجهولهای صحیح هستند، یکی از مباحث پایهای در نظریه اعداد است. پیدا کردن جوابهای صحیح چنین معادلهای همیشه ممکن نیست. شرط اصلی وجود جواب، این است که $\gcd(a,b)$ (بزرگترین مقسومعلیه مشترک) باید $c$ را عاد کند.
اما گاهی به جای جستجوی هر دو مجهول $x$ و $y$، میتوانیم معادله را به شکلی بازنویسی کنیم که فقط یک مجهول داشته باشیم. این کار با استفاده از مفهوم همنهشتی2 انجام میشود. ایده اصلی: عبارت $by$ را به طرف دیگر میبریم و از بخشپذیری بر $b$ استفاده میکنیم.
2. تبدیل گامبهگام: از معادله تا همنهشتی
فرض کنید معادله $3x + 5y = 7$ را داریم. میخواهیم آن را به همنهشتی $3x \equiv 7 \pmod{5}$ تبدیل کنیم. مراحل زیر را طی میکنیم:
- گام اول: عبارت شامل $y$ را به یک سمت ببرید: $3x - 7 = -5y$.
- گام دوم: توجه کنید که سمت راست یعنی $-5y$ همیشه بر $5$ بخشپذیر است. پس $3x - 7$ نیز باید بر $5$ بخشپذیر باشد.
- گام سوم: بنویسید $5 \mid (3x - 7)$ که یعنی $3x \equiv 7 \pmod{5}$.
- گام چهارم (اختیاری): در صورت نیاز، همنهشتی را ساده کنید. مثلاً $7 \equiv 2 \pmod{5}$، پس $3x \equiv 2 \pmod{5}$.
اگر ضریب $b$ منفی باشد، مثلاً معادله $2x - 3y = 4$، آنگاه $|b| = 3$ را در همنهشتی استفاده میکنیم: $2x \equiv 4 \pmod{3}$ که پس از سادهسازی به $2x \equiv 1 \pmod{3}$ تبدیل میشود.
3. جدول مقایسه: معادله اصلی در برابر همنهشتی معادل
| معادله دیوفانتی | همنهشتی معادل (پیمانه |b|) | شرط وجود جواب صحیح |
|---|---|---|
| $4x + 6y = 10$ | $4x \equiv 10 \pmod{6}$ یا $4x \equiv 4 \pmod{6}$ | $\gcd(4,6)=2$ و $2|10$ دارد |
| $5x - 2y = 3$ | $5x \equiv 3 \pmod{2}$ که ساده میشود به $x \equiv 1 \pmod{2}$ | $\gcd(5,-2)=1$ همیشه برقرار است |
| $3x + 0y = 9$ | $3x \equiv 9 \pmod{0}$ (تعریف نشده) – باید جداگانه بررسی شود | حالت خاص |
در معادله $3x + 0y = 9$، ضریب $b$ صفر است و روش تبدیل به همنهشتی کاربرد ندارد. در این حالت به سادگی $x = 3$ و $y$ هر عدد صحیح خواهد بود.
4. کاربرد عملی: حل یک معادله با استفاده از همنهشتی
فرض کنید میخواهیم جوابهای صحیح معادله $7x + 9y = 5$ را پیدا کنیم. طبق روش، ابتدا همنهشتی زیر را مینویسیم:
حال $7$ را به صورت وارون ضربی3 در پیمانه $9$ پیدا میکنیم. از آنجا که $7 \times 4 = 28 \equiv 1 \pmod{9}$، وارون $7$ برابر $4$ است. پس دو طرف همنهشتی را در $4$ ضرب میکنیم:
بنابراین $x = 2 + 9k$ به ازای $k \in \mathbb{Z}$. حال این $x$ را در معادله اصلی قرار میدهیم تا $y$ را بیابیم:
پاسخ کلی: $(x, y) = (2+9k, -1-7k)$ که با قراردادن هر عدد صحیح به جای $k$ جوابهای بیشمارهای به دست میآید.
5. چالشهای مفهومی
چالش ۱: آیا همیشه میتوانیم معادله $ax+by=c$ را به $ax \equiv c \pmod{|b|}$ تبدیل کنیم، حتی اگر $b$ صفر باشد؟
خیر. اگر $b=0$، معادله به شکل $ax = c$ در میآید و مفهوم همنهشتی بر پیمانه صفر تعریف نشده است. در این صورت معادله مستقیماً حل میشود و $y$ آزاد خواهد بود (در صورتی که $a|c$).
چالش ۲: چرا در همنهشتی نهایی از $|b|$ استفاده میکنیم نه خود $b$؟
زیرا تعریف همنهشتی میگوید: $m \mid (a-b)$ اگر و تنها اگر $a \equiv b \pmod{m}$. از آنجا که بخشپذیری به علامت مقسومعلیه حساس نیست ($m \mid n$ یعنی $|m| \mid n$)، میتوانیم پیمانه را مثبت در نظر بگیریم تا از ابهام جلوگیری کنیم. در اغلب کتابها، پیمانه را عددی مثبت فرض میکنند.
چالش ۳: اگر $\gcd(a,b)$ مقسومعلیه $c$ نباشد، همنهشتی چه شکلی پیدا میکند؟
اگر $d = \gcd(a,b)$ و $d \nmid c$، معادله اصلی جواب صحیح ندارد. در این حالت، همنهشتی $ax \equiv c \pmod{|b|}$ نیز بیجواب خواهد بود زیرا اگر این همنهشتی جواب داشت، آنگاه $b \mid (ax-c)$ میشد و در نتیجه $d \mid (ax-c)$. از طرفی $d \mid a$ و $d \mid b$، پس $d \mid ax$ و در نتیجه $d \mid c$ که تناقض است. بنابراین شرط $d|c$ هم برای معادله اصلی و هم برای همنهشتی معادل ضروری است.
6. جمعبندی
پاورقی
1 معادله دیوفانتی (Diophantine equation): معادلهای چندمتغیره با ضرایب صحیح که جوابهای صحیح (یا گویا) برای آن جستجو میشود.
2 همنهشتی (Congruence): رابطهای بین دو عدد صحیح که تفاوت آنها بر عدد ثابتی (پیمانه) بخشپذیر باشد؛ نوشته میشود $a \equiv b \pmod{m}$.
3 وارون ضربی (Modular multiplicative inverse): عدد صحیح $a^{-1}$ در پیمانه $m$ به گونهای که $a \cdot a^{-1} \equiv 1 \pmod{m}$، در صورتی که $\gcd(a,m)=1$.