Question about calculating $2^{32101}\bmod 143$? I am trying to calculate $2^{32101}\bmod 143$ with using paper and a calculator. 
What bothers me is that $32101 = 47 \times 683$ and $143=11 \times 13$, so they are not prime numbers. This means i can't use Fermat's little theorem. I tried also to solve it by square and multiply algorithm, but i am stuck there too, so maybe it doesn't work too. 
I have been thinking of using the Chinese reminder theorem, but i don't know how to apply it here, because of the prima facorization of $32101$...
Does anyone have an idea how to calculate suche large numbers when they are not prime? 
I would be glad if someone could help me. Thank you in advance!
 A: Well, you already thought about using Fermat's Little Theorem and Chinese Remainder theorem, which combined can do this.
The basic idea is that you can compute
$2^{32101} \pmod{11}$ and $2^{32101} \pmod{13}$ using Fermat's Little Theorem, and then use the results to compute $2^{32101} \pmod{143}$ using Chinese Remainder Theorem.
A: Square and multiply should work. The calculation is long enough that it's easy to have made a mistake, though, if you aren't careful. I usually wind up doing long calculations twice (hopefully with variations in the two tries -- e.g. one calculation might use the bottom-up variation and the other the top-down variation) to get some extra confidence I didn't make an error.
You could break mod 143 into mod 11 and mod 13, and do those individually, then recombine to get an answer.
The base and modulus are relatively prime, so you could use the generalization of Fermat's little theorem:

If $\gcd(b,m) = 1$, then $b^{\varphi(m)} \equiv 1 \bmod m$, where $\varphi$ is Euler's totient function.

A: We can use Carmichael function to find $$\lambda(143)=60$$
$$\implies 2^{60}\equiv1\pmod{143}\implies 2^{60a}\equiv1^a\pmod{143}\equiv1\text{ for any integer }a$$
Now, $32101\equiv1\pmod{100}$ and $32101\equiv1\pmod3$
$\implies 32101\equiv1\pmod{\text{lcm}(100,3)}\implies 32101\equiv1\pmod{300}$
$\implies32101\equiv1\pmod{60}$
A: The factors of $32101$ really don't matter.  What is to be done is to note for example, that $2^{12} = 1 \pmod{13}$, and $2^{10} = 1 \pmod{11}$, so $2^{60}= 1 \pmod{143}$, where $60 = \operatorname{lcm}(12, 10)$, 
So, you can put $2^{60}x = x \pmod{143}$, and thus freely subtract multiples of $60$ from $32101$.  This equates to $2^{32101} = 2^1 \mod{143}$, because subtracting multiples of 60 from 32101 equates to $32101 = 1 \pmod{60}$.  
So then it's the simple task of evaluating $2^1 = 2$, which is the desired answer.
