معادله سیاله خطی: از مبانی تا یافتن تمام جوابهای صحیح
۱. معادله سیاله خطی چیست و چه ساختاری دارد؟
معادله سیاله خطی1 به معادلهای به شکل $ax + by = c$ گفته میشود که در آن $a$، $b$ و $c$ اعداد صحیح معلوم هستند و $x$ و $y$ متغیرهایی هستند که فقط جوابهای صحیح (مثبت، منفی یا صفر) برای آن جستجو میشود. این معادله به نام ریاضیدان یونانی، دیوفانتوس اسکندریهای2، نامگذاری شده است.
برای درک بهتر، فرض کنید میخواهیم بدانیم آیا میتوان با ترکیب خطی دو عدد صحیح $a$ و $b$، عدد $c$ را ساخت؟ پاسخ به این پرسش توسط قضیه زیر مشخص میشود:
مثال ۱: معادله $6x + 9y = 15$ را در نظر بگیرید. در اینجا $\gcd(6,9)=3$. از آنجا که $3 \mid 15$ (یعنی $15$ بر $3$ بخشپذیر است)، این معادله جواب صحیح دارد. اما معادله $6x + 9y = 14$ جواب صحیح ندارد زیرا $3 \nmid 14$.
۲. روش گامبهگام یافتن جوابهای صحیح
برای حل معادله $ax + by = c$ در اعداد صحیح، از الگوریتم اقلیدس3 استفاده میکنیم. این الگوریتم مقدار $\gcd(a,b)$ را محاسبه کرده و سپس با روش بازگشت به عقب (Extended Euclidean Algorithm) یک جواب خصوصی $(x_0, y_0)$ پیدا میشود.
مراحل عملی:
- گام ۱: تعیین $d = \gcd(a,b)$. اگر $d \nmid c$، معادله جواب صحیح ندارد.
- گام ۲: اگر $d \mid c$، دو طرف معادله را بر $d$ تقسیم کنید تا معادله $a'x + b'y = c'$ بدست آید، که در آن $\gcd(a',b')=1$.
- گام ۳: با الگوریتم اقلیدس گسترده، یک جواب خصوصی $(x_0, y_0)$ برای معادله $a'x + b'y = 1$ پیدا کنید، سپس در $c'$ ضرب کنید تا جواب معادله اصلی بدست آید.
- گام ۴: تمام جوابهای صحیح به صورت $x = x_0 + b't$ و $y = y_0 - a't$ هستند، که $t$ هر عدد صحیح دلخواه است.
ابتدا $\gcd(15,9)=3$. از آنجا که $3 \mid 6$، تقسیم میکنیم: $5x + 3y = 2$. اکنون برای $5x + 3y = 1$، با الگوریتم اقلیدس: $5 = 1\times3 + 2$، $3 = 1\times2 + 1$، $2 = 2\times1 + 0$. بازگشت به عقب: $1 = 3 - 1\times2 = 3 - 1\times(5-1\times3) = 2\times3 - 1\times5$. بنابراین $x_0' = -1$ و $y_0' = 2$ برای معادله $5x+3y=1$. حال برای معادله $5x+3y=2$ داریم: $x_0 = -1\times2 = -2$ و $y_0 = 2\times2 = 4$. بازبینی: $5(-2)+3(4) = -10+12=2$. درست است. تمام جوابها: $x = -2 + 3t$ و $y = 4 - 5t$، که $t \in \mathbb{Z}$.
۳. کاربرد عملی در مسائل روزمره
معادلات سیاله خطی در موقعیتهای واقعی مانند خرید و فروش، ترکیب سکهها و زمانبندی ظاهر میشوند. فرض کنید شخصی میخواهد با استفاده از سکههای $7$ تومانی و $5$ تومانی، دقیقاً مبلغ $31$ تومان را پرداخت کند. معادله $7x + 5y = 31$ را حل میکنیم. از آنجا که $\gcd(7,5)=1$، جواب وجود دارد. با الگوریتم اقلیدس: $7 = 1\times5 + 2$، $5 = 2\times2 + 1$. بازگشت: $1 = 5 - 2\times2 = 5 - 2\times(7-5) = 3\times5 - 2\times7$. بنابراین $x_0 = -2$ و $y_0 = 3$ برای معادله $7x+5y=1$. با ضرب در $31$: $x_0 = -62$ و $y_0 = 93$. جواب عمومی: $x = -62 + 5t$، $y = 93 - 7t$. با انتخاب $t=13$ داریم $x = 3$ و $y = 2$ (یعنی $3$ سکه $7$ تومانی و $2$ سکه $5$ تومانی).
| شرایط | تعداد جوابهای صحیح | مثال |
|---|---|---|
| $\gcd(a,b) \nmid c$ | صفر (بدون جواب) | $2x+4y=3$ |
| $\gcd(a,b) \mid c$ و $a,b$ ثابت | بیشمار (نامتناهی) | $3x+6y=9$ (با تقسیم بر $3$ میشود $x+2y=3$) |
| جستجوی جوابهای مثبت | محدود و متناهی | $x+2y=5$ با $x,y \ge 0$ جوابهای $(5,0),(3,1),(1,2)$ |
۴. چالشهای مفهومی
پاسخ: زیرا مجموعه تمام ترکیبات خطی $ax+by$ (وقتی $x,y$ اعداد صحیح هستند) دقیقاً مضربهای $\gcd(a,b)$ است. بنابراین عدد $c$ تنها زمانی قابل دستیابی است که خود مضربی از این بزرگترین مقسومعلیه مشترک باشد.
پاسخ: بله. زیرا اگر $(x_0,y_0)$ یک جواب باشد، تفاوت دو جواب $(x-x_0, y-y_0)$ در معادله همگن $a(x-x_0)+b(y-y_0)=0$ صدق میکند. از آنجا که $\frac{a}{d}$ و $\frac{b}{d}$ نسبت به هم اول هستند، نتیجه میشود $x-x_0$ مضربی از $\frac{b}{d}$ و $y-y_0$ مضربی از $-\frac{a}{d}$ است.
پاسخ: با اعمال نامساویهای $x \ge 0$ و $y \ge 0$ روی فرمول کلی. این کار بازه محدودی برای پارامتر $t$ تعیین میکند. تعداد جوابهای مثبت معمولاً متناهی است و با حل دو نامساوی خطی بر حسب $t$ به دست میآید.
جمعبندی
پاورقی
1 معادله سیاله (Diophantine Equation): معادلهای چندمتغیره با ضرایب صحیح که تنها جوابهای صحیح (یا گویا) برای آن جستجو میشود. نام آن از دیوفانتوس اسکندریه، ریاضیدان یونان باستان گرفته شده است.
2 دیوفانتوس اسکندریهای (Diophantus of Alexandria): ریاضیدان یونانی سده سوم میلادی که نخستین مطالعه سیستماتیک روی معادلات با جوابهای صحیح را انجام داد و کتاب «حساب» او سرآغاز نظریه اعداد دیوفانتینی است.
3 الگوریتم اقلیدس (Euclidean Algorithm): روشی کارآمد برای یافتن بزرگترین مقسومعلیه مشترک دو عدد صحیح با تکرار تقسیمات متوالی. نسخه گسترده آن (Extended Euclidean Algorithm) ضرایبی مثل $x$ و $y$ را نیز محاسبه میکند به طوری که $ax+by = \gcd(a,b)$.