لم اقلیدس

در جبر و نظریۀ اعداد، لم اقلیدس ( به انگلیسی: Euclid's lemma ) بیان می کند که اگر p ∣ a b ، آنگاه p ∣ a یا p ∣ b . که p عددی اول و a و b اعدادی صحیح هستند؛ به عبارتی دیگر، اگر عدد اولی مانند p ، حاصل ضرب a و b را عاد کند، در این صورت p حداقل یکی از اعداد a یا b را عاد خواهد کرد؛ به عبارت دیگر، a یا b بر p بخش پذیر هستند.
لم اقلیدس کاربردهای زیادی در نظریۀ اعداد دارد. یکی از این کاربردها را در قضیۀ اساسی حساب می بینیم.
اثبات با استفاده از قضیۀ بزو:
طبق قضیۀ بزو، اگر x و y اعداد صحیح و نسبت به هم اول باشند، آنگاه اعداد صحیح r و s موجودند که:
r x + s y = 1
حال در لم اقلیدس داریم n ∣ a b و ( n , a ) = 1 . لذا طبق قضیۀ بزو، r و s صحیحی موجودند که:
r n + s a = 1
در نتیجه:
r n b + s a b = b
و از طرفی:
n ∣ r n b ,   n ∣ s a b
و لذا:
n ∣ r n b + s a b
بنابراین:
n ∣ b