Mathematics Appendix - Everyday Cryptography - page 502

We will also need the following idea later. Suppose that we know that a positive
integer a takes the value r modulo n . In other words, we know that when we divide
a by n we get the remainder r . This tells us is that it is possible to write a as:
a

,
for some number k . We do not necessarily know what k is, but there must be a
k for which this is true. Returning to our previous example, knowing that 5417
takes the value 6 modulo 7 allows us to claim that:
5417

= ( k × n ) + r

,
for some number k (in fact it is easy to work out, in this case, that k

= ( k × 7) + 6

= 773).

TERMINOLOGY AND NOTATION
We have kept our terminology as simple as possible. However, other texts may
explain modular arithmetic in a slightly different language. For example, the
process of calculating one number modulo another is sometimes called modular
reduction . Thus we might say that 5417 reduces to 6 modulo 7. Also, just to make
sure that it is recognised that a modular reduction has taken place, often the
symbol ≡ is used instead of = . Thus we would write 5417 ≡ 6mod 7 rather than

5417 6mod 7. This idea is often expressed by stating that 5417 is congruent to

6 modulo 7.
Note that while 5417 is congruent to 6 mod 7, it is also congruent to 13 mod 7,
and 20 mod 7. In fact it is congruent to any multiple of 7 with 6 added. However,
when asked 'what number is congruent to 5417 mod 7?', there will only be one
answer that lies between 0 and 6. This is the default answer, and usually the most
useful one.

=

NEGATIVE MODULAR NUMBERS
We can also work with negative numbers in modular arithmetic. These behave
almost the same way. To start with, we can regard any negative multiple of
the modulus n as being equal to 0 modulo n . In other words, 14 are

both equal to 0 modulo 7. More generally, any negative integer can be uniquely
expressed as a number modulo n . For example, suppose that we wish to compute
−

− 7 and −

17 by 10 and take the remainder. When we do this we
need to have a positive remainder because our answer modulo 10 must be one of
the numbers between 0 and 9. Thus we see that:
−

17mod 10. We divide −

17 = ( − 2 × 10) + 3 .

In other words:

− 17 = 3mod 10 .

A.2.3 Modular arithmetic operations

We now consider how to compute basic arithmetic operations modulo n .