Modular equations

Question

$$ x^{13}\equiv4\pmod{101}\\x\equiv5^{5^{5^{5}}}\pmod{47\cdot27} $$ Equations are separate. How should I approach these? Both has something to do with Euler's theorem, I believe, but all my attempts to solve them were futile. I have an idea on the second one, however I'm not sure there is no mistakes. Is it true that if $y=5^{5^{5}}\pmod{\phi(47\cdot27)}$, then $5^{y}\equiv5^{5^{5^{5}}}\pmod{47\cdot27}$?

Answer 1

For the first question $$x^{13} \equiv 4 \pmod {101} \tag{*1}$$ Since $\gcd(4,101) = 1$, any solution $x$ of $(*1)$ must satisfy $x^{\phi(101)} = x^{100} \equiv 1 \pmod{101}$.
If one can find a positive integer $p$ such that $13\times p \equiv 1 \pmod{100}$, we will have

$$x \equiv x^{13\times p} \equiv 4^p \pmod {101}$$ One can obtain such a $p$ systematically using Euclidean algorithm.

$$\begin{array}{rcll} 100 - 7 \times 13 = 9\\ 13 - 9 = 4 & \implies& 4 &= 13 - (100 - 7\times 13) = 8\times 13 - 100\\ 9 - 2\times 4 = 1 &\implies& 1 &= (100 - 7\times 13) - 2\times ( 8\times 13 - 100)\\ &&&= 3\times 100 - 23\times 13\\ &&&= (3 - 13)\times 100 + (100-23)\times 13\\ &&&= 77\times 13 - 10\times 100\\ \end{array}$$ This implies we can use $77$ as $p$ and

$$x \equiv 4^{77} \pmod {101}\tag{*2}$$

To evaluate the RHS of $(*2)$. A systematic way is look at the binary representation of $77$ $$77 = 64 + 8 + 4 + 1 = 2^6 + 2^3 + 2^2 + 1$$ Construct a helper sequence $4^{2^k}$ by repeat squaring and build the desired result along the way.

Let's use the computation of $4^{77} \pmod {101}$ as an example.
Under modulus arithmetic when every multiplication is modulo $101$, we have $$\begin{array}{lll} & 4^2 \equiv 16\\ \leadsto & 4^4 \equiv 16^2 = 256 \equiv 54 &\leadsto 4^{5} = 4^{4+1} \equiv 54\times 4 = 216 \equiv 14 \\ \leadsto & 4^8 \equiv 54^2 = 2916 \equiv 88 &\leadsto 4^{13} = 4^{8+4+1} \equiv 88\times 14 = 1232 \equiv 20 \\ \leadsto & 4^{16} \equiv 88^2 = 7744 \equiv 68\\ \leadsto & 4^{32} \equiv 68^2 = 4624 \equiv 79\\ \leadsto & 4^{64} \equiv 79^2 = 6241 \equiv 80 &\leadsto 4^{77} = 4^{64+8+4+1} \equiv 80\times20 = 1600 \equiv 85 \end{array}$$

So the answer for the first question is $x \equiv 85 \pmod{101}$.

Answer 2

It seems I've found a solution for the second equation.

Let's find $5^{5^{5}}\pmod{\phi(47\cdot27)}$ : $$ \phi(47\cdot27)=\phi(47)\phi(27)=46\cdot18=2^2\cdot3^3\cdot23=828 $$ Our goal is, therefore, to find the solution of the following system $$ \cases{x\equiv5^{5^{5}}\pmod{4}\\ x\equiv5^{5^{5}}\pmod{9}\\ x\equiv5^{5^{5}}\pmod{23}} $$ Using the same trick with each of the three: $$ \phi(4)=2\Rightarrow 5^{5^{5}}=5^{3125}=(5^2)^{1562}\cdot5^1\equiv5^1\equiv1\pmod{4}\\ \phi(9)=6\Rightarrow 5^{5^{5}}=5^{3125}=(5^6)^{520}\cdot5^5\equiv5^5\equiv2\pmod{9}\\ \phi(23)=22\Rightarrow 5^{5^{5}}=5^{3125}=(5^{22})^{142}\cdot5^1\equiv5^1\equiv5\pmod{23} $$ After applying CRT to the obtained system: $x\equiv5^{5^{5}}\equiv281\pmod{828}$

Nice, know we know that $5^{5^{5^{5}}}=(5^{828})^n\cdot5^{281}\equiv5^{281}\pmod{47\cdot27} $

The final strokes: $$ \cases{5^{281}\equiv(5^{46})^6\cdot5^{5}\equiv5^{5}\equiv23\pmod{47}\\ 5^{281}\equiv(5^{18})^{15}\cdot5^{11}\equiv5^{11}\equiv2\pmod{27}}\\ \\ x\equiv5^{281}\equiv164\pmod{1269} $$

And that's the answer: $5^{5^{5^{5}}}\equiv5^{281}\equiv164\pmod{47\cdot27}$