Hovedinnhold
Kurs: (Informatikk > Enhet 2
Leksjon 5: Modulær aritmetikk- Hva er modulær aritmetikk?
- Modulus operatør
- Modulus utfordring
- Kongruens modulo
- Kongruens sammenhenger
- Ekvivalente sammenhenger
- Kvotient rest teoremet
- Modulær addisjon og subtraksjon
- Modulær addisjon
- Modulus utfordring (addisjon og subtraksjon)
- Modulær multiplikasjon
- Modulær multiplikasjon
- Modulær eksponensiering
- Rask modulær eksponensiering
- Rask modulær eksponensiering
- Modulære inverse
- The Euclidean Algorithm
© 2024 Khan AcademyBrukervilkårPersonvernVarsel om informasjonskapsler
Hva er modulær aritmetikk?
An Introduction to Modular Math
When we divide two integers we will have an equation that looks like the following:
Sometimes, we are only interested in what the remainder is when we divide by .
For these cases there is an operator called the modulo operator (abbreviated as mod).
For these cases there is an operator called the modulo operator (abbreviated as mod).
Using the same , , , and as above, we would have:
We would say this as modulo is equal to . Where is referred to as the modulus.
For eksempel:
Visualize modulus with clocks
Observe what happens when we increment numbers by one and then divide them by 3.
The remainders start at 0 and increases by 1 each time, until the number reaches one less than the number we are dividing by. After that, the sequence repeats.
By noticing this, we can visualize the modulo operator by using circles.
We write 0 at the top of a circle and continuing clockwise writing integers 1, 2, ... up to one less than the modulus.
For example, a clock with the 12 replaced by a 0 would be the circle for a modulus of 12.
To find the result of we can follow these steps:
- Construct this clock for size
- Start at 0 and move around the clock
steps - Wherever we land is our solution.
(If the number is positive we step clockwise, if it's negative we step counter-clockwise.)
Examples
With a modulus of 4 we make a clock with numbers 0, 1, 2, 3.
We start at 0 and go through 8 numbers in a clockwise sequence 1, 2, 3, 0, 1, 2, 3, 0.
We start at 0 and go through 8 numbers in a clockwise sequence 1, 2, 3, 0, 1, 2, 3, 0.
We ended up at 0 so .
With a modulus of 2 we make a clock with numbers 0, 1.
We start at 0 and go through 7 numbers in a clockwise sequence 1, 0, 1, 0, 1, 0, 1.
We start at 0 and go through 7 numbers in a clockwise sequence 1, 0, 1, 0, 1, 0, 1.
We ended up at 1 so .
With a modulus of 3 we make a clock with numbers 0, 1, 2.
We start at 0 and go through 5 numbers in counter-clockwise sequence (5 is negative) 2, 1, 0, 2, 1.
We start at 0 and go through 5 numbers in counter-clockwise sequence (5 is negative) 2, 1, 0, 2, 1.
We ended up at 1 so .
Conclusion
If we have and we increase by a multiple of , we will end up in the same spot, i.e.
for any integer .
For eksempel:
Notes to the Reader
mod in programming languages and calculators
Many programming languages, and calculators, have a mod operator, typically represented with the % symbol. If you calculate the result of a negative number, some languages will give you a negative result.
e.g.
e.g.
-5 % 3 = -2.
Kongruensmodulo
Du har kanskje sett et uttrykk som dette:
This says that is congruent to modulo . It is similar to the expressions we used here, but not quite the same.
In the next article we will explain what it means and how it is related to the expressions above.
Ønsker du å delta i samtalen?
Ingen innlegg enda.