modules with several powers $x^{y^z}$

Question

I have an assignment(which gives no credit) which I cant solve so I would like to get some help

$3^{{1001}^{1002}}\pmod {43}$ (All original numbers were replaced)

Our hint was to use the Chinese-remainder-theorem but I don't see how when $43$ is a prim number.

Answer 1

$$3^{1001^{1002}}\equiv3^{1001^{1002}\pmod{\phi(43)}}\pmod{43}$$

Now, $\phi(43)=42=2\cdot3\cdot7;$

As $(1001,42)=7$

let use find $\displaystyle 1001^{1002-1}\pmod{\frac{42}7}$

As $1001\equiv-1\pmod6\implies 1001^{1002-1}\equiv(-1)^{1001}\equiv-1\pmod6$

$\displaystyle\implies1001^{1002}\equiv1001(-1)\pmod{6\cdot1001}\equiv-1001\pmod{42}\equiv7$

Answer 2

Changing the numbers is good policy for learning - thank you! - but for this kind of problem you have to be careful, as what appears to be a small or random change may make the problem very much harder. So I will change the problem again and show you how to solve it, before returning to your problem.

Problem. Simplify $3^{1001^{1002}}\pmod{52}$.

Solution. By trial and error we get modulo $52$ $$3^1=3\,,\ 3^2=9\,,\ 3^3=27\,,\ 3^4=81=29\,,\ 3^5=87=35\,,\ 3^6=105=1\ .$$ So for any $k$ we have $$3^{6k}=(3^6)^k=1^k=1\pmod{52}\ .$$ We also have $$1001=-1\pmod6\quad\Rightarrow\quad 1001^{1002}=(-1)^{1002}=1\pmod6$$ and so we can write $$1001^{1002}=6k+1\ .$$ Therefore we get the simplification $$3^{1001^{1002}}=3^{6k+1}=(3^6)^k\times3^1=1^k\times3=3\pmod{52}\ .$$

---

For your problem the principle is the same, but unfortunately the trial and error stage does not give $3^n=1\pmod{43}$ until $n=42$, which makes the calculations rather more difficult.

Answer 3

What do you think about this solution? I think it's a general solution(is it?)

{2014^{2013}} \equiv 2^{2014mod\phi (41)^{2013} } \equiv 2^{14^{2013}} \equiv 2^{14^{2013}mod\phi (41)} \equiv 2^{14^{13}} \equiv 2^{(14^{2})^{6}14^{1}} \equiv 2^{36^{6}14^{1}} \equiv 2^{36*14^{1}} \equiv 2^{12*40+24(mod\phi (41))} \equiv 2^{24} \equiv (2^{7})^{3}*2^{3} \equiv (5^{3}*2^{3} \equiv (41*24+16) \equiv 16) (mod41)