Solution

Find an integer $x$ that satisfies the congruence below. $$x^{169} \equiv 119 \pmod{1452}$$



We begin by supposing that $x = 119^u$ is a solution.

Substituting, we then have

$$119^{169u} \equiv 119 \pmod{1452}$$

Since $\gcd(119,1452) = 1$, we are free to divide both sides by $119$ to obtain

$$119^{169u-1} \equiv 1 \pmod{1452}$$

Recall, we know by Euler's Theorem that

$$119^{\phi(1452)} \equiv 1 \pmod{1452}$$

Of course, we can calculate $\phi(1452)$ from its prime factorization:

$$\begin{array}{rcl} \phi(1452) &=& \phi(2^2 \cdot 3 \cdot 11^2)\\ &=& \phi(2^2) \cdot \phi(3) \cdot \phi(11^2)\\ &=& (2^2 - 2)(3-1)(11^2 - 11)\\ &=& 2 \cdot 2 \cdot 110\\ &=& 440 \end{array}$$

Consequently, we know that for any positive integer $c$,

$$119^{440c} \equiv 1 \pmod{1452}$$

So we search for a $u$ and $c$ such that

$$169u-1 = 440c$$

Equivalently, we solve

$$169u \equiv 1 \pmod{440}$$

Solving such congruences should be routine by now -- so we omit the details -- but this leads to

$$u \equiv 289 \pmod{440}$$

So $x \equiv 119^{289} \pmod{1452}$ should solve the congruence with which we started. To find this large power, we appeal to the process of successive squaring...

Breaking the exponent into a sum of powers of two, we find $289 = 256 + 32 + 1$, so we compute $123^n \pmod{1452}$ for all $n$ that are powers of $2$ less than or equal to $256$.

$$\begin{array}{rcl} 119^{1} &\equiv& \fbox{119} \\ 119^{2} &\equiv& 1093\\ 119^{4} &\equiv& 1105\\ 119^{8} &\equiv& 1345\\ 119^{16} &\equiv& 1285\\ 119^{32} &\equiv& \fbox{301}\\ 119^{64} &\equiv& 577\\ 119^{128} &\equiv& 421\\ 119^{256} &\equiv& \fbox{97} \end{array}$$

Finally, multiplying the boxed values together, we arrive at the solution we seek

$$x \equiv 119 \cdot 301 \cdot 97 \equiv 1259 \pmod{1452}$$