Introduction to Modular Arithmetic, Part 3
In this part, we will confirm that modular arithmetic works well with sums and products, as claimed in Part 1. We'll also have a look at powers (where a little care is needed). [Actually, powers will be postponed until Part 3b.]
So, we start by showing that our operations of addition and multiplication are 'consistent' with congruence modulo \(k\) (for positive integers \(k\)). In the curiously named Lecture 9b of my first-year pure maths module (FPM) the result I prove is the following. For convenience (non-standard) let's call this the Modular Arithmetic Consistency Theorem, or MACT for short.
Here \(\mathbb{Z}\) is the set of all integers (positive, negative or zero) and, for us, \(\mathbb{N}\) is the set \(\{1,2,3,\dots\}\) of all positive integers. So in the MACT, \(k\) is a positive integer, while \(a_1\), \(b_1\), \(a_2\) and \(b_2\) are integers which need not be positive.
The MACT is fairly easy to prove directly, and that is what I do in my lecture. But just for a change let me state an even easier result, which we can use to prove the MACT in two steps. We'll call it a lemma. (A lemma is often a preliminary result that you prove along the way to proving a more important theorem.)
Lemma
Let \(k\) be a positive integer, and let \(a_1\), \(a_2\) and \(b\) be integers. Suppose that \(a_1\equiv a_2~~(\mathrm{mod}~k)\). Then
\(a_1+b \equiv a_2+b ~~(\mathrm{mod}~k)\) and \(a_1b \equiv a_2b ~~(\mathrm{mod}~k)\).
Comment: Since addition and multiplication are commutative, under the conditions of the lemma we also have
\(b + a_1 \equiv b + a_2~~(\mathrm{mod}~k)\) and \(b a_1 \equiv b a_2 ~~(\mathrm{mod}~k)\,.\)
And of course, we can change the variable names in the lemma for more general use.
Once we have this lemma, we can prove the MACT as follows.
Under the conditions of the MACT, the lemma tells us first that \(a_1 + b_1 \equiv a_2+b_1 ~~(\mathrm{mod}~k)\) and that \(a_1 b_1 \equiv a_2 b_1 ~~(\mathrm{mod}~k)\).
Then (see the comment after the lemma), the lemma also gives us that \(a_2 + b_1 \equiv a_2+b_2 ~~(\mathrm{mod}~k)\) and that \(a_2 b_1 \equiv a_2 b_2 ~~(\mathrm{mod}~k)\).
Combining all of this with transitivity (see Part 2), we obtain the full version of the MACT.
That is all well and good, but we shouldn't forget to prove the lemma!
Proof of the lemma
Under the conditions of the lemma, we have \(a_1\equiv a_2~~(\mathrm{mod}~k)\), which means that \(a_1-a_2\) is divisible by \(k\).
For the sum, we need to show that \(a_1+b \equiv a_2+b ~~(\mathrm{mod}~k)\), i.e., that \((a_1+b)-(a_2+b)\) is divisible by \(k\). But this is rather quick, because \((a_1+b)-(a_2+b) = a_1-a_2\), and we already know that this is divisible by \(k\), so the result is immediate.
For the product, we need to show that \(a_1b \equiv a_2 b ~~(\mathrm{mod}~k)\), i.e., that \(a_1b-a_2b\) is divisible by \(k\). Now, we have \(a_1b-a_2b = (a_1-a_2)b\), and you probably already know that if you multiply a multiple of \(k\) by an integer, then you obtain another multiple of \(k\). But let's just check this carefully using the elementary definitions and assumptions we are using (see Part 2).
Since \(a_1-a_2\) is divisible by \(k\), our elementary definition of divisibility tells us that \(\dfrac{a_1-a_2}k\) is an integer. Then we have
\(\dfrac{(a_1-a_2)b}{k} = \dfrac{a_1-a_2}k \, b\,\),
and this is a product of two integers, so it is still an integer. Thus \((a_1-a_2)b\) is divisible by \(k\), i.e., \(a_1b-a_2b\) is divisible by \(k\), and that is exactly what we needed to finish the proof.
I did say that I would look at powers in this post, but ... well, it's getting late, so I'll postpone powers to what I will call Part 3b.
Comments
Post a Comment