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

Евклид леммасы — элементар сандар теориясының классикалық нәтижесі. Ол 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-ға бөлінеді, демек, оң жақта бөліну керек, дәлелдеу керегі де осы.