Tuesday, 10 March 2026

Exercise (5.2).5

Determine the least non-negative residue $x$ in

$$11^{1767} \equiv x  \pmod {301}$$


Since $\gcd(11,301)$ the by Euler's Theorem we have

$$ 11^{\phi(301)} \equiv 1 \pmod {301} $$

Using $\phi(301)=252$ gives us

$$ 11^{252} \equiv 1 \pmod {301} $$

Noting that $1767 = 7(252)+3$, we have

$$ \begin{align} 11^{1767} & \equiv (11^{252})^7 \times 11^3 \pmod {301} \\ \\ & \equiv 1 \times 1331 \pmod {301} \\ \\ & \equiv  127 \pmod {301}  \end{align}$$

And so the least non-negative residue $x$ is 127.