Modular Arithmetic — Some Advanced Tricks in Finding The Least Positive Residue

By mathvault | Abstract Algebra

Modular arithmetic, Chinese Remainder Theorem, Fermat's Little Theorem, McGill Concordia Math Tutoring, MATH 235, MATH 240

We got a least-residue question from David a few weeks ago, but never took the time to address it properly. While procrastination and busyness can take a toll on us, at some point one still needs to face the reality and get things done promptly (don’t you think, students? 😉 ). OK. Enough said. Here’s the bombshell David dropped us:

Find the least positive residue of $\displaystyle 12^{345}$ in mod 35.

Wow. That seems like a huge number. How on earth do you reduce it to a positive number below $35$? Well, read on!

Method 1: Brute-Force Attack

Without any sophisticated mathematical machinery, the conceptually-easiest approach is just to calculate the powers of 12 — incrementally — until we get to $12^{345}$. Sounds easy enough? Let’s jump in and give it a try!

$12^2 \equiv 144 \equiv 144-4(35) \equiv 4 \pmod{35}$

$12^3 \equiv (12^2)12 \equiv (4)12 \equiv 48 \equiv 13 \pmod{35}$

$12^4 \equiv {(12^2)}^2 \equiv 4^2 \equiv 16 \pmod{35}$

$12^5 \equiv (12^3)12^2 \equiv (13)4 \equiv 52 \equiv 17 \pmod{35}$

$12^6 \equiv (12^2)(12^2)(12^2) \equiv (4)(4)(4) \equiv 64 \equiv -6 \pmod{35}$

$12^7 \equiv (12^6)12 \equiv (-6)12 \equiv -72 \equiv -2 \pmod{35}$

Ouf… Finally we get some small numbers!  Can we do better though? Yes! In fact, we can prove that in this case, we will eventually get to 1 (and we’ll tell you why: it’s because 12 is coprime with our modulus 35). However, there is a catch — we actually don’t know when that will happen! We can, of course, proceed with computations and just pray for its prompt occurrence:

$12^8 \equiv (12^7)12 \equiv (-2)12 \equiv -24 \equiv 11 \pmod{35}$

$12^9 \equiv (12^7)(12^2) \equiv (-2)(4) \equiv -8 \pmod{35}$

$12^{10} \equiv (12^7)(12^3) \equiv (-2)(13) \equiv -26 \equiv 9 \pmod{35}$

$12^{11} \equiv (12^7)(12^4) \equiv (-2)(16) \equiv -32 \equiv 3 \pmod{35}$

$12^{12} \equiv (12^{11})12 \equiv (3)12 \equiv 36 \equiv 1 \pmod{35}$

Thank Goodness! Looks like that we are lucky this time! By the way, there is a reason why we didn’t skip the exponents (for example, we could have calculated $12^8$ from $12^4$ directly quite easily), but let’s solve our original question first shall we?

$12^{345} \equiv 12^{12(28)+9} \equiv {(12^{12})}^{28}12^9 \equiv (1)^{28}(-8) \equiv -8 \equiv 27 \pmod{35}$

See… if we skipped the exponents, would we have known that $12^9 \equiv -8$? 😉

Standard Trick 1: Fermat’s Little Theorem

There are several ways to deal with large exponents more efficiently, one of which is to leverage the so-called Fermat’s Little Theorem (FLT), which asserts that:

Given a prime modulus $p$ and any non-zero integer $n$ (i.e., $n \not\equiv 0 \pmod{p}$), $n^{p-1} \equiv 1 \pmod{p}$.

In other words, when the modulus is a prime number, any non-zero number, when raised to the predecessor of the modulus, will be congruent to 1. While FLT has profound implications in number theory, its immediate usefulness for us is that it allows for fast calculations in prime moduli.

For example, since 31 is a prime number, any non-zero number raised to 30 will be congruent to 1 in mod 31 (e.g., $2^{30} \equiv 1 \pmod{31}$, $15^{30} \equiv 1 \pmod{31}$). In practice, this means that a big number such as $234^{567}$ can be reduced in mod 31 as follows:

