Евклид леммасы

Уикипедия — ашық энциклопедиясынан алынған мәлімет
Мұнда ауысу: шарлау, іздеу

Евклид леммасы — элементар сандар теориясының классикалық нәтижесі. Ол 30-шы сөйлем ретінде Евклидтің «Бастамасының» VII бөлімінде келтірілген .

Гер p жай саны екі x·y сандарының көбейтіндісін бөлсе, онда p не x не y санын да қалдықсыз бөледі.


Дәлелдеу

x·y p-ға бөлінсін, сонымен бірге x p-ға бөлінбесін. Онда x және p — өзара жай, яғни, u және v

x\cdot u+p\cdot v=1 болатындай бүтін сандар табылады (Безу қатынасы бойынша).

Екі жағында y-ке көбейтсе шығатыны

(x\cdot y)\cdot u+p\cdot v\cdot y=y.

Сол жағындағы екі қосылғыш та p-ға бөлінеді, демек, оң жақта бөліну керек, дәлелдеу керегі де осы.