Find a positive integer $x$ such that $0Find a positive integer $x$ such that $0<x\leq38$ and $$14^{36}\equiv x\pmod{38}$$
This is what I've come up with so far:
$$14^{36}\equiv x\pmod{38} \iff 14^{36}\equiv x\pmod{19} \, \land 14^{36}\equiv x\pmod{2}$$
For the first of these two I can just use Fermat's Little Theorem which gives me $14^{36}\equiv1\pmod{19}.$ This second just tells me that $x$ is even. 
I'm stuck at this point though. What do I need to do now?
 A: Building upon what you've found you know that:
$$14^{36}\equiv1\pmod{19}$$
and that its even.
So you can write $x$ as $19k+1$ for some $k$. As it is even then $k$ must be odd, i.e. equal to $2n+1$. Subbing this in gives:
$$x=38n+20$$
Hence $14^{36}\equiv 20\pmod{38}$
Alternatively (via direct calculations):
$$\begin{align*} 
14^{36}&=(14^2)^{18} \\
&=196^{18}\\
&\equiv6^{18} &&\pmod{38} \\
&\equiv(6^2)^9 &&\pmod{38} \\
&\equiv36^9 &&\pmod{38} \\
&\equiv(-2)^9 &&\pmod{38} \\
&\equiv(-8)^3 &&\pmod{38}\\
&\equiv-512 &&\pmod{38} \\
&\equiv20 &&\pmod{38} \\
&\end{align*}$$
A: Write $14^{36}\equiv 2^{36} \cdot 7^{36}$.
Fermat–Euler applies to $7^{36} = (7^{18})^2 \equiv 1 \bmod 38$, because $\gcd(7,38)=1$ and $\phi(38)=18$.
Fermat–Euler does not apply to $2^{36} \bmod 38$ but it does apply to $2^{36} \equiv 1 \bmod 19$, because $\gcd(2,19)=1$ and $\phi(19)=18$.
Following your idea, just use the Chinese remainder theorem for $x \equiv 1 \bmod 19$ and $x \equiv 0 \bmod 2$. It is clear that $x \equiv 20 \bmod 38$ is a solution. Thus, $2^{36} \equiv 20 \bmod 38$.
Therefore, $14^{36}\equiv 2^{36} \cdot 7^{36} \equiv 20 \cdot 1 = 20 \bmod 38$.
