Remainder of $37^{100}\equiv \pmod {29}$ I'm not allowed to use theorems, so I'm doing like this:
$$37^1 \equiv 8 (\mbox{mod} \ \ 29)$$
$$37^2 \equiv 6 (\mbox{mod} \ \ 29)$$
$$37^4 \equiv 7 (\mbox{mod} \ \ 29)$$
$$37^8 \equiv 20 (\mbox{mod} \ \ 29)$$
$$37^{16} \equiv 23 (\mbox{mod} \ \ 29)$$
$$37^{32} \equiv 7 (\mbox{mod} \ \ 29)$$
$$37^{64} \equiv 20 (\mbox{mod} \ \ 29)$$
However, if I double the exponent here, I'll get more than $100$. But if I multiply both sides by $37^{36}$ to get $37^{100}$ I'll not be able to compute $37^{36}$

UPDATE: turns out my teacher won't let me multiply the congruences to
  get another one. Is there a more elementar way of doing this by hand??

 A: Hint: Multiply your 3rd , 6th and 7th lines. I think you will get your answer.
A: Note that: $$37^{100}=37^{64+32+4}$$
A: $37^{32} \equiv 7\ (mod\ 29)$  
Take this one to the degree of 3 and you're almost there (at degree 96). 
So you have: 
$37^{96} \equiv 7^3\ (mod\ 29)\ \ \ \ \ \ \ \ \ \ (1)$
Now use the fact that: 
$37^{4} \equiv 7\ (mod\ 29)\ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$   
and multiply the congruences (1) and (2). 
Now you're at degree 100 and you're done.
From here one can do it almost without writing: 
the end result is $37^{100} \equiv 7^4\ \equiv 49 . 49 \equiv 20 . 20 \equiv 400 \equiv 110 \equiv 52 \equiv 23\ (mod\ 29)$.     
A: $37\equiv8\pmod{29}\equiv2^3$
$\implies37^{100}\equiv(2^3)^{100}\pmod{29}$
Now $2^5\equiv3\implies2^{15}=(2^5)^3\equiv3^3\equiv-2$
$\implies37|2(2^{14}+1)\implies2^{14}\equiv-1\pmod{29}$ as $(2,29)=1$
Now $300=14\cdot21+6$
$2^{300}=(2^{14})^{21}\cdot2^6\equiv(-1)^{21}\cdot2^6\equiv-64\equiv-6\equiv-6+29$
A: I'm lazy. And I have trouble remembering all the fancy theorems, anyway. But since $37 > 29$, we may as well reduce that, first.
Now we're calculating $8^{100}$ (mod $29$), which at least is a "little" better.
Now using Fermat's Little Theorem is really the way to go, here (we could knock down that exponent in a hurry), but without it, we take a slightly longer path.
$8^{100} = (8^2)^{50} = 64^{50} = 6^{50}$ (mod $29$). Notice how I keep reducing the "base". This is to try to "keep it small" because exponentiating large integers is painful. Same thing again:
$6^{50} = (6^2)^{25} = 36^{25} = 7^{25}$ (mod $29$). Now since I don't really want to have to figure out what $7^5$ actually is, I'll cheat a little:
$7^{25} = (7^5)^5 = [(7^2)(7^2)7]^5 = [(49)(49)(7)]^5 =  [(20)(20)(7)]^5 = 2800^5$ (mod $29$).
Note that $28 = -1$ (mod $29$), so we can re-write this as:
$2800^5 = (-100)^5 = [(-1)(100)]^5 = -(100^5) = -(13^5) = (-13)^5 = 16^5$ (mod $29$)
(using the handy fact that $5$ is an odd number, so exponentiating $5$ times preserves signs).
Now I still don't feel like calculating $16^5$ (yes, I'm that lazy), so I do this:
$16^5 = (2^4)^5 = 2^{20}$ (mod $29$). Now I have a smaller "base" (even though my exponent went up a bit). The reason I did this was to write:
$2^{20} = (2^5)^4 = 32^4 = 3^4$ (mod $29$). Now I have a small base, AND a small exponent. THIS I can do in my head:
$3^4 = 81 = 58 + 23 = (2)(29) + 23 = 23$ (mod $29$). And done.
