Hoofdmenu openen

Modulair rekenen, of rekenen modulo een getal, is een vorm van geheeltallig rekenen met een getal dat als bovengrens fungeert, de modulus. Een typisch voorbeeld is de klok waarop modulo 12 (of modulo 24) gerekend wordt. Als het 6 uur is, dan staat de klok 8 uur later niet op 14, maar op 14 − 12 = 2 uur.

Bij modulair rekenen met modulus of rekenen modulo wordt gerekend met de getallen , waarna niet volgt maar weer opnieuw met 0 begonnen wordt. De getallen 0 tot en met staan als het ware in een kring. Het resultaat van een berekening modulo is de rest van het resultaat bij gewone berekening na deling door de modulus . De normale definities van optelling en vermenigvuldiging worden gebruikt, maar als het resultaat groter is dan of gelijk aan wordt net zo vaak afgetrokken tot het resultaat weer kleiner is dan . Getallen die modulo gelijk zijn, die dus een veelvoud van van elkaar verschillen, noemt men congruent modulo .

In het bovenstaande voorbeeld van de klok zijn 6 + 8 en 2 congruent modulo 12, wat genoteerd wordt als:


De verzameling getallen waarmee gerekend wordt modulo , wordt aangeduid als , naar het symbool dat de verzameling gehele getallen aanduidt.

VoorbeeldBewerken

Rekenen modulo 7 gebeurt met de getallen 0,1,...,6. De uitkomst van 4 + 5 is niet 9, maar 9 − 7 = + 2. Denkt men de getallen in een kring, of herhaald:

0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, ...

en telt men 5 verder vanaf het getal 4, dan komt men bij 2 uit.

Wat is 4 × 5? Niet 20, maar 20 − 7 − 7 = 6. Dat kan ook zo gezien worden als

4 × 5 = 5 + 5 + 5 + 5 = (5 + 5) + 5 + 5 ≡ 3 + 5 + 5 = (3 + 5) + 5 ≡ 1 + 5 = 6

De onderstaande tabel geeft alle mogelijkheden voor de optelling modulo 7.

optelling modulo 7
+ 0 1 2 3 4 5 6
0 0 1 2 3 4 5 6
1 1 2 3 4 5 6 0
2 2 3 4 5 6 0 1
3 3 4 5 6 0 1 2
4 4 5 6 0 1 2 3
5 5 6 0 1 2 3 4
6 6 0 1 2 3 4 5

Ook voor de vermenigvuldiging kan men een tabel maken.

vermenigvuldiging modulo 7
× 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6
2 0 2 4 6 1 3 5
3 0 3 6 2 5 1 4
4 0 4 1 5 2 6 3
5 0 5 3 1 6 4 2
6 0 6 5 4 3 2 1

Met behulp van deze tabel kan men ook delingen uitvoeren. Wat is 5 : 4 modulo 7? Noem dit getal q, dan is 4 q ≡ 5 modulo 7. Uit de tabel kan men aflezen dat q = 3, dus 5 : 4 ≡ 3 modulo 7.

DefinitieBewerken

Zij   een natuurlijk getal ongelijk aan 0, dan heten de twee gehele getallen   en   congruent modulo  , genoteerd:

 ,

als hun verschil   een geheel veelvoud is van  .

Het getal   wordt de modulus genoemd.

Opgemerkt moet worden dat de haakjes rond " " ook wel worden weggelaten.

In veel programmeertalen is het teken voor modulus het procentteken (%).

ToepassingBewerken

Het bekendste voorbeeld van modulair rekenen is de tijdrekening in hele uren (zie ook onder voor willekeurige tijden), die modulo 12 of modulo 24 gaat. Zo is de tijd bijvoorbeeld 10 uur na 22 uur gelijk aan 8 uur. Dus 10 + 22 = 8 modulo 24.

Geheeltallig rekenen in digitale computers vindt doorgaans plaats modulo  , waarbij   het aantal bits is dat gebruikt wordt om een getal weer te geven.   is dan begrensd door (meestal) de grootte van een processorregister. In een typische moderne computer heeft   de waarde 32 of 64. Niet-modulair rekenen wordt door sommige programmeertalen ondersteund, maar gaat ten koste van de rekensnelheid.

