5Modular arithmetic
IA Numbers and Sets
5 Modular arithmetic
We are going to study modular arithmetic. In modular arithmetic, we first pick
a particular natural number to be the modulus, say 7. Then we consider two
numbers to be “equal” if their difference is a multiple of the modulus. For
example, modulo 7, we will think that 3 and 10 are “the same”, while 2 and 4
are different.
We will study arithmetic under this number system. Like the integers, we
are allowed to add and multiply numbers. However, while in
Z
, we can only
divide by 1 and -1, in modular arithmetic, more numbers can be divided. For
example, modulo 10, we are allowed to divide by 3.
An important application of modular arithmetic is RSA encryption. This is
a widely deployed asymmetric encryption algorithm. By asymmetric, we mean
that the key for encryption is different from the key for decryption. This is very
useful in real life, since we can broadcast the encryption key to the world, and
keep the decryption key to ourselves. This way anyone can send you encrypted
messages that only you can decrypt.