# Find a positive integer $x$ such that $0<x\leq38$ and $14^{36}\equiv x\pmod{38}$

Find 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?

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*}

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$.