Modular Arithmetic: 4 Important Truths
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”. Sox|y
is another way of writingy % 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 meansbc % 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 thatacx/a
is an integer. - Because
a|bcy
we know thatbcy/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 thataᵏ≡ 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
, becausea
is coprime ton
, and no new factors have been introduced. - They are all smaller than
n
, because each ismod 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 ofk
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:
- If
a
&b
are coprime, ANDa|bc
, THENa|c
- If
a
&b
are coprime, ANDax ≡ ay (mod n)
, THENx ≡ y (mod n)
- If
a
&b
are coprime, THEN there is a positive integer,k
such thataᵏ≡ 1 (mod n)
- If
aᵏ ≡ 1 (mod n)
ANDr
is a multiple ofk
THENaʳ≡ 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.
More ?
I write the world’s shortest newsletter. One quick thing I’ve learned or seen or read in the week, each Wednesday.
I want it to be the most accessible, to-the-point newsletter you receive.
It might be worth giving a try. Unsubscribing is easy too.
It’s called <One More Thing>. See you there!