Discrete Structure20815 marksNumerical: multiplicative inverse, Extended EuclideanExtended Euclidean algorithm
Find the multiplicative inverse of 6 in mathbbZ25 using Extended Euclidean Algorithm.
Find the multiplicative inverse of 6 in $\mathbb{Z}_{25}$ using Extended Euclidean Algorithm. [5]
- Modulus: $n = 25$ - Element whose inverse is sought: $a = 6$ - Ring: $\mathbb{Z}{25}$ - Goal: find $x$ such that $6x \equiv 1 \pmod{25}$ $$25 = 4 \times 6 + 1$$ $$6 = 6 \times 1 + 0$$ So $\gcd(25, 6) = 1$. Since the gcd is $1$, the inverse exists. From the first equation, isolate the remainder ...