Find the multiplicative inverse of 450 modulo 359. (Express your answer as an integer n with 0 <= n < 359). You can use the fact that 60, 221, and 229 are the sides of a right triangle.

1 answer

Since $60^2 + 221^2 = 3601 = 10^2 \cdot 359$, we see that $60 \cdot 221 \equiv -10 \pmod{359}$. Also, $229^2 = 52441 = 146 \cdot 359$, so $229 \cdot 229^{-1} \equiv 146 \cdot 229^{-1} \equiv -1 \pmod{359}$. Hence,
\begin{align*}
450^{-1} &\equiv (60 \cdot 221) (229 \cdot 229^{-1}) \\
&\equiv (-10)(-1) \\
&= \boxed{10} \pmod{359}.
\end{align*}