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.

∀   a , b ∈ Z : p   priem ∧ p | a b ⟹ p | a ∨ p | b {\displaystyle \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.

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

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

x p + y a = 1 {\displaystyle xp+ya=1}

Vermenigvuldigen van beide zijden met b levert

x p b + y a b = b {\displaystyle 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.