2
What is modular arithmetic?
source link: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
An Introduction to Modular Math
When we divide two integers we will have an equation that looks like the following:
AB=Q remainder R \dfrac{A}{B} = Q \text{ remainder } R BA=Q remainder Rstart fraction, A, divided by, B, end fraction, equals, Q, start text, space, r, e, m, a, i, n, d, e, r, space, end text, R
A A AA is the dividend
B B BB is the divisor
Q Q QQ is the quotient
R R RR is the remainder
B B BB is the divisor
Q Q QQ is the quotient
R R RR is the remainder
Sometimes, we are only interested in what the remainder is when we divide A A AA by B B BB.
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 A A AA, B B BB, Q Q QQ, and R R RR as above, we would have: A mod B=R A \text{ mod } B = R A mod B=RA, start text, space, m, o, d, space, end text, B, equals, R
We would say this as A A AA modulo B B BB is equal to R R RR. Where B B BB is referred to as the modulus.
For example:
13513 mod 5==2 remainder 33
Visualize modulus with clocks
Observe what happens when we increment numbers by one and then divide them by 3.
03132333435363=======0 remainder 00 remainder 10 remainder 21 remainder 01 remainder 11 remainder 22 remainder 0
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 A mod B A \text{ mod } B A mod BA, start text, space, m, o, d, space, end text, B we can follow these steps:
- Construct this clock for size B B BB
- Start at 0 and move around the clock A A AA steps
- Wherever we land is our solution.
(If the number is positive we step clockwise, if it's negative we step counter-clockwise.)
Examples
8 mod 4=? 8 \text{ mod } 4 = ? 8 mod 4=?8, start text, space, m, o, d, space, end text, 4, equals, question mark
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 8 mod 4=0 8 \text{ mod } 4 = \bf{0} 8 mod 4=08, start text, space, m, o, d, space, end text, 4, equals, 0.
7 mod 2=? 7 \text{ mod } 2 = ? 7 mod 2=?7, start text, space, m, o, d, space, end text, 2, equals, question mark
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 7 mod 2=1 7 \text{ mod } 2 = \bf{1} 7 mod 2=17, start text, space, m, o, d, space, end text, 2, equals, 1.
−5 mod 3=? -5 \text{ mod } 3 = ? −5 mod 3=?minus, 5, start text, space, m, o, d, space, end text, 3, equals, question mark
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 −5 mod 3=1 -5 \text{ mod } 3 = \bf{1} −5 mod 3=1minus, 5, start text, space, m, o, d, space, end text, 3, equals, 1.
Conclusion
If we have A mod B A \text{ mod } B A mod BA, start text, space, m, o, d, space, end text, B and we increase A A AA by a multiple of B \bf{B} BB, we will end up in the same spot, i.e.
A mod B=(A+K⋅B) mod B A \text{ mod } B = (A + K \cdot B) \text{ mod } B A mod B=(A+K⋅B) mod BA, start text, space, m, o, d, space, end text, B, equals, left parenthesis, A, plus, K, dot, B, right parenthesis, start text, space, m, o, d, space, end text, B for any integer K \bf{K} KK.
For example:
3 mod 10=313 mod 10=323 mod 10=333 mod 10=3
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.Congruence Modulo
You may see an expression like:
A≡B(mod C) A \equiv B\ (\text{mod } C) A≡B (mod C)A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
This says that A A AA is congruent to B B BB modulo C C CC. 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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK