شرط وجود جواب صحیح در معادلهٔ $ax + by = c$
۱. آشنایی با معادلهٔ $ax + by = c$ و جواب صحیح
معادلهٔ $ax + by = c$ که در آن $a,b,c$ اعداد صحیح ثابت و $x,y$ متغیرهای صحیح هستند، یک معادلهٔ دیوفانتی خطی نامیده میشود. برخلاف معادلات معمولی که در اعداد حقیقی جوابهای بیشماره دارند، در اینجا فقط به دنبال جفتهای صحیح ($x,y$) هستیم که در معادله صدق کنند.
به عنوان مثال، معادلهٔ $2x + 3y = 1$ را در نظر بگیرید. با کمی آزمون و خطا میتوان جواب $x = 2$ و $y = -1$ را یافت زیرا $2(2) + 3(-1) = 4 - 3 = 1$. اما آیا معادلهٔ $2x + 4y = 3$ جواب صحیح دارد؟ سمت چپ معادله همیشه زوج است، در حالی که سمت راست عددی فرد ($3$) میباشد. بنابراین جواب صحیحی وجود ندارد. این مشاهدات ما را به سمت یک شرط کلی هدایت میکند.
۲. نقش بزرگترین مقسومعلیه مشترک ($\gcd(a,b)$)
بزرگترین مقسومعلیه مشترک دو عدد صحیح $a$ و $b$ که با نماد $\gcd(a,b)$ نشان داده میشود، بزرگترین عدد صحیح مثبتی است که هم $a$ و هم $b$ بر آن بخشپذیر هستند.
نکتهٔ کلیدی این است: برای هر دو عدد صحیح $a$ و $b$ که هر دو صفر نیستند، مقادیری که ترکیب خطی $ax + by$ (با $x,y$ صحیح) میتواند تولید کند، دقیقاً مضربهای صحیح $\gcd(a,b)$ هستند. به عبارت دیگر، مجموعهٔ $\{ ax + by \mid x,y \in \mathbb{Z} \}$ برابر است با $\{ k \cdot \gcd(a,b) \mid k \in \mathbb{Z} \}$.
۳. شرط وجود جواب (قضیه اصلی)
قضیه: معادلهٔ دیوفانتی خطی $ax + by = c$ دارای جواب صحیح است اگر و تنها اگر $\gcd(a,b)$ بر $c$ بخشپذیر باشد. به زبان ریاضی:
علامت $\mid$ به معنای «تقسیم میکند» است. یعنی $\gcd(a,b)$ باید عیناً $c$ را بدون باقیمانده تقسیم کند.
۴. گامهای عملی برای بررسی شرط
برای تعیین اینکه آیا معادلهٔ $ax + by = c$ جواب صحیح دارد یا خیر، به ترتیب زیر عمل کنید:
- گام اول: بزرگترین مقسومعلیه مشترک $a$ و $b$ را محاسبه کنید ($d = \gcd(a,b)$). میتوانید از الگوریتم اقلیدس3 استفاده کنید.
- گام دوم: بررسی کنید که آیا $d$ بر $c$ بخشپذیر است یا خیر (یعنی $c \div d$ یک عدد صحیح باشد).
- گام سوم: اگر شرط برقرار بود، معادله جواب صحیح دارد. در غیر این صورت، هیچ جواب صحیحی وجود نخواهد داشت.
در صورت وجود جواب، میتوان با استفاده از الگوریتم اقلیدس گسترشیافته یک جواب خاص پیدا کرد و سپس همهٔ جوابها را به صورت پارامتری نوشت.
۵. جدول مقایسهٔ وضعیت جوابها بر اساس مقدار $\gcd(a,b)$ و $c$
| معادله | $\gcd(a,b)$ | آیا $\gcd(a,b) \mid c$ ؟ | وضعیت جواب صحیح |
|---|---|---|---|
| $3x + 6y = 9$ | $3$ | بله ($3 \mid 9$) | دارد |
| $4x + 10y = 7$ | $2$ | خیر ($2 \nmid 7$) | ندارد |
| $5x + 9y = 1$ | $1$ | بله ($1 \mid 1$) | دارد |
| $6x - 15y = 10$ | $3$ | خیر ($3 \nmid 10$) | ندارد |
۶. کاربرد عملی: مسئلهٔ تمبر و پست
فرض کنید میخواهیم با استفاده از تمبرهای $4$ تومانی و $7$ تومانی، هزینهٔ پستی معادل $c$ تومان را دقیقاً بپردازیم. معادلهٔ $4x + 7y = c$ را داریم. بزرگترین مقسومعلیه مشترک $4$ و $7$ برابر $1$ است. از آنجا که $1$ هر عدد صحیحی را تقسیم میکند، برای هر مقدار صحیح $c$ جواب صحیح وجود دارد. اما اگر تمبرها به جای آن $6$ و $9$ تومانی بودند، $\gcd(6,9)=3$ میشد و تنها هزینههایی قابل پرداخت بودند که مضربی از $3$ باشند. بنابراین با تمبرهای $6$ و $9$ تومانی هرگز نمیتوان هزینهٔ $10$ تومان را دقیقاً پرداخت کرد، زیرا $3 \nmid 10$.
۷. چالشهای مفهومی
پاسخ: وقتی $\gcd(a,b)=1$، این عدد $1$ همیشه بر هر $c$ صحیحی بخشپذیر است. بنابراین معادله برای هر مقدار صحیح $c$ حداقل یک جواب صحیح دارد. این حالت خاص و بسیار مهمی است.
پاسخ: خیر. شرط $\gcd(a,b) \mid c$ هم لازم و هم کافی است. چون $3 \mid 15$، حتماً جواب صحیح وجود دارد. یک جواب خاص $x = 5$ و $y = \frac{30-15}{-9}?$ در واقع با حل دقیق: $6x - 9y = 15 \implies 2x - 3y = 5$ که جوابهایی مانند $x=4, y=1$ دارد.
پاسخ: اگر $(x_0, y_0)$ یک جواب خاص باشد، آنگاه برای هر $t \in \mathbb{Z}$، جواب عمومی به صورت $x = x_0 + \frac{b}{d}t$ و $y = y_0 - \frac{a}{d}t$ است که در آن $d = \gcd(a,b)$. بنابراین تعداد جوابهای صحیح نامحدود است (بیشماره).
۸. جمعبندی
۹. پاورقی
1 معادله دیوفانتی (Diophantine equation): معادلهای چندمتغیره با ضرایب صحیح که جوابهای آن فقط در مجموعه اعداد صحیح جستجو میشوند.2 قضیه بزو (Bézout's identity): به ازای هر دو عدد صحیح $a$ و $b$، اعداد صحیح $x$ و $y$ وجود دارند که $ax + by = \gcd(a,b)$.
3 الگوریتم اقلیدس (Euclidean algorithm): روشی کارا برای محاسبهٔ بزرگترین مقسومعلیه مشترک دو عدد از طریق تقسیمهای متوالی و استفاده از باقیماندهها.