Basic Operations

Modular arithmetic has nearly the same arithmetic rules as regular integers with some slight differences. As a result addition and multiplication are straight forward. Subtraction is different in that it  will always result in a positive number.

Addition : $a \bmod N + b \bmod N = (a+b) \bmod N$

•  $5 \bmod 6 + 2 \bmod 6 = 7 \bmod 6 = 1 \bmod 6$

subtraction : $a \bmod N - b \bmod N = (a-b) \bmod N$

•  $4 \bmod 5 - 3 \bmod 5 = 1 \bmod 5$

Multiplication : $a \bmod N \times b \bmod N = ( a \times b) \bmod N$

• $3 \bmod 7 \times 4 \bmod 7 = 12 \bmod 7 = 5 \bmod 7$

exponentiation : $a^b \bmod N = (a \bmod N)^b$

• $13^ {100} \bmod 12 = 13 \bmod12 ^ {100} = 1 \bmod 12 ^ {100} = 1 \bmod 12$

The modulo of a negative number will always result in a positive number. For example $-12 \bmod 8 = 4$ since $-12 = -1 \times 8 + 4$. Another example is $-40 \bmod 6 = 2$ since $-40 = -7 \times 6 + 2$.

Filed under : Crash Courses, Mathematics

Sources Used

• Elementary Number Theory by James K. Strayer
• Data Abstraction and Problem Solving with C++, Walls and mirrors by Frank M. Carrano