WisFaq!

Modulorekenen

Zou iemand kunnen bewijzen dat a²⁵ mod(88) congruent is met a⁵ mod(88)? (in het geval dat a en 88 relatief priem zijn heb ik al bewezen, het andere geval nog niet).

bob
7-6-2015

Antwoord

Hallo Bob,

Laten we eerst naar het eenvoudiger geval kijken modulo 11.
Als je de vijfdemachten van 1 tot en met 11 modulo 11 bekijkt, dan zijn de uitkomsten:

1⁵ = 1 (mod 11)
2⁵ = -1 (mod 11)
3⁵ = 1 (mod 11)
4⁵ = 1 (mod 11)
5⁵ = 1 (mod 11)
6⁵ = -1 (mod 11)
7⁵ = -1 (mod 11)
8⁵ = -1 (mod 11)
9⁵ = 1 (mod 11)
10⁵ = -1 (mod 11)
11⁵ = 0 (mod 11)

We zien dat in alle gevallen de uitkomst -1 (of 10), 0 of 1 is. Voor deze drie zelf geldt bovendien dat a⁵ =a (mod 11), dus als je nog een keer tot de vijfde macht doet, dan blijft de uitkomst in dezelfde congruentieklasse. Dat betekent dat voor elk getal a²⁵ =a⁵ (mod 11), dus a²⁵-a⁵ is altijd deelbaar door 11.

Voor congruentierekenen modulo 8 geldt iets dergelijks:
1⁵ = 1 (mod 8)
2⁵ = 0 (mod 8)
3⁵ = 3 (mod 8)
4⁵ = 0 (mod 8)
5⁵ = 5 (mod 8)
6⁵ = 0 (mod 8)
7⁵ = 7 (mod 8)
8⁵ = 0 (mod 8)
Dus de vijfde macht is ofwel congruent 0 mod 8 (alle vijfdemachten van even getallen zijn deelbaar door 8 - natuurlijk), of zij blijven in dezelfde congruentieklasse mod 8. Ik laat het afronden van de conclusie aan jezelf over.

Met vriendelijke groet,

FvL
8-6-2015