Lemma van Euclides

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

Volgens het lemma van Euclides geldt dat wanneer van twee gehele getallen a en b het product ab door het priemgetal p is te delen, in ieder geval één van beide, dus of a of b of beide door p zijn te delen. Genoteerd:

.

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]

Zij de grootste gemene deler van a en p. Daar p een priemgetal is en door d is te delen, geldt:

.

Veronderstel nu dat a niet door p is te delen, dus dat:

.

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.