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.

Previous | Next

  1. What is Modular Arithmetic?
  2. Basic Operations
  3. Multiplicative Inverse
  4. Fermat’s Little Theorem
  5. Euler’s Totient Function
  6. Applications

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

Sharing the Wonder