کوچک‌ترین مضرب مشترک

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

فرض کنید a_1,a_2,...,a_n اعدادی صحیح و نا صفر باشند. عدد صحیح k را مضرب مشترکی از a_1,a_2,...,a_n می‌نامیم، به شرطی که k همه‌ی a_1 تا a_n را بشمارد.

مثلاً اگر t عددی صحیح باشد t.a_1.a_2...a_n مضرب مشترکی از a_1,a_2,...,a_n است؛ بنابراین، تعداد مضرب‌های مشترک a_1,a_2,...,a_n نامتناهی است.

تعریف: فرض کنید a_1,a_2,...,a_n اعدادی صحیح و ناصفر باشند. در میان مضرب‌های مشترک مثبت a_1,a_2,...,a_n کوچکترین عدد را (که بنا بر اصل خوش ترتیبی وجود دارد.) کوچکترین مضرب مشترک a_1,a_2,...,a_n می‌نامیم و آن را با ‍[a_1,a_2,...,a_n] نشان می‌دهیم.

قضیه: اگر a_1,a_2,...,a_n اعدادی صحیح و ناصفر باشند، هر مضرب مشترک آن‌ها بر [a_1,a_2,...,a_n] بخش‌پذیر است.

برهان: اگر k مضرب مشترکی از a_1,a_2,...,a_n باشد، بنابر الگوریتم تقسیم اعدادی صحیح مانند q و r وجود دارند که

(۱) k=[a_1,a_2,...,a_n]q+r و 0 \le r<[a_1,a_2,...,a_n]


از طرف دیگر a_i|[a_1,a_2,...,a_n] و a_i|k برای هر 1 \le i \le n

بنابراین a_i|r

یعنی r مضربی مشترک از a_1,a_2,...,a_n است. در نتیجه اگر r>0، آنگاه r \ge [a_1,a_2,...,a_n]، که با نابرابری سمت راست (۱) تناقض دارد بنابراین r=0 و k|[a_1,a_2,...,a_n]

منابع[ویرایش]

کتاب نظریه اعداد-مریم میرزاخانی، رویا بهشتی زواره