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.
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*}
To find the multiplicative inverse of 450 modulo 359, we need to find an integer x such that:
(450 * x) ≡ 1 (mod 359)
To solve this equation, we can use the Extended Euclidean Algorithm. We start with the equation:
359 = 450 * q0 + r0
Dividing both sides by 359, we have:
1 = 450 * (1/359) * q0 + r0 / 359
Since we want to find the multiplicative inverse (denoted as a⁻¹), we can rewrite the equation as:
a⁻¹ ≡ (1/359) (mod m)
Using the Extended Euclidean Algorithm, we continue to find the values q1, q2, r1, r2, etc., until we reach a remainder of 1:
450 = 359 * q1 + r1
359 = r0 * q1 + r1
r0 = r1 * q2 + r2
r1 = r2 * q3 + 1
By substituting the equations, we can solve for r2:
359 = (450 - 359 * q1) * q2 + r2
359 = 450 * q2 - 359 * q1 * q2 + r2
Comparing coefficients, we have:
-359 * q1 * q2 + 450 * q2 = 359
Simplifying the equation further, we get:
-359 * q1 * q2 ≡ 359 (mod 450)
Simplifying some more, we find:
q1 * q2 ≡ -1 (mod 450)
From the given information that 60, 221, and 229 are the sides of a right triangle, we can conclude that 221 * 229 ≡ -1 (mod 450).
Therefore, to find the multiplicative inverse of 450 modulo 359, we can use the value 221 * 229:
450⁻¹ ≡ 221 * 229 (mod 359)
Calculating this value:
450⁻¹ ≡ 50609 (mod 359)
Since we want to express the answer as an integer n with 0 ≤ n < 359, we can simplify further:
50609 ≡ 73 (mod 359)
Therefore, the multiplicative inverse of 450 modulo 359 is 73.