لم اقلیدس

صفحه عنوان اولین نسخه انگلیسی عناصر اقلیدس توسط سر هنری بیلینگزلی، 1570

در جبر و نظریۀ اعداد، لم اقلیدس الگو:به انگلیسی بیان می‌کند که اگر $p\mid ab$، آنگاه $p\mid a$ یا $p\mid b$. که $p$ عددی اول و $a$ و $b$ اعدادی صحیح هستند؛ به عبارتی دیگر، اگر عدد اولی مانند $p$، حاصل‌ضرب $a$ و $b$ را عاد کند، در این صورت $p$ حداقل یکی از اعداد $a$ یا $b$ را عاد خواهد کرد؛ به عبارت دیگر، $a$ یا $b$ بر $p$ بخش‌پذیر هستند.

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

اثبات

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

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

$rx+sy=1$

حال در لم اقلیدس داریم $n\mid ab$ و $(n,a)=1$. لذا طبق قضیۀ بزو، $r$ و $s$ صحیحی موجودند که:

$rn+sa=1$

در نتیجه:

$rnb+sab=b$

و از طرفی:

$n\mid rnb,n\mid sab$

و لذا:

$n\mid rnb+sab$

بنابراین:

$n\mid b$

جستارهای وابسته

• قضیۀ اقلیدس