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!)
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:
x1≡x2nx1≡x1nx2≡1x2≡x2 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 nx≡1 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 nj≡l mod m. Then, let o be the column in which 1 appears in that row. This means that no≡1 mod m. Adding the equations we get:
no+nj≡n(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)≡0≡n0 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
x1≡x2 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!
Nice!
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.
I will fix that soon! I’m kind of busy today, but I should be able to get to it by tommorow.
All fixed!