لم اقلیدس

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

لم اقلیدس بیان می‌کند که اگر عدد اولی مانند p عدد a.b (حاصل ضرب a و b) را عاد کند(a.b بر p بخشپذیر باشد) در این صورت p حداقل یکی از اعداد a یا b را عاد می‌کند، به عبارت دیگر a یا b بر p بخش پذیر هستند.

لم اقلیدس کاربر دهای زیادی در نظریه اعداد دارد. یکی از این کاربردها را در قضیه اساسی حساب می‌بینیم.

اثبات

اثبات با استفاده از قضیه ی بزو :

طبق قضیه بزو اگر x و y اعداد صحیح و نسبت به هم اول باشند آنگاه اعداد صحیح r و s موجودند که :

rx + sy = 1

حال در لم اقلیدس داریم n|ab و 1 = (n,a) لذا طبق قضیه ی بزو r و s صحیحی موجودند که

rn + sa = 1

در نتیجه

rnb + sab = b

و از طرفی

n|rnb و n|sab

و لذا

n|rnb+sab

بنابراین

n|b

جستارهای وابسته[ویرایش]