5.4: Modular Systems

Divides

Let \(a\) and \(b\) be two integers such that \(a \neq 0\). We say "\(a\) divides \(b\)" or \(a\mid b\) if and only if \(b=aq\) for some integer \(q\).

The following statements are equivalent:

• \(a\) divides \(b\),
• \(a\) is a divisor of \(b\),
• \(a\) is a factor of \(b\),
• \(b\) is a multiple of \(a\), and
• \(b\) is divisible by \(a\).

In terms of division, we say that \(a\) divides \(b\) if and only if the remainder is zero when \(b\) is divided by \(a\). We adopt the notation \(a \mid b\).

Do not use a forward slash \(/\) or a backward slash \(\backslash\) in the notation. To say that \(a\) does not divide \(b\), we add a slash across the vertical bar, as in \(a \nmid b\)

Do not confuse the notation \(a\mid b\) with \(\frac{a}{b}\). The notation \(\frac{a}{b}\) represents a fraction. It is also written as \(a/b\) with a (forward) slash. It uses floating-point (that is, real or decimal) division. For example, \(\frac{11}{4}=2.75\).

Both integers \(a\) and \(b\) can be positive or negative, and \(b\) could even be 0. The only restriction is \(a\neq0\). In addition, \(q\) must be an integer.

Example 1

Check to see if these are true:

1. \(5 \mid 35\)
2. \(7 \mid 14\)
3. \(8 \mid 36\)

Solution

1. Yes \(5 \mid 35\) because \(35=5 \times 7\).
2. Yes \(7 \mid 14\) because \(14=7 \times 2\).
3. No \(8 \nmid 36\) because \(\frac{36}{8}=4.5\) which is not an integer.

Modular arithmetic uses only a fixed number of possible results in all its computation. For instance, there are only 12 hours on the face of a clock. If the time now is 7 o’clock, 20 hours later will be 3 o’clock; and we do not say 27 o’clock! This example explains why modular arithmetic is referred to by some as clock arithmetic.

Example 2

If the current time is 2:00 p.m. What time will it be 65 hours from now?

Solution

Assume the current time is 2:00 p.m. Write this as 14:00. Sixty five hours later, it would be 79:00. Since \[79 = 24\cdot3+7, \nonumber\] it will be 7:00 or 7 a.m.

Example 3

If today is Wednesday. What day of the week will it be 11 days from now?

Solution

Designate Sunday, Monday, Tuesday, …, Saturday as Day 0, 1, 2, …, 6. If today is Wednesday, then today is Day 3. 11 days from now it will be day 14. Since \[14 = 7\cdot2+0, \nonumber\] it will be Day 0 or Sunday.

hIn the clock example above, we essentially regard 27 o’clock the same as 3 o’clock. They key is, we are only interested in the remainder when a value is divided by 24. In the week example above, we are only interested in the remainder when a value is divided by 7.

Congruent Modulo \(m\)

Let \(m\geq2\) be a fixed integer. We say the two integers \(a\) and \(b\) are congruent modulo m, denoted \[a \equiv b \pmod{m} \nonumber\] if and only if \(m\mid (a-b)\). The integer \(m\) is called the modulus of the congruence.

Example 4

Determine if these are true:

1. \(59 \equiv 27 \pmod{8} \nonumber\)
2. \(33 \equiv 11 \pmod{12} \nonumber\)
3. \(11 \equiv 35 \pmod{6} \nonumber\)

Solution

1. Yes. \(59-27=32\) and \(8 \mid 32\).
2. No. \(33-11=22\) and \(\frac{22}{12} \approx 1.83\) which is not an integer.
3. Yes. \(11-35=-24\) and \(6 \mid -24\) because \(-24=6 \times -4\).

Performing Arithmetic Operations In A Modulo \(m\) System

To add, subtract, and multiply in a modulo \(m\) system:

1. Perform the operation as usual.
2. Replace the result in (1) by one of the numbers 0, 1, 2, ... , \(m-1\) that is congruent to that result.

(These are the remainders when dividing an integer by \(m\)).

Example 5

Perform the following operations:

1. \(7 + 4 \pmod{8}\)
2. \(2 - 5 \pmod{12}\)
3. \(5 \times 8 \pmod{9}\)

Solution

1. \(7+4=11\) and \(11 \equiv 3 \pmod{8} \nonumber\), so \(7 + 4 \equiv 3 \pmod{8}\).
2. \(2-5=-3\) and \(-3 \equiv 9 \pmod{12} \nonumber\), (\(-3+12=9\)), so \(2 - 5 \equiv 9 \pmod{12}\).
3. \(5 \times 8=40\) and \(40 \equiv 4 \pmod{9} \nonumber\), (\(40 = 9 \cdot 4 + 4\)), so \(5 \times 8 \equiv 4 \pmod{9}\).

Example 6

Solve \(4 + x \equiv 2 \pmod{5} \nonumber\) using trial and error.

Solution

We need to test all the remainders 0, 1, 2, 3, and 4 to see which one(s) work. Yes there can be multiple answers.

\(4 + 0 \equiv 4 \pmod{5} \nonumber\) FALSE

\(4 + 1 \equiv 0 \pmod{5} \nonumber\) FALSE

\(4 + 2 \equiv 1 \pmod{5} \nonumber\) FALSE

\(4 + 3 \equiv 2 \pmod{5} \nonumber\) TRUE

\(4 + 4 \equiv 3 \pmod{5} \nonumber\) FALSE

Thus \(x \equiv 3 \pmod{5} \nonumber\).

Try it Now 1

Solve \(2x \equiv 3 \pmod{6} \nonumber\) by trial and error.

Answer

\(x \equiv 0 \pmod{6} \nonumber\) AND \(x \equiv 3 \pmod{6} \nonumber\).

Example 7

In the late third century, the Chinese mathematician Sun Tzu asked his students: "We have things of which we do not know the number; if we count by threes, the remainder is 2; if we count be fives, the remainder is 3; if we count by sevens, the remainder is 2. How many things are there?"

Solution

Each of his sentences is a congruence. Let's set them up:

\[\begin{aligned}
x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 2 \pmod{7}
\end{aligned} \nonumber \]

Then let's create a list of numbers that satisfy each congruence.

\[\begin{aligned}
2, 5, 8, 11, 14, 17, 20, 23, ...\\ 3, 8, 13, 18, 23, 28, 33, 38, ... \\ 2, 9, 16, 23, 30, 37, 44, 51, ...
\end{aligned} \nonumber \]

Since 23 is the smallest number that appears in all three lists, \(x=23\) is the least positive number that satisfies all three congruences.

Try it Now 2

Find the smallest positive integer such that if we divide by two, three, and four, the remainder is 1, but seven divides the number evenly. (Hint create four congruences and four lists of numbers).

Answer

49