Part of my series explaining the RSA Algorithm

Modular arithmetic is an important area of Number Theory. Here we’ll cover 4 important but slightly contrived laws of modular arithmetic, useful to understand when tackling other mathematical ideas which use modular arithmetic proofs, as we see in our exploration of Carmichael’s Function.

Notes:

• The | symbol means “divides without remainder”. So x|y is another way of writing y % x = 0.

• The greatest common divisor or GCD(x, y) is the largest number into which all provided integers divide without remainder.

• Two numbers which are coprime share no common divisors larger than 1. They are prime with respect to one another.

Rule 1

• IF GCD(a, b) = 1, i.e. a & b are coprime

• AND a|bc (remember this means bc % a = 0 )

• THEN a|c

Proof

Remember Bézout’s Identity, which we covered while discussing the Euclidean Algorithm? It states that for any 2 coprimes , a & b there must be values x & y that satisfy:

ax + by = 1

Therefore:

> multiply by `c`
acx + bcy = c

> acx divides by a
a|acx

> and because we stated that
a|bc

> so bcy must divide by a
a|bcy

> therefore divide both sides of the statement by `a`
acx/a + bcy/a = c/a

• Because a|acx, we know that acx/a is an integer.

• Because a|bcy we know that bcy/a is an integer.

So their sum, c/a, must also be an integer. Otherwise put, a|c. This is a logical extension of Euclid’s Lemma.

Rule 2

• IF GCD(a, n) = 1 (ie. coprimes)

• AND ax ≡ ay (mod n)

• THEN x ≡ y (mod n)

Proof

> IF
ax ≡ ay (mod n)

> THEN
(ax — ay) % n = 0

> Factor out `a`
a(x-y) % n = 0

> Put differently
n|a(x-y)

> Remember that `a` & `n` are coprime
> So applying Rule 1 from above
n|(x-y)

> Meaning that
x ≡ y (mod n)

This rule is known as the rule of cancellation in modular arithmetic.

Rule 3

• IF a & n are coprime

• THEN there is a positive integer k such that aᵏ≡ 1 (mod n)

Proof

There are a finite number of coprimes of n, less than n. Let’s assign this value to the letter t. So there are t coprimes of n which are less than n.

Given the list of numbers:

a¹, a², ..., aᵗ, aᵗ⁺¹ (each mod n)

We know a few things about the list.

• There only t + 1 numbers in the list.

• They are all coprime to n, because a is coprime to n, and no new factors have been introduced.

• They are all smaller than n, because each is mod n.

If there are only t coprimes to n less than n, and we have t + 1 coprimes less than n in this list, then we know at least two of the numbers in this list will clash – they will result in the same value. The list is not unique.

So we know there are two integers h & j, h < j, such that:

aʰ ≡ aʲ (mod n)

If k = j - h then:

> substitute out j
aʰ ≡ aʰ⁺ᵏ (mod n)

> separating exponents
aʰ ≡ aʰaᵏ (mod n)

We know already know that aʰ is a coprime of n. We can apply Rule #2 from above.

aʰ ≡ aʰaᵏ (mod n)

> cancel aʰ
1 ≡ aᵏ (mod n)

…proving that there must be some positive integer, k for any coprime of n, a such that aᵏ % n = 0.

Rule 4

• IF aᵏ ≡ 1 (mod n)

• AND r is a multiple of k

• aʳ≡ 1 (mod n)

Proof

Because r is a multiple of k there is some integer s where r/k = s.

aʳ = aᵏˢ = (aᵏ)ˢ

> We know that
aᵏ ≡ 1 (mod n)

> So
aʳ ≡ (aᵏ)ˢ ≡ (1)ˢ ≡ 1 (mod n)

In Summary

We’ve just shown the following:

1. If a & b are coprime, AND a|bc, THEN a|c

2. If a & b are coprime, AND ax ≡ ay (mod n), THEN x ≡ y (mod n)

3. If a & b are coprime, THEN there is a positive integer, k such that aᵏ≡ 1 (mod n)

4. If aᵏ ≡ 1 (mod n) AND r is a multiple of k THEN aʳ≡ 1 (mod n)

The first rule is not specific to modular arithmetic, although its use in proving the other rules makes it helpful to derive. These truths arise frequently when tackling proofs in number theory. They are a strong foundation for approaching any modular arithmetic problem.

You can see them applied to such a problem when we take a look at Carmichael’s Function.