Finding remainder on division by 2014 I'm trying to find the remainder when $6^{936}$ is divided by $2014$
I started thinking I could use Euler's theorem but then noticed that $6$ isn't prime, I then tried to split it into $6=2 \times 3$ but have got stuck now and don't know how to continue?
 A: As $2014=2\cdot19\cdot53,$
$$6^{936}\equiv0\pmod2\  \ \ \ (1)$$
$$936\equiv0\pmod{18}\implies6^{936}\equiv1\pmod{19}$$
$$936\equiv0\pmod{52}\implies6^{936}\equiv1\pmod{53}$$
$$\implies6^{936}\equiv1\pmod{19\cdot53}\  \ \ \ (2)$$
Method $\#1:$ Chinese remainder theorem on $(1),(2)$
Method $\#2: 6^{936}=1+1007a$ where $a$ is any integer
As $6$ is even, $a$ must be odd $=2b+1$(say) where $b$ is any integer
$$\implies6^{936}=1+1007(2b+1)\equiv1+1007\pmod{2\cdot1007}$$
A: Here's how to continue: By the Euler-Fermat theorem, you know how to work out the remainders of $2^{936}$ and $3^{936}$ modulo $2014.$ Suppose the remainders are $a$ and $b$ so that 
$$ 2^{936} = 2014 \alpha + a \ , \ 3^{936} = 2014 \beta + b$$ for some integers $\alpha, \beta. $ Now if you multiply these, you see that $$ 6^{936} = 2014^2 \alpha \beta + 2014 \alpha b + 2014 a\beta + ab.$$
Modulo 2014, this is $ab.$ In a similar way, you should prove that if $n = a \pmod k$ and $m=b \pmod k$ then $nm = ab \pmod k.$
An alternative method is the Chinese Remainder Theorem, which you should not avoid. Ask your lecturer to help you through some examples. What CRT does is reduce the problem to finding $6^{936}$ modulo the prime factors of 2014 (= 2 * 19 * 53). The product of the remainders mod 2, 19 and 53 is then the remainder mod 2014. With this approach, you can get by with just Fermat's Little Theorem (which Euler generalized) since now you just need to compute remainders after dividing by prime numbers. 
A: Hint $\ $ Specialize $\,a,p,q = 6,19,53\,$ and $\ e = (p\!-\!1)(q\!-\!1) = 936\,$ in the following
Lemma $\ $ If $\ a,p,q\, $ are pairwise coprime, $\,p,q$ odd, and $\ \phi(p),\phi(q)\mid e\,$ then $$\,a^e\equiv\, 1+a'pq\!\pmod{2pq}\ \ \ {\rm for}\ \ \ a' = (a\!-\!1\ {\rm mod}\ 2)$$
Proof $\,\ {\rm mod}\ p\!:\ a^e \equiv (a^{\large \phi(p)})^{\large e/\phi(p)}\!\!\overset{\rm {Euler}}{\underset{\large (a,p)=1}\equiv} 1.\,$ Similarly $\,a^e\equiv 1\pmod q\ $ by $\ (a,q)= 1.$   
So $\ p,q\mid a^e-1\,\Rightarrow\,pq\mid a^e-1\,\Rightarrow\,a^e = 1 + jpq,\,\ j\in\Bbb Z\ $ by $\,{\rm lcm}(p,q) = pq\,$ by $\,p,q\,$ coprime.  
${\rm mod}\ 2\!:\ a \equiv a^e = 1 + jpq \overset{p,q\ \rm odd}\equiv 1\!+\!j\!\iff\! j\equiv a\!-\!1\equiv a',\ $ i.e. $\ j = a'\!+\!2k,\ k\in\Bbb Z$
Therefore $\ a^e = 1+jpq = 1\!+\!(a'\!+\!2k)pq \equiv 1+a'pq\pmod{2pq}\ \ $ QED