In België heeft zowel een gestructureerde mededeling van een overschrijving, alsook het bankrekeningnummer en het rijksregisternummer als laatste twee cijfers een controlegetal dat modulo 97 congruent is met de voorgaande cijfers. Zo geldt bijvoorbeeld voor de gestructureerde mededeling +++090/9337/55493+++, dat 0909337554 ≡ 93 (mod 97). Ook in de IBAN wordt een modulo 97 berekening uitgevoerd om een tweecijferig controlegetal te berekenen.

AlgebraBewerken

Eenvoudig aangetoond kan worden dat   algebraïsch gezien een ring is en wel een commutatieve ring met eenheidselement. De elementen van   noemt men de restklassen modulo  .

In het bijzondere geval dat   een priemgetal is, is   zelfs een lichaam. (Opgepast: wat men in Nederland een lichaam noemt, is in België een veld. Wat men in België een lichaam noemt, is in Nederland een scheeflichaam!)

Dit laatst kan als volgt worden aangetoond : uit de definitie van een priemgetal volgt dat een priemgetal   relatief priem is met alle getallen   tussen 0 en   (want 1 is de enige deler van   die kleiner is dan   zelf). Met behulp van het uitgebreid algoritme van Euclides kan nu voor elke   tussen 1 en   de getallen   en   gevonden worden zodat  .

Nu is de term   modulo   gelijk aan 0, want  . Verder geldt dat  , want   en   zijn relatief priem.

Dus modulo een priemgetal   is er voor elke   een   zodat  .

MachtsverheffenBewerken

Bij de machtsverheffing modulo   mogen alleen de grondtallen herleid worden, niet de exponenten. Zo is bijvoorbeeld:

 
 
 

Wel geldt de volgende stelling van Euler: als het grondtal geen delers gemeen heeft met  , dan mag de exponent herleid worden modulo de Euler-indicator   van  .

Grote machtenBewerken

Machtsverheffen modulo   tot grote machten kan relatief gemakkelijk uitgevoerd worden met behulp van machtsverheffing door kwadrateren, aangezien

 

Om   uit te rekenen kunnen achtereenvolgens de machten  ,  ,   berekend worden. Omdat  , wordt de gevraagde macht bepaald als het product modulo 319 van de overeenkomstige machten.

Voorbeeld en tegenvoorbeeld bij de stelling van EulerBewerken

De Euler-indicator van 5 is 4, en inderdaad is:

 

Dit geldt omdat 3 en 5 relatief priem zijn.

Daarentegen hebben 5 en 10 een deler gemeen en blijkt na herleiden van de exponent modulo 4, de Euler-indicator van 10, dat:

  maar:  

Reële getallenBewerken

Naar analogie van modulair rekenen met gehele getallen waarbij veelvouden van een bepaald geheel getal   buiten beschouwing worden gelaten, kan men ook reële getallen optellen en aftrekken (en vermenigvuldigen met gehele getallen) waarbij veelvouden van een positief reëel getal   buiten beschouwing worden gelaten. Een voorbeeld is het rekenen met de tijd van de dag, waarbij veelvouden van 24 uur buiten beschouwing worden gelaten, of de tijdweergave op een klok met wijzers, waarbij veelvouden van 12 uur buiten beschouwing worden gelaten, en daarmee corresponderend, rekenen met hoeken, waarbij volledige omwentelingen buiten beschouwing worden gelaten. De groep met betrekking tot de optelling is de cirkelgroep  .

Als additieve groep kan vermenigvuldigen met gehele getallen worden toegevoegd omdat dit overeenkomt met herhaald optellen, of herhaald aftrekken van nul. Als men echter vermenigvuldigen van willekeurige elementen toevoegt (gedefinieerd door gewoon vermenigvuldigen, met het buiten beschouwing laten van veelvouden van  ) wordt het geen ring, want bijvoorbeeld voor   geldt  , terwijl  . Er geldt dus geen distributiviteit (het komt er eenvoudig op neer dat als een term   buiten beschouwing wordt gelaten, dit uiteraard niet geldt voor een willekeurig reëel getal maal  ).

Zie ookBewerken