Lemma van Euclides

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Jump to search

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.