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
$\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):

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

| cite | improve this answer | |
$\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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.