Modulair rekenen
Modulair rekenen is een vorm van geheeltallig rekenen met een modulus.
Bij modulair rekenen wordt gerekend met de rest na deling door de modulus m. Dus alleen met de getallen 0, 1, ..., m-1. De normale definitie van optelling en vermenigvuldiging worden gebruikt, maar als het resultaat groter of gelijk is aan m wordt net zo vaak m afgetrokken tot het resultaat weer kleiner is dan m.
Het rekenen met modulus 'm' of ook modulo 'm' wiskundig ook aangeduid als (
).
Het bekendste voorbeeld van modulair rekenen is de tijdrekening in uren, 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. Ook elke computer rekent modulair met modulus 2n, waarbij n het aantal bits in een variabele is.
Eenvoudig aangetoond kan worden dat () algebraïsch gezien een ring is en wel een commutatieve ring met één-element.
In het bijzondere geval dat m een priemgetal is, is () zelfs een lichaam.
Dit laatst kan als volgt worden aangetoond : uit de definitie van een priemgetal volgt dat een priemgetal m relatief priem is met alle getallen 1, ..., m-1 tussen 0 en m (want 1 is de enige deler van m die kleiner is dan m zelf). Met behulp van het algoritme van Euclides kan nu voor elke n tussen 1 en m de getallen x en y gevonden worden zodat nx + my = ggd(n,m)
Nu is de term my modulo m gelijk aan 0, want my /m = y rest 0. Verder geldt dat ggd(n,m) = 1, want n en m zijn relatief priem.
Dus modulo m een priemgetal is er voor elke n een x zodat nx = 1
