Multiplicative Inverse 5Ce716

1. **Problem Statement:** Define the multiplicative inverse in modular arithmetic and find the multiplicative inverse of $5$ modulo $9$. 2. **Definition:** The multiplicative inverse of an integer $a$ modulo $m$ is an integer $x$ such that: $$a \times x \equiv 1 \pmod{m}$$ This means when $a$ is multiplied by $x$, the result is congruent to $1$ modulo $m$. 3. **Important Rule:** A multiplicative inverse of $a$ modulo $m$ exists if and only if $a$ and $m$ are coprime, i.e., $\gcd(a,m) = 1$. 4. **Check if inverse exists:** Calculate $\gcd(5,9)$: $$\gcd(5,9) = 1$$ Since $1$, the inverse exists. 5. **Algorithm Used: Extended Euclidean Algorithm** This algorithm finds integers $x$ and $y$ such that: $$a x + m y = \gcd(a,m)$$ Since $\gcd(5,9) = 1$, we want $x$ such that: $$5x + 9y = 1$$ The value of $x$ modulo $9$ is the multiplicative inverse. 6. **Apply Extended Euclidean Algorithm:** - Divide $9$ by $5$: $$9 = 5 \times 1 + 4$$ - Divide $5$ by $4$: $$5 = 4 \times 1 + 1$$ - Divide $4$ by $1$: $$4 = 1 \times 4 + 0$$ Back substitute to express $1$ as a combination of $5$ and $9$: $$1 = 5 - 4 \times 1$$ But $4 = 9 - 5 \times 1$, so: $$1 = 5 - (9 - 5 \times 1) \times 1 = 5 - 9 \times 1 + 5 \times 1 = 5 \times 2 - 9 \times 1$$ 7. **Result:** $$5 \times 2 \equiv 1 \pmod{9}$$ So, the multiplicative inverse of $5$ modulo $9$ is $2$. **Final answer:** The multiplicative inverse of $5$ mod $9$ is $2$.