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

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.

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

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 obtained through brute force . ðŸ™‚

Chow Kim Wan

July 20, 2015 @ 10:15 pm

This seems like a typical math olympiad problem. Maybe I could share more of these on my Math features.

Math Vault

July 21, 2015 @ 6:30 pm

Hehe… we are by no means Math Olympians, we just happen to tutor/teach undergrad and graduate students. Looking forward to post more stuffs of the like on a regular basis as well – depending on our availabilities of course! ðŸ˜‰