$234^{567} \equiv \left[ (31)7+17 \right]^{567} \equiv 17^{567} \equiv 17^{(30)18+27} \equiv (17^{30})^{18}17^{27} \equiv 17^{27} \pmod{31}$

As you can see here, in the case of prime modulus, the base can always be reduced so that it is smaller than the modulus, and the exponent smaller than the predecessor of the modulus. Once there, we can resort again to brute force to further simplify the expression:

$17^2 \equiv 289 \equiv 10$, $17^4 \equiv 100 \equiv 7$, $17^8 \equiv 49 \equiv 18 \pmod{31}$

$17^{16} \equiv 324 \equiv 14$, $17^{24} \equiv (17^{16})17^8 \equiv (14)18 \equiv 4 \pmod{31}$

$17^{26} \equiv (17^{24})17^2 \equiv (4)10 \equiv 9 \pmod{31}$

$\therefore 17^{27} \equiv (17^{26})17 \equiv (9)17 \equiv 153 \equiv 29 \pmod{31}$

That is, $234^{567} \equiv 29 \pmod{31}$!

McGill / Concordia Math Tutoring, MATH 235, MATh 240, Modular Arithmetic, Find the Least Positive Residue

Think of it this way: even Google can’t compute what we just did!

Before we get overly excited about FLT though, it is to be emphasized that this theorem only works when you have a prime modulus. In fact, we even know that the same theorem is false if the modulus were unprime (if that’s even a word), and as we search for a more general technique that caters to other moduli, we would naturally stumble upon the following hack…

Standard Trick 2: Chinese Remainder Theorem

In a nutshell, the simple version of Chinese Remainder Theorem (CRT) asserts that:

Given $\displaystyle a$, $\displaystyle b$ and two coprime moduli $p$ and $q$, $a \equiv b \pmod{p}\text{ and }a \equiv b \pmod{q} \Leftrightarrow a \equiv b \pmod{pq}$

What that means in practice, is that we can break down a hard residue question into 2 easier residue questions. For example, we can find the residue of, say, $2^{10}$ in mod 15, by finding its residues in mod 3 and mod 5 (which are coprime) first instead:

$2^{10} \equiv (-1)^{10} \equiv 1 \pmod{3}$, $2^{10} \equiv 4^5 \equiv (-1)^5 \equiv -1 \pmod{5}$.

By inspection, $2^{10} \equiv 4 \pmod{3}\text{ and }2^{10} \equiv 4 \pmod{5}$, so $2^{10} \equiv 4 \pmod{15}$.

So the least positive residue of $2^{10}$ would be 4 then. By the way, did you see where the theorem was invoked? 😉

Revisiting David’s Question

Now that we cover a bunch of tricks in modular arithmetic, can we leverage them to solve our original question (i.e., simplifying $12^{345}$ in mod 35) in less steps? Well, you bet!

Step 1: Setting Up for CRT — Breaking Down The Modulus

Note that the modulus 35 can be factored into 5 and 7 (which are coprime), so let’s work on the residues in mod 5 and mod 7 first:

$12^{345} \equiv 2^{345} \equiv 2^{(4)86+1} \equiv 2 \pmod{5}$

$12^{345} \equiv (-2)^{345} \equiv (-2)^{(6)57+3} \equiv (-2)^3 \equiv -1 \pmod{7}$

(notice that Fermat’s Little Theorem was invoked twice?)

Step 2: Finding the Common Number and Invoking CRT

So $12^{345} \equiv 2 \pmod{5}\text{ and }12^{345} \equiv -1 \pmod{7}$. In addition, a bit of inspection shows that $12^{345} \equiv 2+25 \equiv 27 \pmod{5}$, and that $12^{345} \equiv -1+28 \equiv 27 \pmod{7}$ (i.e., 27 is our common number). Therefore, by CRT:

$12^{345} \equiv 27 \pmod{35}$

which, as expected, matches the previous result we’ve obtained through brute force! 🙂

Follow

About the Author

Math Vault and its Redditbots has the singular goal of advocating for education in higher mathematics through digital publishing and the uncanny use of technologies. Head to the Vault for more math cookies. :)

(2) comments

Add Your Reply