110 6. Integers, Divisors, and Primes
the subtraction table, since in this fielda+b=a−bfor everyaandb
(check!), nor the division table, since this is obvious: We cannot divide by
0, and dividing by1 does not change the dividend.)
It is inconvenient to write all these bars over the numbers, so we most
often omit them. But then we have to be careful, because we must know
whether 1 + 1 means 2 or 0; therefore, we change the sign of addition, and
use⊕for the addition in the 2-element field. In this notation, the addition
and multiplication tables look like this:
⊕ 0 1
0 0 1
1 1 0· 0 1
0 0 0
1 0 1
(we did not have to introduce a new multiplication symbol, because the
multiplication table for 0 and 1 is the same in the 2-element field as for
ordinary numbers).
This field is very small but very important, because a lot of computer
science, information theory, and mathematical logic uses it: Its two ele-
ments can be interpreted as “YES–NO,” “TRUE–FALSE,” “SIGNAL–NO
SIGNAL,” etc.
6.8.2Let 0 mean “FALSE” and 1 mean “TRUE.” LetAandBbe two state-
ments (which are either true or false). Express, using the operations⊕and·, the
truth of “not A,” “AorB,” “AandB.”
6.8.3Let the modulus be 6; show by an example that division by a nonzero
“number” cannot always be carried out. Generalize the example to every com-
posite modulus.
Division in modular arithmetic.Our argument that division in modu-
lar arithmetic can be carried out if the modulus is a prime was reasonably
simple but it did not tell us how to carry out the division. To find the quo-
tient by this method would involve looking at all numbers between 0 and
p−1, which was OK forp= 7, but would be quite tedious for a prime like
p= 234,527 (not to mention the really huge primes used in cryptography
and computer security, as we’ll see).
So how do we divide, say,53 by2 modulo 234,527?
We can simplify the problem, and just ask about dividing1by2 modulo
234,527. If we have that 1 /2=a, then we can get 53 /2= 53 ·a, which we
know how to compute.
At this point the proof can be explained better in the general case. We
are given a prime moduluspand an integera(1≤a≤p−1), and want to
find an integerx(0≤x≤p−1) such thatax=1. Using the congruence
notation from Section 6.7, we can write this as
ax≡1 (modp).