Discrete Structures20805 marksNumerical: extended Euclidean algorithmExtended Euclidean Algorithm
Find the multiplicative inverse of 4 in mathbbZ11 using extended euclidean algorithm.
Find the multiplicative inverse of 4 in $\mathbb{Z}_{11}$ using extended euclidean algorithm. [5]
- Modulus: $n = 11$ - Element: $a = 4$ - Goal: find $x$ such that $4x \equiv 1 \pmod{11}$ We seek integers $s, t$ satisfying: $$s \cdot 4 + t \cdot 11 = \gcd(4, 11)$$ Since $\gcd(4,11) = 1$, the inverse exists, and $s \bmod 11$ is the inverse of 4. Step Division ---------------- 1