WisFaq!

Modulo rekenen

Hoe bewijs ik dat:
(y^A mod p)^B mod p = y^(A * B) mod p?

Bedankt alvast!

Jasper
19-4-2004

Antwoord

Dag Jasper,

Het staat er niet bij, maar ik ga er van uit, dat alle variabelen hier gehele getallen voorstellen, dus ook A en B.
Het bewijs zou je als volgt kunnen aanpakken.
y^A mod p is te beschrijven als
y^A + k·p
waarbij k een of ander geheel getal is.
Dit getal moet je tot de macht B verheffen.
Het binomium van Newton geeft aan, hoe je dit zou kunnen uitwerken.
Zie je dan, dat bijna alle termen tenminste een factor p bevatten?
De rest kun je dan misschien zelf verder bedenken.
succes!

Anneke
19-4-2004