Wednesday, 31 December 2025

Exercise (4.1).9

Find a solution of $x^{101} ≡ 5 \pmod {13}$.


There are two cases to consider: 13 divides $x$ and 13 does not divide $x$. In the first case, there is no solution because then $x \equiv 0 \pmod {13} \implies x^{101} \equiv 0 \pmod {13}$.

So we are left with the second case where 13 does not divide $x$. This means we can use the FlT, and so we have

$x^{12} \equiv 1 \pmod {13}$

$(x^{12})^{8} \equiv x^{96} \equiv 1 \pmod {13}$

And so

$x^{101} \equiv x^{96} \times x^{5} \equiv x^5 \equiv 5 \pmod {13}$

The following table shows some $x^5 \pmod{13}$.

xx^5x^5 mod 13
000
111
2326
32439
4102410
531255
677762

We can see $x=5$ is a solution, and our assumption 13 does not divide $x=5$ holds.