معادله سیاله خطی؛ شرط وجود و جوابهای صحیح
آموزش حل ax+by=c در اعداد صحیح با ب.م.م، الگوریتم اقلیدس و نوشتن خانواده کامل جوابها.
پاسخ کوتاه
در معادله سیاله، جوابها باید صحیح باشند؛ بنابراین حل حقیقی یک خط کافی نیست. ب.م.م ضرایب تعیین میکند آیا اصلاً جواب صحیح وجود دارد و پس از یافتن یک جواب، یک پارامتر صحیح همه جوابها را تولید میکند.
شرط وجود جواب
معادله ax+by=c جواب صحیح دارد اگر و تنها اگر d=gcd(a,b) عدد c را تقسیم کند. اگر این شرط برقرار نباشد، هیچ جفت صحیحی وجود ندارد. دلیل آن این است که هر ترکیب صحیح ax+by مضربی از d است.
سادهسازی معادله
وقتی d مقسومعلیه c است، هر سه ضریب را بر d تقسیم کن تا ضرایب x و y نسبت به هم اول شوند. این کار عددها را کوچکتر میکند و نوشتن جواب عمومی را آسانتر میسازد، بدون آنکه جوابهای صحیح تغییر کنند.
یافتن یک جواب
با الگوریتم اقلیدس توسعهیافته میتوان d را به صورت au+bv نوشت. با ضرب این رابطه در c/d، یک جواب ویژه x0=u(c/d) و y0=v(c/d) ساخته میشود. گاهی آزمون چند مقدار کوچک سریعتر است.
خانواده جوابها
اگر (x0,y0) یک جواب و d=gcd(a,b) باشد، همه جوابها x=x0+(b/d)t و y=y0-(a/d)t هستند که t عدد صحیح است. علامتهای دو تغییر مخالفاند تا مقدار ax+by ثابت بماند.
مثال و تست کوتاه
برای 6x+9y=3، ب.م.م برابر 3 و شرط وجود برقرار است. یک جواب x0=-1 و y0=1 است. همه جوابها x=-1+3t و y=1-2t برای t صحیحاند؛ جایگذاری جملههای وابسته به t را حذف میکند.
چکلیست حل تست
- ابتدا بررسی کن gcd(a,b) عدد c را تقسیم میکند.
- یک جواب ویژه برای ساخت همه جوابها کافی است.
- پارامتر خانواده جوابها باید عدد صحیح باشد.