Introduction to Modular Arithmetic, Part 3b
In this post we'll look at some applications of the result from last time that we gave the non-standard name Modular Arithmetic Consistency Theorem, or MACT for short. In particular, we will finally have a proper look at powers of integers.
Theorem (MACT)
Let \(k\) be a positive integer, and let \(a_1\), \(b_1\), \(a_2\) and \(b_2\) be integers. Suppose that \(a_1\equiv a_2~~(\mathrm{mod}~k)\) and \(b_1\equiv b_2~~(\mathrm{mod}~k)\). Then
\(a_1+b_1 \equiv a_2+b_2 ~~(\mathrm{mod}~k)~~~ \textrm{and}~~~ a_1b_1 \equiv a_2b_2 ~~(\mathrm{mod}~k)\,.\)
Warning! You can't expect anyone else to know what this so-called MACT is, so if you want to use the name MACT in your work, you will need to explain which result it is that you are calling the MACT. (However you can usually use it implicitly in your working without actually naming it. The standard official name might be a bit long: Consistency of the equivalence relation congruence modulo \(k\) with the operations of addition and multiplication.)
Before looking at powers, let's first see how the MACT can help us to simplify the task of calculating remainders when dividing by positive integers.
Question: Consider the integer \(m= 26 \times 25 \times 243 - 13 \times 17 \times 31\). What is the remainder when you divide \(m\) by \(8\)?
Answer: Obviously you could multiply out these numbers, subtract, and then divide by \(8\) in order to find the remainder. Or you can type this into Google. However, here is a quick way to work this out by hand.
Let's work modulo \(8\). Then we can easily see that \(26 \equiv 2\), \(25 \equiv 1\), \(243 \equiv 3\), \(13 \equiv 5\), \(17 \equiv 1\) and \(31 \equiv {-1}\), all modulo \(8\).
How does this help? Well, using the MACT, when multiplying or adding we can replace integers by any other integers that are congruent to them modulo \(8\) in order to simplify the calculation, and the result will remain congruent to the original result modulo \(8\). Subtraction is also fine, since it is just the same as adding \({-1}\) times the number. Using the MACT (repeatedly, but we don't have to say how often!), we have
\(m= 26 \times 25 \times 243 - 13 \times 17 \times 31 \equiv 2 \times 1 \times 3 - 5 \times 1 \times (-1)~~(\mathrm{mod}~8)\,.\)
The rest of the calculation is easy:
\(2 \times 1 \times 3 - 5 \times 1 \times (-1) =6 - (-5) = 11 \equiv 3 ~~(\mathrm{mod}~8)\,.\)
Putting everything together (here we implicitly use both transitivity and the fact that equality implies congruence modulo \(8\)) we have
\(m \equiv 3 ~~(\mathrm{mod}~8)\)
and so the remainder when we divide \(m\) by \(8\) is \(3\).
In fact, we have \(m=151099\), and you can now easily divide by \(8\), or type 151099 mod 8 into Google, or indeed you can type (26*25*243 - 13*17*31) mod 8 into Google, to confirm that the remainder really is \(3\).
Now let's have our long-promised look at powers of integers. If you look back at Part 1, you'll see the kind of thing we want to do. For example, we want to be able to say things like
\(53^{100} - 55^{201} \equiv (-1)^{100}-1^{201} = 1-1 =0 ~~(\mathrm{mod}~27)\)
and so \(53^{100} - 55^{201}\) is divisible by \(27\).
This isn't so far removed from what we did with the MACT. It is easy to see that \(53 \equiv {-1} ~~(\mathrm{mod}~27)\) and that \(55 \equiv 1 ~~(\mathrm{mod}~27)\), so all we have done is replace some integers by integers that are congruent to them modulo \(27\). Also, it is true that an integer is divisible by \(27\) if and only if it is congruent to \(0\) modulo \(27\).
Major Warning! Although, as we will see, it is fine to replace in this way the integers which are being raised to some positive integer powers, it is not OK to replace the powers that you are raising your integers to (the exponents or indices), or at least not in the same way. To see how this can go wrong we can simply look at powers of \(-1\) modulo \(7\) (where I chose \(7\) because it is odd).
Consider \((-1)^3=-1\) and \((-1)^{10}=1\). Now, \(-1\) is not congruent to \(1\) modulo \(7\), and so \((-1)^3\) is not congruent to \((-1)^{10}\) modulo \(7\), even though \(3 \equiv 10~~(\mathrm{mod}~7).\)
We will return later to see what you are allowed to do with the powers/exponents/indices. But for now, let's finish by showing that it really is OK to replace the integer that is being raised to a positive integer power. The result we need is the following.
Lemma
Let \(k\) be a positive integer, and let \(a\) and \(b\) be integers such that
\(a \equiv b ~~(\mathrm{mod}~k)\,.\)
Then, for all positive integers \(n\), we have
\(a^n \equiv b^n ~~(\mathrm{mod}~k)\,.\)
I usually prove this lemma by repeatedly applying the MACT, so implicitly by induction. Since
\(a \equiv b ~~(\mathrm{mod}~k)\,,\)
the MACT gives us that
\(a \times a \equiv b \times b ~~(\mathrm{mod}~k)\,,\)
i.e.,
\(a^2 \equiv b^2 ~~(\mathrm{mod}~k)\,.\)
Then applying the MACT again gives us that
\(a^2 \times a \equiv b^2 \times b~~(\mathrm{mod}~k)\,,\)
i.e.,
\(a^3 \equiv b^3 ~~(\mathrm{mod}~k)\,,\)
and so on. In later years I would just say something like
'An easy proof by induction shows that \(a^n \equiv b^n ~~(\mathrm{mod}~k)\,,\) for all positive integers \(n\).'
However, in first year we do like to do proofs by induction more formally.
Exercise: Write this out as a formal proof by induction.
Here is an alternative proof based on factorization.
We are given that \(a \equiv b ~~(\mathrm{mod}~k)\,\), i.e., \(a - b\) is divisible by \(k\).
Now let \(n\) be a positive integer. We can factorize \(a^n-b^n\) in a standard way:
\(a^n-b^n = (a-b)(a^{n-1}+a^{n-2} b +\cdots+a b^{n-2} +b^{n-1})\,.\)
Then, since \(a-b\) is divisible by \(k\), so is \(a^n-b^n\) (as it is an integer times a multiple of \(k\)). Thus \(a^n \equiv b^n ~~(\mathrm{mod}~k)\,,\) as required.
That's enough for now! To be continued ...
Comments
Post a Comment