Lemma van Euclides

Het lemma van Euclides is een uitspraak over delers van het product van twee gehele getallen. Het lemma zegt: als van twee gehele getallen a en b het product ab deelbaar is door het priemgetal p, is p in ieder geval deler van een van beide, dus of van a of van b (of van beide). Formeel:

$\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. Het lemma is naar de Griekse wiskundige Euclides van Alexandrië, ongeveer 265 - 200 v.Chr., genoemd.

Bewijs

Veronderstel dat a niet door p is te delen, dus dat de grootste gemene deler van a en p gelijk is aan 1:

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

Volgens de stelling van Bachet-Bézout zijn er 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 is te delen, is ook yab door p te delen. Dus zijn beide producten aan de linkerkant van de vergelijking door p te delen, en is ook b door p te delen.