6.8 Strange Numbers 109(wherexandyare the numbers corresponding to the daysXandY), and
so 7 is a divisor of (x−y)5. But 5 is not divisible by 7 and neither is
x−y(since these are two different nonnegative integers smaller than 7).
Since 7 is a prime, this is a contradiction. This way can talk about ordinary
numbers instead of the days of the week; the price we pay is that we have
to use congruences instead of equality.
6.8.1Find We/Fr; Tu/Fr; Mo/Tu; Sa/Tu.Is there anything special about the number 7 here? In a society where the
week consists of 10 or 13 or 365 days, we could define addition, subtraction,
and multiplication of the days of the week similarly.
Letmbe the number of days of the week, which in mathematical lan-
guage we call the modulus. It would be impractical to introduce new names
for the days of the week,^1 so let’s just call them 0 , 1 ,...,m−1. The over-
lining indicates that, for example,2 refers not only to day 2, but also to
daym+2, day 2m+ 2, etc.
Addition is defined bya+b=c, wherecis the remainder ofa+bmodulo
m. Multiplication and subtraction are defined in a similar way. This way
we have a new number system: It consists of onlymnumbers, and the basic
arithmetic operations can be carried out. These operations will obey the
basic laws of computation, which follows just as in the casem= 7 above.
This version of arithmetic is calledmodular arithmetic.
What about division? If you carefully read the proof that we can do
division whenm= 7, you see that it uses one special property of 7: that
it is a prime! There is indeed a substantial difference between modular
arithmetic with prime and nonprime moduli.^2 In what follows, we shall
restrict our attention to the case where the modulus is a prime, and to
emphasize this, we will denote it byp. This number system consisting of
0 , 1 ,...,p−1, with the four operations defined as above, is called aprime
field.
The 2-element field.The smallest prime number is 2, and the simplest
prime field has only 2 elements,0 and1. It is easy to give the addition and
multiplication tables:
+ 0 1
0 0 1
1 1 0
· 0 1
0 0 0
1 0 1
(There is really only one operation here that does not follow from the
general properties of 0 and 1, namely,1+1=0. There is no need to specify
(^1) In many languages, the names of some days are derived from numbers.
(^2) Plural of “modulus.”