Doubts about a nested exponents modulo n (homework)

Question

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

Answer 1

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$

Answer 2

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.

Answer 3

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$