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!

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$? 😉

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}$!

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…

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? 😉

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!

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?)

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! 🙂

**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. :)

Desmos: A Definitive Guide (How to Perform Cool Computations and Creating Great Graphs Using Online Graphing Calculator)

Infinite Limits and the Behaviors of Polynomials at the Infinities — A Theoretical Musing

The Ultimate Guide to Logarithm: Basic Theory Commonly Missed in High School Which Turns a Log Noob into a Log Whiz

Quadratic Factorisation — A General Method that Conquers Each and Every Quadratic Trinomial

Add Your Reply