Skip to main content
It looks like you're using Internet Explorer 11 or older. This website works best with modern browsers such as the latest versions of Chrome, Firefox, Safari, and Edge. If you continue with this browser, you may see unexpected results.

Modular Numbers and Cryptography

Modular Multiplication

Properties of modular multiplication:

  1. If \(a \cdot b =c\), then \(a\pmod{N} \cdot b\pmod{N} \equiv c\pmod{N}\).
  2. If \(a \equiv b \pmod{N}\), then \(ka \equiv kb \pmod{N}\) for any integer \(k\).
  3. If \(a \equiv b \pmod{N}\) and \(c \equiv d \pmod{N}\), then \(ac \equiv bd \pmod{N}\).

Examples

1. What is \((8 \times 15) \pmod{6}\)?

We could find the modulo of each number and then find the product.

\(8 \pmod{6} \equiv 2\) and \(15 \pmod{6} \equiv 3\)

\(2 \cdot 3=6\). Therefore, \(6 \equiv 0 \pmod{6} \)

With property 1, we could also find the product first and then the residue.

\begin{align} &(8 \times 15) \pmod{6} \\ \equiv &120 \pmod{6} \\ \equiv &0 \pmod{6} \end{align}

2. Perform the operation \((23 \cdot 37 \cdot 42 \cdot 19) \pmod{17}\).

\(23 \cdot 37 \cdot 42 \cdot 19 = 679,098\)

\(679,098 \pmod {17} \equiv 16 \pmod{17}\)

3. Perform the operation \(\left(32 + 5 \times (123 - 54)\right) \pmod{19} \)

\begin{align} &\equiv 377 \pmod{19} \\ &\equiv 16 \pmod{19} \end{align}

4. Perry has 44 boxes of water in his truck. The bottles of water in each box are packed oddly so that there are 113 bottles of water in each box. Perry plans to pack waters into cases of 12 bottles to sell. After making as many complete cases as possible, how many waters will Perry have leftover?

Solution

Since the word problem is asking us to find the remainder, we can apply modular arithmetic. The cases have 12 bottles, so the modulo is 12.

\[(44 \cdot 113) \pmod{12} \]

We can find the remainder and solve the problem

\[ (44 \cdot 113) \pmod{12} \equiv 4972 \pmod{12} \equiv 4 \pmod{12} \]

There will be 4 bottles of water remaining. 

chat loading...