424
Relations, Functions, and Matrices
example 48
Military time uses a 24-hour clock, where the hours run from 0 through 23. One
half hour before midnight in military time is 23:30. Standard time uses am and pm
for the first half of the day and the second half of the day, respectively, with the
hours in each half running from 0 through 11. One half hour before midnight in
standard time is 11:30 pm. Conversion from military time to standard time uses the
modulo 12 function:
8:00 military time:
Compute 8 mod 12 = 8 gives 8:00 am standard time
16:00 military time:
Compute 16 mod 12 = 4 gives 4:00 pm standard time
The am or pm designation is determined by whether the quotient in the division is
0 (am) or 1 (pm). Counting modulo 12 begins at 0 and wraps around to 0 again
when 12 is reached:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3, …
This counting scheme is sometimes taught to young children as “clock arithmetic.”
Section 5.1 defined an equivalence relation called congruence modulo n:
x ≡ y (mod n) if x − y is an integral multiple of n.
Given the similar terminology, one would expect that congruence modulo n and
the modulo n function would surely be related.
PRaCtiCe 43
a. Prove that x ≡ y (mod n) if and only if (x − y) mod n = 0.
b. Prove that x ≡ y (mod n) if and only if x mod n = y mod n.
■
Exercises at the end of this section show how some arithmetic operations
using mod n can be broken down for simpler calculation. One such result
( Exercise 7) is particularly useful:
(x # y) mod n = (x mod n # y mod n) mod n
(1)
By Equation (1),
220 mod 6 = (22 mod 6 # 10 mod 6) mod 6 = (4 # 4) mod 6 = 16 mod 6 = 4
In addition, spreadsheet software usually contains a mod function that speeds up
computations.
Hashing
A hash function is a function h: S S T where the domain S is a set of text strings
or integer values, and the codomain T is the set of integers 50, 1, …, t − 16
Relations, Functions, and Matrices
example 48
Military time uses a 24-hour clock, where the hours run from 0 through 23. One
half hour before midnight in military time is 23:30. Standard time uses am and pm
for the first half of the day and the second half of the day, respectively, with the
hours in each half running from 0 through 11. One half hour before midnight in
standard time is 11:30 pm. Conversion from military time to standard time uses the
modulo 12 function:
8:00 military time:
Compute 8 mod 12 = 8 gives 8:00 am standard time
16:00 military time:
Compute 16 mod 12 = 4 gives 4:00 pm standard time
The am or pm designation is determined by whether the quotient in the division is
0 (am) or 1 (pm). Counting modulo 12 begins at 0 and wraps around to 0 again
when 12 is reached:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3, …
This counting scheme is sometimes taught to young children as “clock arithmetic.”
Section 5.1 defined an equivalence relation called congruence modulo n:
x ≡ y (mod n) if x − y is an integral multiple of n.
Given the similar terminology, one would expect that congruence modulo n and
the modulo n function would surely be related.
PRaCtiCe 43
a. Prove that x ≡ y (mod n) if and only if (x − y) mod n = 0.
b. Prove that x ≡ y (mod n) if and only if x mod n = y mod n.
■
Exercises at the end of this section show how some arithmetic operations
using mod n can be broken down for simpler calculation. One such result
( Exercise 7) is particularly useful:
(x # y) mod n = (x mod n # y mod n) mod n
(1)
By Equation (1),
220 mod 6 = (22 mod 6 # 10 mod 6) mod 6 = (4 # 4) mod 6 = 16 mod 6 = 4
In addition, spreadsheet software usually contains a mod function that speeds up
computations.
Hashing
A hash function is a function h: S S T where the domain S is a set of text strings
or integer values, and the codomain T is the set of integers 50, 1, …, t − 16