Solve the linear congruence: $2^{2015}x\equiv 1\pmod {13}$

Question

Solve the linear congruence: $2^{2015}x\equiv 1\pmod {13}$

$x\equiv (2^{2015})^{\phi(13)-1}\equiv (2^{2015})^{12-1}\equiv 2^{22165}\equiv y\pmod{13}$

$22165=13\cdot 1705$

$y=2^{13} $ or $y=2^{1705}$

Is this correct?

Answer 1

By Fermat's Little theorem: $2^{12}\equiv 1\pmod{13}$.

$$2^{2015}\equiv 2^{2015\bmod {12}}\equiv 2^{11}\equiv \frac{1}{2}\equiv \frac{14}{2}\equiv 7\pmod{13}$$

So you're solving $7x\equiv 1\pmod{13}$.

$$7x\equiv 1\equiv 14\pmod{13}\stackrel{:7}\iff x\equiv 2\pmod{13}$$

---

Using your method: you've found that $x\equiv 2^{22165}\pmod{13}$. By Fermat's Little theorem:

$$2^{22165}\equiv 2^{22165\bmod 12}\equiv 2^{1}\equiv 2\pmod{13}$$

Your argument was alright until you said "$y=2^{13}$ or $y=2^{1705}$". It's unclear what logic you were using there.