Finding a solution $x \in \mathbb{N}$ of $x^{125} \equiv 7 \ (\mathrm{mod} \ 39)$

Question

I want to find a solution $x \in \mathbb{N}$ of $x^{125} \equiv 7 \ (\mathrm{mod} \ 39)$ by using Ender Wiggin's method Find $x^{98}$ congruent to $7$ (mod $18$)

My steps are:

$x^{125} \equiv 7 \ (\mathrm{mod} \ 39) \Rightarrow x^{125}=7+39 \cdot n,\ n \in \mathbb{N}$

$\Rightarrow \mathrm{gcd}(x,39)=1$

It's $\varphi(39)=\varphi(3)\cdot\varphi(13)=24$

So $x^{24} \equiv 1 \ (\mathrm{mod} \ 39)$

Since $x^{125} \equiv 7 \ (\mathrm{mod} \ 3)$ and $x^{125} \equiv 7 \ (\mathrm{mod} \ 13)$ it follows that

$x^{\varphi(3)}=x^2 \equiv 1 \ (\mathrm{mod} \ 3)$ and $x^{\varphi(13)}=x^{12} \equiv 1 \ (\mathrm{mod} \ 13)$.

Now I don't know what to do next.

I tried with $x=4$ and it works, but how to show it properly?

What has to be done now?

Answer 1

Better use Carmichael Function $$\lambda(39)=12$$

and $125\equiv5\pmod{12}$

$$ x^{125}\equiv x^5\pmod{39}$$

$$\implies x^5\equiv7\pmod{39}$$

Now as $x^{12}\equiv1\pmod{39}$

$$x\equiv(x^5)^5(x^{12})^{-2}\equiv7^5\cdot1^{-2}\pmod{39}$$

Finally $7^2\equiv10,7^4\equiv10^2\equiv-17, 7^5\equiv7(-17)\equiv-2\equiv39-2$

Answer 2

$ x^{24} \equiv 1 \pmod{39} $ is not something to be solved; it's something you know is true whenever $\gcd(x,39)=1$. So

$$ x^{125} = (x^{24})^5 x^5 \equiv x^5 \equiv 7 \pmod{39} $$

Then you can continue as in @lab bhattacharjee's answer.

Or for a different approach, you could start by noting that $x^{125} \equiv 7 \pmod{39}$ if and only if $x^{125} \equiv 7 \pmod{3}$ and $x^{125} \equiv 7 \pmod{13}$.