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.