# 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):

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

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