WisFaq!

Cryptografie

Hallo,

Wij moeten te weten komen waarom 8¹³ MOD 13= 8
en waarom 8²¹ MOD 21= Niet 8??
Wij weten dat het iets te maken heeft met priemgetallen en de driehoek van pascal, maar we komen er niet echt verder mee. Hopelijk kunt u ons verder helpen! Alvast bedankt!
Groetjes

julia en lizelotte
25-2-2004

Antwoord

Begin eens met 8 x 8 = 64 en 65 = 5 x 13.
Dit levert samen de volgende identiteit op: 64º-1(mod13).
In gewoon Nederlands staat hier: als je 64 deelt door 13, dan kom je één tekort.
Nog anders gezegd: deling van 64 door 13 laat een rest na van -1.
Normaal zou je natuurlijk zeggen: de rest is 12, maar hier is het slimmer om met -1 te werken.

Het product van 13 getallen 8 laat zich uiteraard schrijven als: (8x8) x (8x8) x (8x8) x (8x8) x (8x8) x (8x8) x 8.
Als je dit nu gaat delen door 13, dan hou je als rest over -1 x -1 x -1 x -1 x -1 x -1 x 8 = 8
Die zes getallen -1 snap je natuurlijk wel vanwege de eerdere opmerkingen.

Nu met 8^21.
Als je 8 x 8 = 64 deelt door 21, dan hou je als rest 1 over, want 64 = 3 x 21 + 1.
Schrijf nu in gedachten de rij van 21 achten eens helemaal uit. Steeds als je er twee hebt, krijg je bij deling door 21 de rest 1. In totaal heb je 10 van die tweetallen en dan nog één getal 8 extra, namelijk nummer 21.
De deling laat dus na: 1 x 1 x 1 ...... x 1 x 8 = 8.

Je ziet: beide leveren wel degelijk 8 op.

MBL
25-2-2004