Modular Arithmetic: Basics and Solving x MOD A = B and A MOD x = B (with A ≥ 0 and B ≥ 0)

Good to talk with you all again. Before we get back to HP Prime programming goodness, let's make a side trip into algebra land.

The Modulus Function

Definition:

X MOD Y = R where

R = remainder(X/Y) = frac(X/Y) * Y

A practical way to get the modulus is to get the remainder (in other words, what's left over) of the division X/Y.

For example:

13 MOD 5 = 3

Divide 13 by 5, we get the quotient of 2 and the remainder of 3.

Properties:

Let A and B be integers.

A MOD A = 0. Easily justified since an integer divided by itself has no remainder.

If B > A, A > 0, and B > 0, then A MOD B = A. Any integer divided by a larger integer, the remainder will be an original integer.

Example: 11 MOD 12 = 11. The division of 11/12 has the quotient of 0 and the remainder of 11.

A common way to think of the modulus function is dealing clocks and calendars (MOD 12).

x MOD A = B, A ≥ 0 and B ≥ 0

General solution: x = B + A*n, where n is any integer

Example:
x MOD 4 = 2.

Easily x = 2 is a solution since 2/4 leaves a quotient of 0 and remainder of 2.

Observe that x = 6 also works. 6/4 has a quotient of 1 and a remainder of 2.

Hence the solution is: x = 2 + 4 * n

A MOD x = B, A ≥ 0 and B ≥ 0

A way to find possible solutions is to build a table, using the good old trial and error technique. Stop when we get to A MOD A. (See the Properties section above) This can get very lengthy when A gets large. In trade, you can easily see the solutions of A MOD x = B (if solutions exist).

Example 1: 11 MOD x = 3

11 MOD 1 = 0
11 MOD 2 = 1
11 MOD 3 = 2
11 MOD 4 = 3
11 MOD 5 = 1
11 MOD 6 = 5
11 MOD 7 = 4
11 MOD 8 = 3
11 MOD 9 = 2
11 MOD 10 = 1
11 MOD 11 = 0

From this we find that the solutions are x = 4 and x = 8. A very fortunate occasion.

Example 2: 13 MOD x = 8

13 MOD 1 = 0
13 MOD 2 = 1
13 MOD 3 = 1
13 MOD 4 = 1
13 MOD 5 = 3
13 MOD 6 = 1
13 MOD 7 = 6
13 MOD 8 = 5
13 MOD 9 = 4
13 MOD 10 = 3
13 MOD 11 = 2
13 MOD 12 = 1
13 MOD 13 = 0

Darn it! No solution to 13 MOD x = 8. It happens sometimes.


Hopefully this is helpful. Thank you for your comments and questions. Honestly I can't thank you enough. Have a great day!

Eddie


This blog is property of Edward Shore. 2013