4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
4
  • $\begingroup$ 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)$? $\endgroup$ – Décio Soares Dec 1 '13 at 4:03
  • $\begingroup$ @DécioSoares. you are correct. $\endgroup$ – lab bhattacharjee Dec 1 '13 at 4:18
  • $\begingroup$ 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. $\endgroup$ – Décio Soares Dec 1 '13 at 4:41
  • $\begingroup$ @DécioSoares, my pleasure. Have you derived the generalization. Btw, please have a look into my other answer. $\endgroup$ – lab bhattacharjee Dec 1 '13 at 4:43
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Décio Soares Dec 1 '13 at 4:33
1
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ @user17762, how about this method? $\endgroup$ – lab bhattacharjee Dec 1 '13 at 4:40
  • $\begingroup$ 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. $\endgroup$ – Décio Soares Dec 1 '13 at 5:02
  • $\begingroup$ @DécioSoares, as $(14,30)=2$ and $14=2^1\cdot7$ I just took out $14^1$ from $14^{54321}\pmod{30}$ $\endgroup$ – lab bhattacharjee Dec 1 '13 at 5:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.