Fermat's Little Theorem says:
If p is a prime and a is any integer not divisible by p, then ap − 1 − 1 is divisible by p.
This is equivalent to the following two statements:
\(\displaystyle a^{p-1} \equiv 1 \: \: \text{(mod p)}\) and \(\displaystyle a^p \equiv a \: \: \text{(mod p)}\)
It looks like you've tried to apply this in the second line of your workings, but this is incorrect, because 15 is not a prime number. In actuality, \(\displaystyle 12^{14} \equiv 9 \: \: \text{(mod 15)}\). Because the number you're "modding by" isn't prime, Fermat's Little Theorem probably won't help much here. But some of the principles can still apply. You've correctly identified a possible rewriting of 12
49, so let's work with that for now:
\(\displaystyle 12^{49}=12^{14 \cdot 3 + 7}=(12^{14})^3 \cdot 12^7\)
Using a calculator, I determined that \(\displaystyle 12^{14} \equiv 9 \: \: \text{(mod 15)}\). But, the problem specifically says not to use a calculator. So, let's apply the exact same tactics as above to break it down further. \(\displaystyle 12^{14}=12^{2 \cdot 7}=(12^2)^7\)
12
2 = 144, and this is a small enough value that we can just do the division by hand and find that the remainder is 9. That tells us that \(\displaystyle 12^{14} \equiv 9^7 \: \: \text{(mod 15)}\).
Iterating again will leave \(\displaystyle 9^{7}=9^{2 \cdot 3 + 1}=(9^2)^3 * 9\). Doing the division by hand shows that \(\displaystyle 9^2 = 81 \equiv 6 \: \: \text{(mod 15)}\). This tells us that \(\displaystyle 9^{7} \equiv 6^3 \cdot 9 \: \: \text{(mod 15)}\).
As it turns out, \(\displaystyle 6^3 = 216 \equiv 6 \: \: \text{(mod 15)}\). This tells us that \(\displaystyle 9^{7} \equiv 6 \cdot 9 = 54 \equiv 9 \: \: \text{(mod 15)}\).
This all leaves us with the conclusion that \(\displaystyle 12^{49} \equiv 9^3 \cdot 12^7 \equiv 9^2 \cdot 9 \cdot (12^2)^3 \cdot 12 \: \: \text{(mod 15)}\). Try continuing from here and see what you get.
