We got a least-residue question from David a few weeks ago, but never really took the time to address it properly. Here’s the bombshell David dropped us a bit earlier:

Find the

least positive residueof $\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!

Table of Contents

## 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$ (this is due to the fact that because $12$ is coprime with the 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$? 😉

## Method 2: 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}$), we have that $\,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 within *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 we have a *prime* modulus. In fact, we even know that the same theorem is *false* if the modulus were *composite*. and the search for more general techniques would lead us to yet another standard trick…

## Method 3: 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}$ and $a \equiv b \pmod{q}$ if and only if $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}\,$ 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$ in this case. 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}\,$ and $\, 12^{345} \equiv -1 \pmod{7}$. In addition, a bit of inspection would show that:

- $12^{345} \equiv 2+25 \equiv 27 \pmod{5}$
- $12^{345} \equiv -1+28 \equiv 27 \pmod{7}$

And since $27$ is our common number in both cases, by CRT, we must have that:

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

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

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

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

This is so impressive. When I started working as an Instructor in Mathematics last week, I had to attend a 2 hours lecture on Number Theory. The course is new at our college. I did some concepts in Abstract Algebra before the breakdown. I am now studying much on Number Theory. My love for Maths has been kindled so greatly. It’s now that I’m dreaming of doing my Masters in Pure Mathematics.

I feel like much of the discussions on the group will even help me in coming up with a research topic for my Masters. Will start applying shortly while studying.

Regards,

Omega Zomba, Malawi.

That’s wonderful Omega. Thanks for sharing!