How to evaluate $1234^{1234} \pmod{5379}$? Note: $5379 = 3 \times 11 \times 163$.
I tried Chinese Remainder Theorem and Fermat's Little Theorem, got as far as:
$$
1234^{1234} = 1 \pmod{3} \\
1234^{1234} = 5 \pmod{11}
$$
With a bit more work:
$$1234^{1234} = 93^{100} \pmod{163}$$
But $93^{100}$ doesn't really help?
WolframAlpha tells me that $\phi(5379)=3240>1234$
So I can't use Euler's Theorem?
N.B This appeared on a 1st year undergrad problem sheet. So presumably, not too much technology is required. 
 A: A little noodling produced the following, where all congruences are mod $163$:
$$93\equiv256=2^8\implies2^{10}\cdot93^{100}\equiv2^{810}=2^{162\cdot5}\equiv1$$
Noting that $2^{10}=1024\equiv46$, it remains to compute $46^{-1}$ mod $163$.  This could be done by a straightforward Euclidean algorithm, but I found it easy enough to argue as follows:
$$\begin{align}
23\cdot7=161\equiv-2
&\implies46\cdot7\equiv-4\\
&\implies46\cdot7\cdot(-41)\equiv164\equiv1\\
&\implies46^{-1}\equiv-287\equiv39
\end{align}$$
All in all, we have
$$93^{100}\equiv39\mod163$$
Remark:  The one computation I had to do off to the side was 
$$1024-6\cdot163=1024-978=46$$
Everything else I could do easily in my head.
A: Well this is far from perfect,but it works if you have enough time or a calculator.
$$93\equiv -70\pmod{163}$$
$$\begin{align}
93^{100}&\equiv(-70)^{100}\\
&= 490^{50}\cdot10^{50}\\
&\equiv 10^{50}\\
&= 2^{50}\cdot 5^{50}\\
&= 1024^5\cdot 3125^{10}\\
&\equiv 46^5\cdot 28^{10}\\
&=2^{25}\cdot 23^5\cdot 7^{10}\\
&= 2^{25}\cdot (23\cdot 7)^5\cdot 7^5\\
&= 2^{25}\cdot (161)^5\cdot 7^5\\
&\equiv 2^{10}\cdot2^{10}\cdot 2^5\cdot (-2)^5\cdot 7^5\\
&=1024\cdot 1024\cdot (-1024)\cdot 7^5\\
&\equiv -46^3\cdot 7^5\\
&= -(46\cdot 7)^3\cdot 7^2\\
&= -(322)^3\cdot 7^2\\
&\equiv -(-4)^3\cdot 49\\
&= 49\cdot 64\\
&\equiv 39 
\end{align}$$
A: $93^{100}$ can be computed with the Fast Exponentiation algorithm. First note $93^2\equiv 10\mod163$. Hence all we have to compute is $10^{50}\mod 163$
It can be done with a hand-held calculator. First note  the exponent in base $2$ is written as $110010$, and we use these digits (from right to left) in the algorithm: at each step, the number $a=10$ is squared and reduced modulo $163$. The power $p$ is initially equal to $1$ and, if the digit in the step is $1$, we multiply the previous value of $p$ by the actual value of $a$ and reduce it modulo $163$: 
$$\begin{array}{c|cr|cr}
\text{exponent}&a&&p\\
\hline
0&a&10&1&1\\
1 & x^2 & 100 & x^2&100\\
0 & x^4 & 57& x^2&100\\
0 & x^8 & -11& x^2&100\\
1 & x^{16} & -42& x^{18}&38\\
1 & x^{32} &-29& x^{50}& 39\\
\end{array}$$
There remains to solve the system of congruences:
$$\begin{cases}
x\equiv 1\mod 3\\x\equiv 5\mod 11\\x\equiv39\mod163
\end{cases}$$
As $4\times 3-11=1$, the solution of the first two congruences is  $x\equiv5\cdot 4\cdot3-1\cdot 11=49\equiv16\mod33$.
Morever, a Bézout's relation between $163$ and $33$ is, by the Extended Euclidean algorithm, $16\cdot163-79\cdot33=1$, whence the solution to the system of congruences
$$\begin{cases}
x\equiv 16\mod 33\\x\equiv39\mod163
\end{cases}\iff x\equiv 16^2\cdot163-39\cdot79\cdot33\equiv4603\mod5379.$$
