1
$\begingroup$

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?

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .