\require{AMSmath}

Modulo rekenen

Bestaat er een wiskundig bewijs voor onderstaande stelling? Zoja, zou u mij dan a.u.b. kunnen zeggen waar ik deze kan vinden? Bij voorbaat hartelijk dank!

x^a(mod b) = [x^(1/2 a)(mod b) * x^(1/2 a)(mod b)](mod b)

Scheve
Iets anders - woensdag 11 juni 2003

Antwoord

Voor de duidelijkheid, het gaat dus om de volgende stelling:
(x^a)(mod b) = [(x^(1/2 a))(mod b) * (x^(1/2 a))(mod b)](mod b)

Je kun dit als volgt inzien:
In het algemeen geldt:
((x mod p)·(y mod p)) mod p = x·y mod p
want
(x + m·p)·(y + n·p) = x·y + een veelvoud van p.

Pas je dit toe op jouw stelling, dan hoef je alleen nog maar aan te tonen dat x^a hetzelfde is als x^(1/2 a)·x^(1/2 a), en dat volgt vrijwel direct uit de regels voor machten.

Ik hoop dat dit duidelijk genoeg is.
groet,

Anneke
woensdag 11 juni 2003

©2001-2024 WisFaq