Hello I'm having some issues when trying to calculate big exponents(without the help of a calculator)

Let's say I have the following question

\((46)^{27} = n \text{(mod 27)}\)

Suppose you have to solve for the smallest natural number solution n, how would you go about doing that? I gave a shot and I'm not sure if I got it correct by sheer luck or if my methods were correct.

I ended up having to use a calculator at the (-8)^3 part as I wasn't sure how to solve for that in any other way than brute forcing it. Thanks in advance!

Quazars
Feb 28, 2017

#1**+11 **

**I gave a shot and I'm not sure if I got it correct by sheer luck or if my methods were correct.**

Your methods are correct.

**I ended up having to use a calculator at the (-8)^3 part as I wasn't sure how to solve for that in any other way than brute forcing it.**

\(\begin{array}{|rcll|} \hline &&(-8)^3 \pmod {27} \\ &\equiv& (-8)^2\cdot(-8) \pmod {27} \\ &\equiv& 64\cdot(-8) \pmod {27} \quad & | \quad 64 \pmod {27} \equiv 64-2\cdot 27 \pmod {27} = 10\pmod {27} \\ &\equiv& 10\cdot(-8) \pmod {27} \\ &\equiv& -80 \pmod {27} \\ &\equiv& -80 + 3\cdot 27 \pmod {27} \\ &\equiv& -80 + 81 \pmod {27} \\ &\equiv& 1 \pmod {27} \\ \hline \end{array}\)

heureka
Feb 28, 2017

#1**+11 **

Best Answer

**I gave a shot and I'm not sure if I got it correct by sheer luck or if my methods were correct.**

Your methods are correct.

**I ended up having to use a calculator at the (-8)^3 part as I wasn't sure how to solve for that in any other way than brute forcing it.**

\(\begin{array}{|rcll|} \hline &&(-8)^3 \pmod {27} \\ &\equiv& (-8)^2\cdot(-8) \pmod {27} \\ &\equiv& 64\cdot(-8) \pmod {27} \quad & | \quad 64 \pmod {27} \equiv 64-2\cdot 27 \pmod {27} = 10\pmod {27} \\ &\equiv& 10\cdot(-8) \pmod {27} \\ &\equiv& -80 \pmod {27} \\ &\equiv& -80 + 3\cdot 27 \pmod {27} \\ &\equiv& -80 + 81 \pmod {27} \\ &\equiv& 1 \pmod {27} \\ \hline \end{array}\)

heureka
Feb 28, 2017