2
$\begingroup$

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!

$\endgroup$
5
  • 7
    $\begingroup$ By Fermat's little theorem, $3^{30}\equiv1\pmod{31}$. $\endgroup$ Dec 17, 2017 at 21:09
  • 1
    $\begingroup$ Somebody tell why this is not a duplicate??? :-( All half experienced answerers surely know about this umbrella thread. $\endgroup$ Dec 17, 2017 at 21:21
  • $\begingroup$ @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. $\endgroup$
    – DonAntonio
    Dec 17, 2017 at 21:30
  • 2
    $\begingroup$ @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. $\endgroup$
    – Alec
    Dec 17, 2017 at 21:36
  • $\begingroup$ @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. $\endgroup$ Dec 17, 2017 at 21:54

4 Answers 4

2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

By FLT:

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

thus:

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

$\endgroup$
0
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .