\require{AMSmath}
WisFaq - de digitale vraagbaak voor wiskunde en wiskunde onderwijs


Printen

Modulo met macht

Hallo ,
ik moet volgende vraag kunnen oplossen in stappen ,
6156 mod 33 = ?
ik weet niet echt met welke manier het beste is ,
zelf heb ik al geprobeert
6156 mod 33 = 6132 mod 33 · 6116 mod 33 ·618 mod 33
= 3 · 4 · 618 mod 33

bij de voorbeelden die ik heb staan komt het steeds uit dat de laatste term van de macht 1 is , nu weet ik niet of dit verplicht is ofzo , maar ik kan maar niet aan 16 als uitkomst komen ,

graag enige hulp

mvg Dimitri

Dimitr
Student Hoger Onderwijs België - zaterdag 5 december 2009

Antwoord

Je hebt al uitgezocht dat je 6132 mod 33 · 6116 mod 33 ·618 mod 33 moet berekenen.
Dit zijn niet zomaar willekeurige exponenten, maar de exponenten zijn machten van 2.
Bedenk nu het volgende: voor iedere a en e geldt dat ae·ae=a2e.
Je kunt dus die machten met exponenten die zelf weer machten van twee zijn heel makkelijk generen door herhaald te kwadrateren.
Ik krijg dan onderstaand tabelletje:

61 mod 33=28
612 : 282=784 mod 33=25
614 : 252=625 mod 33=31
618 : 312=961 mod 33=4
6116 : 42=16 mod 33=16
6132 : 162=256 mod 33=25

Kennelijk is dan 6156 mod 33=25·16·4 mod 33=1600 mod 33=16.

Hoe je nu eenvoudig kunt weten welke exponenten je moet kiezen is een ander verhaal. Dat op 1 uitkomen zou daar wel eens mee te maken kunnen hebben.


zondag 6 december 2009

Re: Modulo met macht

©2001-2024 WisFaq