# $158^{158} \pmod {31}$

Trying to brush up on my modular arithmetic, and came across this problem.

Calculate $158^{158} \pmod {31}$.

Using the rule $a^b \pmod c = (a\pmod c)^b \pmod c$ I was able to reduce it to $3^{158} \pmod{31}$, which should be the same.

But from here, I'm stumped.

Which rule can I use to progress here? Or is there some immediately obvious solution already?

Thanks in advance for any help!

• By Fermat's little theorem, $3^{30}\equiv1\pmod{31}$. Dec 17, 2017 at 21:09
• @JyrkiLahtonen Not me...I don't even know what an "umbrella thread" is, and even more important: searching for a question as simple as this in the rather cumbersome archive of questions/answers usually takes more time than answering the question directly. Dec 17, 2017 at 21:30
• @JyrkiLahtonen - I will keep that question/answer in mind for next time, but I would argue that going through all the answers in that thread looking for the path would take a significantly longer time than it did the guys in this thread to post good answers to this problem in particular. I'm not saying that lengthy lookups should always be avoided - in fact, there's a lot to learn there - but I definitely appreciate the conciseness of succinct and to-the-point answers to concrete problems.
– Alec
Dec 17, 2017 at 21:36
• @DonAntonio Locating this meta thread takes less than 10 seconds if you favorite it. Using it is just scrolling down the list. I am known to be a bit more militant than average about it, but I strongly feel that replicating calculations like this is not useful for the site. Anyway, I won't vote to close/delete threads like this, because my view is not supported by all. Dec 17, 2017 at 21:54

Since $158\equiv3\pmod{31}$, you have to compute $3^{158}\pmod{31}$. You know (Fermat's little theorem) that $3^{30}\equiv1\pmod{31}$. Since $158\equiv8\pmod{30}$, you have to compute $3^8\pmod{31}$. But $3^4=81\equiv19\equiv-12\pmod{31}$, and therefore $3^8\equiv144\equiv20\pmod{31}$.

Since $31$ is prime, you have that $a^{30} \equiv 1 \textrm{ (mod } 31)$ for $a \not \equiv 0 \textrm{ (mod } 31)$. Here of course we take $a = 3$. Now observe that $3^{158} = 3^{5 \cdot 30 + 8} = (3^{30})^5 \cdot 3^8$, and now taking the modulus we find that $3^{158} \equiv 1 \cdot 3^8 \textrm{ (mod } 31) \equiv 3^8 \textrm{ (mod } 31)$. Now $3^8 \textrm{ (mod } 31)$ isn't a hard calculation and results in $20 \textrm{ (mod } 31)$, and thus we find that $$158^{158} \equiv 20 \textrm{ (mod } 31)$$

By FLT:

$$158^{30}\equiv 1\pmod {31}$$

thus:

$$158^{158}\equiv 158^{8}\equiv3^8\equiv9(-4)^2\equiv20\pmod {31}$$

Fermat's Little Theorem (extension):

$$3^{31}=3\pmod{31}\stackrel{\text{arit. mod}\,31}\implies 3^{158}=\left(3^{31}\right)^5\cdot 3^3=3^8=\left(3^4\right)^2=(-12)^2=20$$

• That's not what I get $\ddot\frown$ Dec 17, 2017 at 21:13
• ahh, you just miscalculated $158-155 = 3$ and not $1$ Dec 17, 2017 at 21:16
• Surely $3^{158}$ should equal $3^{31\times5+3}$ not $3^{31\times5+1}$?
– Jam
Dec 17, 2017 at 21:16