# Doubts about a nested exponents modulo n (homework)

As part of my homework I am supposed to find the remainder of the division of $2^{{14}^{45231}}$ by $31$.

Using the ideas explained in calculating nested exponents modulo n I tried the following:

$\phi(31)=30$ since $31$ is prime. Then:

$2^{{14}^{45231}}$ (mod $31$) = $2^{{14}^{45231} (\textrm{mod}30)}$ (mod $31$)

Since $30 = 2 \cdot 3 \cdot 5 \quad$ I need to solve:

$$\begin{matrix} 14^{45231} \equiv a_1 \; (\textrm{mod} \; 2) \\ 14^{45231} \equiv a_2 \; (\textrm{mod} \; 3) \\ 14^{45231} \equiv a_3 \; (\textrm{mod} \; 5) \end{matrix}$$

That means to solve:

$$\begin{matrix} x \equiv 0 \; (\textrm{mod} \; 2) \\ x \equiv -1 \equiv 2 \; (\textrm{mod} \; 3) \\ x \equiv -1 \equiv 4 \; (\textrm{mod} \; 5) \end{matrix}$$

Let $N = 30 = 2 \cdot 3 \cdot 5$; $n_1=2$; $n_2=3$; $n_3=5$, since $\textrm{gdc}(n_i,n_j) = 1 \; \forall i \neq j \; ; \; i,j \in (1,2,3)$, I can use the chinese remaider theorem which gives me that:

$$x = \sum_{i=1}^{3}a_i \cdot N_i \cdot y_i \; (\textrm{mod} \; n_1 \cdot n_2 \cdot n_3)$$

Where $N_i = \frac{N}{n_i}$; $y_i=N_i^{-1} \; (\textrm{mod} \; n_i)$; $a_1=0$; $a_2=2$ and $a_3=4$.

Applying the formula I found that: $x=44 \equiv 14 \; (\textrm{mod} \; 30)$

Going back to the beginning I made:

$2^{{14}^{45231}}$ (mod $31$) = $2^{{14}^{45231} (\textrm{mod}30)}$ (mod $31$) = $2^{{14}} \equiv 2^4 \equiv 16$ (mod $31$)

And because of that I can say that the remainder of the division of $2^{{14}^{45231}}$ by $31$ is $16$.

I have two doubts about this resolution:

1) Is it right? If not, could you please point out where I made a mistake?

2) Is there another way to solve nested exponents other than using Euler's Totient Function? Even better, is there any other way to solve this using less step's or arguments? (Despite of the obvious fact that they are valid answer's to the second question, I think its better to mention that I am not looking for answer's like: Yes, using Mathematica. (or similar ones))

## 3 Answers

HINT:

Fermat's Little Theorem, Euler's Totient Theorem or Carmichael function, help us find one of the minimal integer $n>0$ such that $a^n\equiv1 \pmod m$, but not the modulo order.

Before that we can check for the remainders some smaller power of $2\pmod{31}$

Observe that $\displaystyle2^5=32\equiv1\pmod{31}$

As $\displaystyle14\equiv-1\pmod5,14^{45231}\equiv(-1)^{45231}\equiv-1\equiv4$

Generalization:

If $\displaystyle d=$ord$_ma\iff a^d\equiv1\pmod m$ and $\displaystyle n\equiv r\pmod d,$ $\displaystyle a^n\equiv a^r\pmod m$

• Let me see if I understood. If I had to compute for example: $2^{{15}^{n}} \; (\textrm{mod} \; 31)$ with n a very big number, since $2^{5}=32 \equiv 1 \; (\textrm{mod} \; 31)$ and $15 \equiv 0 \; (\textrm{mod} \; 5)$, all I had to do is to compute $2^{{0}^{n}}=1 \equiv 1 \; (\textrm{mod} \; 31)$? Dec 1, 2013 at 4:03
• @DécioSoares. you are correct. Dec 1, 2013 at 4:18
• Thank you very much for the contribution, the generalization presented helped in a way you could not imagine. I promise to upvote the answer as soon I reach the minimum rep. Dec 1, 2013 at 4:41
• @DécioSoares, my pleasure. Have you derived the generalization. Btw, please have a look into my other answer. Dec 1, 2013 at 4:43

Note that $14 = 2 \cdot 7$. We have $2^5 \equiv 2 \pmod{30}$. Similarly, $7^4 \equiv 1 \pmod{30}$. Hence, $14^{45231} = 2^{45231} \cdot 7^{45231}$. $$2^{45231} \equiv \pmod{30} \equiv 2^{5(9046)+1} \equiv \pmod{30} \equiv 2^{9047} \cdot 2^{5(1809)+2} \pmod{30} \equiv 2^{1811} \pmod{30} \equiv 2^{5(362)+1} \pmod{30} \equiv 2^{362+1} \pmod{30} \equiv 2^{5(72)+3} \pmod{30} \equiv 2^{72+3} \pmod{30} \equiv 2^{3} \pmod{30} \equiv 8 \pmod{30}$$ $$7^{45231} \pmod{30} \equiv 7^{4M+3} \pmod{30} \equiv 7^3 \pmod{30} \equiv 13 \pmod{30}$$ Hence, $$14^{45231} \equiv 14 \pmod{30}$$ Now conclude what you want.

• Thank you for pointing the factorization of $14$, missed that and with it I could had avoided a lot of step's. As soon I reached the minimum reputation I promise to upvote your contribution. Dec 1, 2013 at 4:33

Following your way :

As $\displaystyle14\equiv-1\pmod{15}, 14^{54320}\equiv(-1)^{54320}$

$\displaystyle\implies14^{54320}\equiv1\pmod{15}$

As $\displaystyle a\equiv b\pmod n\implies a\cdot m\equiv b\cdot m\pmod {n\cdot m},$ $\displaystyle\implies14^{54321}\equiv14\cdot1\pmod{15\cdot14}$

$\displaystyle\implies14^{54321}\equiv14\pmod{30}$ as $30|210$

• @user17762, how about this method? Dec 1, 2013 at 4:40
• Very elegant and simple resolution as also a smart move to find the relation between $14$, $15$ and $30$. One more for my arsenal. Thanks again. Dec 1, 2013 at 5:02
• @DécioSoares, as $(14,30)=2$ and $14=2^1\cdot7$ I just took out $14^1$ from $14^{54321}\pmod{30}$ Dec 1, 2013 at 5:09