Resultaat
Zonder mod
Volle rondes
ggd(a, n)

    Meer over modulair rekenen

    Modulaire klok

    Vijf uur na 9 uur is het 2 uur, omdat 9 + 5 = 14 en 14 is 2 meer dan 12. Dat is modulair rekenen: tellen op een klok die na n weer bij 0 begint. Kies een bewerking, voer n, a en b in, en de rekenmachine geeft het antwoord met elke stap uitgeschreven, van de rest van een deling tot herhaald kwadrateren en het uitgebreide algoritme van Euclides, terwijl de klok laat zien hoe het antwoord bereikt wordt. Kies een bewerking en voer dan de modulus n en de getallen a en b in; gehele getallen tot 30 cijfers werken, ook negatieve, en n mag tot 10^18 gaan. De klok heeft n posities met 0 bovenaan, en de wijzer wijst naar het antwoord. Optellen en aftrekken worden getekend als een spiraal van b stappen, met één ring voor elke volle ronde; vermenigvuldigen als sprongen van a; machten als de koorden a, a², a³ …, die zich sluiten tot een cyclus; de inverse en delen als de veelvouden die op 1 of op a uitkomen. De stappen tonen dezelfde berekening in getallen. Tot mod 20 wordt de tabel van de bewerking getoond; klik op een cel om de getallen ervan te gebruiken. Voorbeeld vult een klassiek vraagstuk in.

    Hoe het werkt

    1. Kies een bewerking: a mod n, optellen, aftrekken, vermenigvuldigen, delen, een macht of de inverse van a.
    2. Voer de modulus n en de getallen a en b in, of kies een voorbeeld zoals het laatste cijfer van 7^2026 of een klein RSA-bericht.
    3. Lees het antwoord en de stappen, volg het pad op de klok en klik tot mod 20 op een cel van de tabel om de getallen ervan te proberen.

    Wat a mod n betekent

    a mod n is de rest als a door n wordt gedeeld: 17 mod 5 = 2, omdat 17 = 3 × 5 + 2. De rest ligt altijd van 0 tot n − 1, ook voor negatieve getallen: −7 mod 3 = 2, omdat −7 = −3 × 3 + 2. Op de klok betekent dat 7 stappen terug lopen vanaf 0. Twee getallen met dezelfde rest zijn congruent, geschreven 17 ≡ 2 (mod 5), een notatie die Carl Friedrich Gauss in 1801 invoerde. Sommen, verschillen en producten mogen bij elke stap mod n gereduceerd worden, wat de getallen klein houdt.

    Waar modulair rekenen wordt gebruikt

    Klokken en kalenders werken mod 12, mod 24 en mod 7: 100 dagen na een woensdag is het vrijdag, omdat 100 mod 7 = 2. Controlecijfers gebruiken het om typefouten te vangen, van ISBN-10-nummers (mod 11) tot bankpasnummers (mod 10) en IBAN's (mod 97). Versleutelingen verschuiven letters mod 26, en de affiene versleuteling heeft een inverse mod 26 nodig om te ontsleutelen. RSA, dat een groot deel van het internet beveiligt, versleutelt een bericht m als m^e mod n en ontsleutelt met een andere macht: met n = 3233 is 65^17 mod 3233 = 2790 en 2790^413 mod 3233 = 65.

    Veelgestelde vragen

    Hoe bereken je a mod n voor een negatief getal?

    Tel veelvouden van n op of trek ze af tot het getal tussen 0 en n − 1 ligt. Voor −7 mod 3: −7 + 9 = 2, dus het antwoord is 2. Sommige programmeertalen geven in plaats daarvan −1 voor −7 % 3, omdat ze het quotiënt naar nul afronden; in de wiskunde is de rest nooit negatief.

    Wat is een modulaire inverse?

    De inverse van a mod n is het getal x met a × x ≡ 1 (mod n). De inverse van 7 mod 26 is 15, omdat 7 × 15 = 105 = 4 × 26 + 1. Die bestaat alleen als a en n geen gemeenschappelijke factor hebben, en het uitgebreide algoritme van Euclides vindt hem. Delen door a mod n betekent vermenigvuldigen met de inverse ervan.

    Hoe kun je een macht als 7^2026 mod n berekenen?

    Door herhaald kwadrateren: kwadrateer 7 steeds opnieuw en reduceer elke keer mod n, zodat je 7^1, 7^2, 7^4, 7^8 enzovoort krijgt, en vermenigvuldig dan de machten die samen 2026 in binaire vorm opbouwen. Dat kost 10 kwadrateringen en 7 vermenigvuldigingen in plaats van 2.025 vermenigvuldigingen, en de getallen worden nooit groter dan n². 7^2026 eindigt op 9.

    Waarom toont de klok 0 in plaats van 12?

    Bij modulair rekenen lopen de resten van 0 tot n − 1, dus op een klok met 12 posities is het middaguur 0. 12 ≡ 0 (mod 12); een gewone klok zet gewoon 12 waar de wiskunde 0 schrijft.

    Hoe groot mogen de getallen zijn?

    a en b mogen tot 30 cijfers hebben en negatief zijn, en de modulus mag tot 10^18 gaan. De rekenmachine werkt met exacte gehele getallen in je browser, zodat zelfs voorbeelden op RSA-formaat exacte antwoorden geven, en er wordt niets verstuurd.

    Klaar om het te proberen?

    Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

    Ga naar Editor