معادله سیاله (Diophantine Equation) خطی (Linear Diophantine Equation)، در ریاضیات (Mathematics)
انواع معادلات (Equation) را در آموزش زیر شرح دادیم :
معادله سیاله (Diophantine Equation) خطی (Linear Diophantine Equation) :
🔍 تعریف: معادله سیاله خطی معادله ای به شکل
\[ ax + by = c \]است که در آن a, b, c اعداد صحیح داده شده اند و x, y متغیرهای صحیح (غالبا غیرمنفی) هستند. این معادلات از قدیمی ترین مسائل در نظریه اعداد هستند.
\[ ax + by = c \quad , \quad a, b, c \in \mathbb{Z} \]📌 ویژگی های اصلی:
شرط وجود جواب: معادله دارای جواب صحیح است اگر و فقط اگر
\[ \gcd(a, b) \]بر c بخش پذیر باشد.
جواب عمومی: اگر
\[ (x_0, y_0) \]یک جواب خاص باشد، جواب عمومی به صورت
\[ x = x_0 + \frac{b}{d} t \],
\[ y = y_0 - \frac{a}{d} t \]است که در آن
\[ d = \gcd(a, b) \]و t یک عدد صحیح دلخواه است.
جواب های غیرمنفی: با اعمال محدودیت
\[ x \ge 0, y \ge 0 \]تعداد جواب ها محدود می شود.
کاربرد: در مسائل ترکیبیاتی، رمزنگاری، و برنامه ریزی عدد صحیح.
💡 مثال های متنوع:
🔹 مثال ۱:
\[ 3x + 5y = 7 \]— gcd(3,5)=1 که 7 بر 1 بخش پذیر است. یک جواب خاص:
\[ x = -1, y = 2 \]. جواب عمومی:
\[ x = -1 + 5t, y = 2 - 3t \].
🔹 مثال ۲:
\[ 2x + 4y = 5 \]— gcd(2,4)=2، اما 5 بر 2 بخش پذیر نیست. پس جواب صحیح ندارد.
🔹 مثال ۳:
\[ 6x + 9y = 15 \]— gcd=3، 15/3=5، جواب دارد. با تقسیم بر 3:
\[ 2x + 3y = 5 \].
🔹 مثال ۴ (مسئله سکه): با سکه های ۲ و ۵ تومانی، چه مقادیری را می توان پرداخت؟ معادله
\[ 2x + 5y = n \].
🌍 کاربردها: رمزنگاری (تجزیه اعداد)، برنامه ریزی عدد صحیح، مسائل ترکیبیاتی (مانند شمارش روش های ترکیب سکه ها)، و حل معادلات سیاله در نظریه اعداد.
📝 نکته جالب: معادلات سیاله به نام دیوفانتوس اسکندرانی، ریاضیدان یونان باستان، نامگذاری شده اند. کتاب او "Arithmetica" مجموعه ای از مسائل در این زمینه است.
🧮 الگوریتم اقلیدس: برای یافتن یک جواب خاص
\[ (x_0, y_0) \]از الگوریتم اقلیدس برای یافتن gcd(a,b) و سپس به دست آوردن ضرایب (با استفاده از الگوریتم اقلیدس توسعه یافته) استفاده می شود.
⚠️ نکته: تعداد جواب های صحیح غیرمنفی با محدودیت x,y ≥ 0 ممکن است صفر، یک یا متناهی باشد. برای معادله
\[ ax + by = n \]با a,b مثبت، تعداد جواب ها تقریبا
\[ \frac{n}{ab} \]است.
📈 مسئله سکه فراست: بزرگترین عددی که با سکه های a و b (با gcd(a,b)=1) نمی توان ساخت،
\[ ab - a - b \]است (قضیه فراست).
🔬 مثال عددی: با سکه های ۳ و ۵، مقادیر 1,2,4,7 را نمی توان ساخت. بزرگترین مقدار غیرقابل ساخت
\[ 3\times5 - 3 - 5 = 7 \]است.
