How can I calculate these large exponents with mods? Is there a fast technique that I can use that is similar in each case to calculate the following:
$$(1100)^{1357} \mod{2623} = 1519$$
$$(1819)^{1357} \mod{2623} = 2124$$
$$(0200)^{1357} \mod{2623} = 2227$$
$$(1111)^{1357} \mod{2623} = 1111$$
I used Wolfram Alpha to get to these answers, but I would like to know how to calculate it by hand (with a standard pocket calculator).
 A: I would follow the pseudocode given here:


*

*Write your exponent, 1357, in binary: $10101001101_2$.

*Let $b := x\mod 2623$.

*Let $r := 1$.

*Step through the bits from right-to left:


*

*If the bit is $1$:


*

*Let $r := b \cdot r \mod 2623$.


*Let $b := b^2 \mod 2623$.



Then $r$ will be your final result. This requires 17 multiplications modulo $2623$. In general it requires (number of 1-bits) + (number of bits) multiplications.
(To compute a "modulo" operation on a pocket calculator, you can either subtract $2623$ repeatedly until you get a result that's less than $2623$, or you can calculate $x - \lfloor x / 2623 \rfloor \cdot 2623$.)
EDIT: You can use the Carmichael theorem to reduce the exponent to 97, as @wythagoras explains. Cool!
A: Use the Carmichael theorem. This theorem states that $$a^{\lambda(n)} \equiv 1 \mod n$$
if $\gcd(a,2623)=1$. In this case we have $\lambda(2623)=\mathrm{lcm}(42,60)=420$.
Therefore, if $\gcd(a,n)=1$, then $$a^{1357} \equiv a^{1357-1260} = a^{97} \mod 2623$$
This is more friendly to compute with the method @Mauris describes. 
A: Factorize $2623=43\times 61$.
Remember the Euler theorem, which tells you that
$$a^{\phi(n)}=1\mod n$$
if $n$ and $a$ are coprime. For prime $n$, you have $\phi(n)=n-1$.
You can also use the CRT
A: Combine Little Fermat and Cinese remainder theorem: as $2623=43\cdot61$, we have:
$$\mathbf Z/2623\mathbf Z\simeq \mathbf Z/43\mathbf Z\times \mathbf Z/61\mathbf Z.$$
To compute, say, $1100^{1357}\bmod 2623$, you first compute $1100\bmod 43=25$ and $1100\bmod61=2$. Then use Little Fermat for each of the congruences:
$$\begin{cases}
1100^{1357}\equiv 25^{1357\bmod42}=25^{13}\equiv 14\mod 43\\
1100^{1357}\equiv 2^{1357\bmod60}=2^{37}\equiv 55\equiv-6\mod 61
\end{cases}$$
(the powers can be computed with fast exponentiation, by successive squarings).
Now we have to go back to $\mathbf Z/2623\mathbf Z$. From the Bézout relation:
$\;12\cdot61-17\cdot43=1\;$ (obtained from the extended euclidean algorithm, we obtain:
$$1100^{1357}\equiv 12\cdot14\cdot61-17\cdot55\cdot43\equiv1819\mod 2623.$$
