Modular Arithmetic Part 5 (Finale)

Hello everyone, and welcome to the finale of my series on modular arithmetic! We will be proving a huge theorem, looking at its implications, and much, much more. So get ready as we explore modular arithmetic, one last time! Also, here are the links to the previous 4 blogs!

The theorem

The following are equivalent

a) A positive integer n<m has an inverse mod m

b) Row n in the multiplication table for mod m contains exactly one 1

c) Row n in the multiplication table for mod m contains all the integers from 0 to m-1 (inclusive) exactly once

d) n and m are relatively prime

The intuition

a) to b)

This is fairly trivial in the backwards direction, but we have to be careful about the forwards direction. While a doesn’t specify the number of inverses (could be 1, 2, or more), b specifies exactly 1.

b) to c)

The idea here is that since 1 appears in the multiplication table, lets say at column x, we can in a sense “move over” x columns to add 1, so we get 2. Repeat over and over again to get a proof! (Of course the backwards direction is trivial)

c) to d)

This is probably the least obvious. Even after you see the proof, the intuition here is not at all clear. If you want feel free to try and come up with your own proof of this fact! If you do make sure to send it to me so I can look. If you have an intuitive explanation of this also send it to me, and I will give credit and put it in place of this sentence! Anyways, let’s get on with the proof!

The Proof

(If you aren’t familiar with the idea of proof by contradiction, proof by induction, or proof by contrapositive check out these articles which explain the concepts well!)

Induction!

Contradiction!

Contrapositive!

a) to b)

Forwards

We know that at least 1 inverse exists, and we are trying to prove that exactly 1 exists, so disproving that 2 or more distinct inverses exist will be sufficient. So, assume 2 or more distinct inverses (x1 and x2) exist for contradiction. Then, we have:

1≡x1n≡x2n mod m

Now, clearly x1≡1x1. And since 1≡x2n, we have:

x1x2nx1x1nx21x2x2 mod m

Thus we have a contradiction, since we assumed these were distinct before. Thus there is exactly one 1 in row n of the multiplication table.

Backwards

Since there is a 1 in the nth row of the multiplication table, it follows that nx1 mod m for some x in the integers. Thus, n has an inverse.

b) to c)

Forwards

We will prove this via induction:

Base Case

The row includes 1, by b).

Inductive step

Assume that the row includes l in the jth column. This means that njl mod m. Then, let o be the column in which 1 appears in that row. This means that no1 mod m. Adding the equations we get:

no+njn(o+j)l+1 mod m

Thus the row includes l+1, and thus b implies c.

Backwards

This is quite trivial, as c) implies a) since there is a 1 in the column, and a) implies b) so c) implies b).

c) to d)

Forwards

We will use contrapositive, i.e. not d implies not c, i.e. if m and n are not relatively prime, then the nth row of the multiplication table mod m does not go through all the numbers (0 to m-1) exactly once. To start, note that if m and n are not relatively prime, they share a common (integer) factor f>1. Thus, we have n(m/f)m(n/f)0n0 mod m, which means that 0 does not appear exactly once, rather twice or more.

Backwards

We will once again use contrapositive, i.e. not c implies not d, i.e. if the nth row of the multiplication table mod m does not go through all the numbers (0 to m-1) exactly once, then m and n are not relatively prime. To start, if there is not a repeated number, then since there are exactly m slots in the row, and exactly m numbers to fill said row, our hypothesis will not be true. Thus, at least 1 number is repeated, or in equation form, there exists 2 distinct integers x1, and x2, such that:

x1n≡x2n mod m

This means that:

x1n-x2n≡0 mod m

We can rewrite this outside modular arithmetic as:

x1n-x2n=km for some natural number k

n(x1-x2)=km

Now, assume for contradiction the m and n are relatively prime. Then, x1-x2 must be a multiple of m. Rewriting this in modular arithmetic, we get:

x1-x2≡0 mod m

x1x2 mod m

But since we assumed the the 2 were distinct, we have a contradiction, thus m and n are not relatively prime, and the theorem is proven.

Side notes and final thoughts

After looking at modular arithmetic from a purely mathematical point of view, you might think that it has no applications in reality, but that is far from the truth. It has applications in parts of number theory at the heart of cryptography, and is overall great at dealing with big numbers. The theorem we proved, while being pure in nature, gives a lesson in both proof, and in the art and behavior of modular arithmetic. On another note, it is very helpful in competition math all the way through Olympiad level, and can show up in many surprising places. And with that, I conclude my series on modular arithmetic. There might be a prologue coming soon about applications, so look for that! See you next time, bye!

5 comments

  1. In the proof c)to d)forwards ” if m and n are not relatively prime, they share a common (integer) factor f>1. Thus, for some integer k, nf≡mk≡0≡m0 mod m” does not look true to me. (Consider the counter example, n=12, m=15, and f=3.)
    But n(m/f)=m(n/f)≡0 mod m and m/f is a natural number less than m do imply that 0 appears more than once in row n.

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.