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 really took the time to address it properly. Here’s the bombshell David dropped us a bit earlier:

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