Кіріспе
Жарым-жартылай бөлгіш көбейтіндінің факторларының біреуін бөледі. Алгебра мен сандар теориясында Евклид леммасы – жай сандардың негізгі қасиеттерін көрсететін лемма, атап айтқанда:
In algebra and number theory, Euclid's lemma is a lemma that captures a fundamental property of prime numbers, namely:
For example, if , , , then , and since this is divisible by 19, the lemma implies that one or both of 133 or 143 must be as well. In fact,
If the premise of the lemma does not hold, i. e., p is a composite number, its consequent may be either true or false. For example, in the case of , , , composite number 10 divides , but 10 divides neither 4 nor 15. This property is the key in the proof of the fundamental theorem of arithmetic. It is used to define prime elements, a generalization of prime numbers to arbitrary commutative rings. Euclid's Lemma shows that in the integers irreducible elements are also prime elements. The proof uses induction so it does not apply to all integral domains.
Мысалы, егер , , , болса, онда , және егер бұл 19-ға бөлінсе, лемма бойынша 133 немесе 143-тің біреуі немесе екеуі де 19-ға бөлінуі керек. Шындығында, егер лемманың шарты орындалмаса, яғни p – жай сан болмаса, оның салдары дұрыс немесе бұрыс болуы мүмкін. Мысалы, , , , жай сан емес 10 саны ,-ге бөлінеді, бірақ 10 саны 4-ке де, 15-ке де бөлінбейді. Бұл қасиет арифметиканың негізгі теоремасын дәлелдеуде маңызды рөл атқарады. Ол жай элементтерді, яғни жай сандарды кез келген коммутативті сақиналарға жалпылау үшін қолданылады. Евклид леммасы бүтін сандардағы толымсыз элементтердің де жай элементтер екенін көрсетеді. Дәлелдеме индукцияға негізделген, сондықтан ол барлық интегралдық домендерге қолданылмайды.
In algebra and number theory, Euclid's lemma is a lemma that captures a fundamental property of prime numbers, namely:
For example, if , , , then , and since this is divisible by 19, the lemma implies that one or both of 133 or 143 must be as well. In fact,
If the premise of the lemma does not hold, i. e., p is a composite number, its consequent may be either true or false. For example, in the case of , , , composite number 10 divides , but 10 divides neither 4 nor 15. This property is the key in the proof of the fundamental theorem of arithmetic. It is used to define prime elements, a generalization of prime numbers to arbitrary commutative rings. Euclid's Lemma shows that in the integers irreducible elements are also prime elements. The proof uses induction so it does not apply to all integral domains.
Тарих
Лемма алғаш рет Евклидтің "Элементтер" кітабының VII кітабында 30-шы теорема ретінде келтіріледі. Ол элементарлық сандар теориясын қамтитын дерлік барлық кітапқа енгізілген. Лемманың бүтін сандарға жалпылануы Жан Престедің "Новые элементы математики" оқулығында 1681 жылы пайда болды. Карл Фридрих Гаусс-тың "Disquisitiones Arithmeticae" еңбегінде лемманың тұжырымы Евклидтің 14-теоремасы (2-бөлім) болып табылады, ол бүтін санның жай факторларға жіктелуінің бірегейлігін дәлелдеу үшін қолданылады (16-теорема), оның бар екендігін "көздейтіндей" деп қабылдайды. Осы болмысы мен бірегейлігінен ол жай сандарды бүтін сандарға жалпылайды. Осы себепті Евклид леммасының жалпылануы кейде Гаусс леммасы деп аталады, бірақ кейбіреулер бұл қолданыс Гаусс леммасының квадраттық қалдықтар туралы леммасымен шатасудан туындаған қателік деп санайды.
Дәлелдендіру
Бірінші екі тарау Евклид леммасының жалпыланған түрінің дәлелі болып табылады, атап айтқанда: егер n ab-ны бөледі және a-мен өзара жай болса, онда ол b-ны бөледі. Түпнұсқа Евклид леммасы осыдан бірден шығады, себебі егер n жай сан болса, онда ол a-ны бөледі немесе a-ны бөлмейді, сонда ол a-мен өзара жай болады, демек жалпыланған түріне сәйкес ол b-ны бөледі.