mathematics
23rd September 2010, 08:04 PM
فرم اولیه قضیه در کتاب سان زی سوآنجینگ(孙子算经) نوشته ریاضی دان چینی سان تزو (Sun Tzu) که بعداً با عنوان ۱۲۴۷ توسط قین جیوشاو (Qin Jiushao) باز نوشت شد گنجانده شده.
فرض کنید n۱, n۲, …, nk اعداد صحیحی باشند که دو به دو نسبت به هم اولند. برای هر سری اعداد صحیح a۱,a۲, …, ak عدد صحیح x وجود دارد به طوری که در دستگاه معادلات همنهشتی زیر صدق کند:
http://upload.wikimedia.org/math/4/b/a/4ba21deba1d9581961b07463e1107eec.png
علاوه بر این تمام جوابهای x به پیمانه N = n۱n۲…nk همنهشتند. در نتیجه برای همه 1http://upload.wikimedia.org/math/9/2/b/92b68727874952b96de54cfb2c27839c.png داریم: http://upload.wikimedia.org/math/e/b/8/eb8afbf0cfba230ae1569a482d84bbc6.png اگر و تنها اگر http://upload.wikimedia.org/math/5/2/0/52003e89af842fa5bbd441682c5cdb00.png. گاهی اوقات این دستگاه حتی زمانی که همه niها دوبه دو نسبت به هم اول نیستند هم قابل حل است: جواب x وجود دارد اگر و تنها اگر:
http://upload.wikimedia.org/math/8/2/c/82c836223302ea999989259adf4cfc41.png
نمونه
پرسشی برای بدست آوردن عدد صحیح x که در دستگاه زیر صدق کند را در نظر بگیرید.
http://upload.wikimedia.org/math/1/3/9/139ebbb04538bf66cc09ae13cd719ab8.png
http://upload.wikimedia.org/math/b/3/c/b3c58532d18b8c1270eb4cdcb4e847c5.png
http://upload.wikimedia.org/math/9/9/4/994b801a574b0426e93ff5314c613247.png
با استفاده از الگوریتم اقلیدس برای ۳و ۴×۵ = ۲۰ داریم (۱۳-) × ۳ + ۲ × ۲۰ = ۱، یعنی e۱ = ۴۰ و برای ۴ و ۳×۵ = ۱۵ بدست می‌آوریم (۱۱-) × ۴ + ۳ × ۱۵ = ۱ یعنی e۲ = ۴۵. در نهایت برای ۵ و ۳×۴ = ۱۲ الگوریتم اقلیدس نتیجه می‌دهد۵ × ۵ + (۲-) × ۱۲ = ۱ به این معنا که ''e۳ = −۲۴ است. پس یکی از جوابها برای x عدد ۲ × ۴۰ + ۳ × ۴۵ + ۱ × (۲۴-) = ۱۹۱ است. تمام اعداد صحیح دیگر که به پیمانه ۳ × ۴ × ۵ = ۶۰ با ۱۹۱ همنهشتند هم جواب هستند. یعنی همه آنها با ۱۱ به پمانه ۶۰ همنهشتند.
نکته: ممکن است اعداد بدست آمده با الگوریتم اقلیدس برای eiها متفاوت باشد، اما در جواب نهایی همه مشترکند.
در این حالات تمام جوابهای x به پیمانه بزرگترین مقسوم علیه مشترک niها همنهشتند.
فرض کنید n۱, n۲, …, nk اعداد صحیحی باشند که دو به دو نسبت به هم اولند. برای هر سری اعداد صحیح a۱,a۲, …, ak عدد صحیح x وجود دارد به طوری که در دستگاه معادلات همنهشتی زیر صدق کند:
http://upload.wikimedia.org/math/4/b/a/4ba21deba1d9581961b07463e1107eec.png
علاوه بر این تمام جوابهای x به پیمانه N = n۱n۲…nk همنهشتند. در نتیجه برای همه 1http://upload.wikimedia.org/math/9/2/b/92b68727874952b96de54cfb2c27839c.png داریم: http://upload.wikimedia.org/math/e/b/8/eb8afbf0cfba230ae1569a482d84bbc6.png اگر و تنها اگر http://upload.wikimedia.org/math/5/2/0/52003e89af842fa5bbd441682c5cdb00.png. گاهی اوقات این دستگاه حتی زمانی که همه niها دوبه دو نسبت به هم اول نیستند هم قابل حل است: جواب x وجود دارد اگر و تنها اگر:
http://upload.wikimedia.org/math/8/2/c/82c836223302ea999989259adf4cfc41.png
نمونه
پرسشی برای بدست آوردن عدد صحیح x که در دستگاه زیر صدق کند را در نظر بگیرید.
http://upload.wikimedia.org/math/1/3/9/139ebbb04538bf66cc09ae13cd719ab8.png
http://upload.wikimedia.org/math/b/3/c/b3c58532d18b8c1270eb4cdcb4e847c5.png
http://upload.wikimedia.org/math/9/9/4/994b801a574b0426e93ff5314c613247.png
با استفاده از الگوریتم اقلیدس برای ۳و ۴×۵ = ۲۰ داریم (۱۳-) × ۳ + ۲ × ۲۰ = ۱، یعنی e۱ = ۴۰ و برای ۴ و ۳×۵ = ۱۵ بدست می‌آوریم (۱۱-) × ۴ + ۳ × ۱۵ = ۱ یعنی e۲ = ۴۵. در نهایت برای ۵ و ۳×۴ = ۱۲ الگوریتم اقلیدس نتیجه می‌دهد۵ × ۵ + (۲-) × ۱۲ = ۱ به این معنا که ''e۳ = −۲۴ است. پس یکی از جوابها برای x عدد ۲ × ۴۰ + ۳ × ۴۵ + ۱ × (۲۴-) = ۱۹۱ است. تمام اعداد صحیح دیگر که به پیمانه ۳ × ۴ × ۵ = ۶۰ با ۱۹۱ همنهشتند هم جواب هستند. یعنی همه آنها با ۱۱ به پمانه ۶۰ همنهشتند.
نکته: ممکن است اعداد بدست آمده با الگوریتم اقلیدس برای eiها متفاوت باشد، اما در جواب نهایی همه مشترکند.
در این حالات تمام جوابهای x به پیمانه بزرگترین مقسوم علیه مشترک niها همنهشتند.