Lemma van Euclides

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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:

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[bewerken]

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

.

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

.

Vermenigvuldigen van beide zijden met b levert

.

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.