Lemma van Euclides

Het lemma van Euclides is een uitspraak over getallen, dat het product van twee gehele getallen daar door kan worden gedeeld. Het lemma zegt: als van twee gehele getallen a en b het product ab door het priemgetal p kan worden gedeeld, kan in ieder geval van een van beide, dus of a, of b of allebei door p worden gedeeld.

$\forall \ a,b\in \mathbb {Z} :p\ {\text{priem}}\land p|ab\implies p|a\lor p|b$

Lemma betekent hulpstelling. Het lemma wordt in het bewijs van de hoofdstelling van de rekenkunde gebruikt en is naar de Griekse wiskundige Euclides van Alexandrië, ongeveer 265 - 200 v.Chr., genoemd.

Bewijs met behulp van de stelling van Bachet-Bézout 

Veronderstel dat het product ab door het priemgetal p kan worden gedeeld, maar dat a niet door p is te delen. De grootste gemene deler van a en p is dan gelijk aan 1.

$\operatorname {ggd} (a,p)=1$

Er zijn volgens de stelling van Bachet-Bézout dan gehele getallen x en y zodanig dat:

$xp+ya=1$

Vermenigvuldigen van beide zijden met b levert

$xpb+yab=b$

Omdat ab door p kan worden gedeeld, is ook yab door p te delen. Dus zijn beide producten aan de linkerkant van de vergelijking door p te delen en kan ook b door p worden gedeeld.