LECTURE 3 - MODULAR ARITHMETIC
RONI EDWIN
1. Modular arithmetic
We write a ≡b mod m to mean a −b is divisible by m. Equivalently, a and b
have
the same remainder upon division by m. For example, 3 ≡1 mod 2, and 13 ≡3
mod 5. We will now go over the basic rules of arithmetic applied to modular
arithmetic. So
addition, subtraction, multiplication, and division.
Rules of arithmetic.
Addition. Addition works similar like it does in regular arithmetic. That is, if a ≡
b mod m and c ≡d mod m, then
a + c ≡b + d mod m.
For example, 8 ≡3 mod 5, and 34 ≡4 mod 5, so 8 + 34 = 42 ≡3 + 4 = 7 mod 5.
Multiplication. Multiplication is quite similar: If if a ≡b mod m and c ≡d mod m,
then
ac ≡bd mod m.
Also, we have a ≡b mod m, then ak ≡bk mod m. Why is this true? If a ≡b mod m,
then by definition, a −b is divisible by m, so we can write a −b = mc for some
integer c. Multiplying both sides by k, we get ak −bk = mkc so ak −bk is
divisible by mk, so ak ≡bk mod mk.
Division. Division is a little more complicated. There’s two variations we might con-
sider. The first is when we have something like
ak ≡bk mod m.
We might be tempted to simplify this to a ≡b mod m, but this implication is not
necessarily true. As an example, 21 ≡7 mod 7, but dividing both sides by 7, 3
≡
̸ 1 mod 7. The actual rule is as follows:
Proposition 1.1. If ak ≡bk mod m, then
m
a ≡b mod gcd(m,
k).
1
2 RONI EDWIN
To understand why this is true, let’s consider the case where m and k are
coprime,
so gcd(m, k) = 1 (The general case follows from this). Consider how you would
solve the equation ak = bk in regular algebra. You would typically multiply both
sides by1 k,
to get a = b. Importantly, the number c =1 ksatisfies kc = 1. There is a similar
idea in modular arithmetic, called an inverse:
Inverses. A modular inverse of a number (or residue) a, modulo m, is another
residue
or number b such that ab ≡1 mod m. For example, the inverse of 7 modulo 5
is 3, since 7·3 = 21 ≡1 mod 5. Usually, we will write a−1mod m to denote the
inverse of a modulo m (usually the modulus/divisor will be clear from context),
so a·a−1≡1 mod m. Some things you should know:
• Modular inverses if they exist, are unique. That is, if both b and b′are
inverses
for a modulo m, so ab ≡ab′≡1 mod m, then b ≡b′.
• If b is the modular inverse of a, then a is the modular inverse of b.
Some examples:
(1) 4−1≡7 mod 9, since, 7 · 4 = 28 ≡1 mod
9, (2) 5−1≡7 mod 17, since 5 · 7 = 35 ≡1
mod 17.
Note modular inverses may not always exists. For example, 6 has no inverse
modulo
18: Suppose for the sake of contradiction 6 has an inverse modulo 14, so there is an
integer b ∈{0, 1, ..., 13} such that 6b ≡1 mod 14. We can write this as 6b −1 =
14k
for some integer k, which implies 1 = 6b −14k. But this impossible, since 2
divides the right-hand side, but 1 is odd: The following rule tells us exactly when
a−1mod m
exists:
Proposition 1.2. a−1mod m (the modular inverse of a mod m) exists if and only if
gcd(a, m) = 1.
The nice thing about modular inverses is that we can use them to solve
congruence
equations and also diophantine equations:
Example 1.3. Solve the equation 3x −7 ≡10 mod 13.
Solution. Adding 7 to both sides implies 3x ≡17 mod 13, or
3x ≡4 mod 13 (1.1)
Since gcd(3, 13) = 1, we know 3−1mod 13 exists.
Via trial-and-error, we see that
3 · 9 −1 = 26 = 2 · 13, so we can take 3−1≡9 mod 13. So multiplying both sides
of (1.1) by 9, we get x ≡4 · 9 = 36 ≡−3 mod 13, so x ≡−3 mod 13. □
We can also use it to find solutions to diophantine equations:
Example 1.4. Find a solution to the diophantine equation 8x −6y = 22.
LECTURE 3 3
Solution. We note gcd(6, 8) = 2, so dividing both sides by 2, we get 4x−3y = 11,
which
we rewrite as 4x −11 = 3y, or
4x ≡11 mod 3. (1.2)
We can note 4 ≡1 mod 3, so we can take x ≡11 ≡1 mod 3, so taking x = 1, we
get y = −6. □
Now we talk about powers.
Powers. The first thing to bear in mind is that we can replace the base of a power
with
a congruent number, since powers are just a way of representing repeated
multiplication. For example, 5 ≡2 mod 3, so 5n≡2nmod 3. However, replacing
the index does not always work: For example, 5 ≡2 mod 3, but 25≡ ̸ 23mod 3.
Tricks and tools. Here we will review some tools for working with modular
arithmetic:
The first is as follows:
Proposition 1.5. If a ≡b mod m and n divides m, then a ≡b mod n.
This is not too hard to see. If a ≡b mod m, then we can write a −b = mk. Since
n
divides m, we can write m = nk′, so we get a −b = nk′k, which implies a ≡b
mod m. The next is as follows:
Proposition 1.6. Suppose a ≡b mod m and a ≡b mod ℓ, with gcd(m, ℓ) = 1. Then
a ≡b mod mℓ.
For example, 13 ≡3 mod 2, and 13 ≡3 mod 5. Since gcd(2, 5) = 1, this implies
13 ≡3 mod 10. This is most likely going to be most useful when finding modular
inverses.
