Use Euclid's Algorithm to find the multiplicative inverse of $13$ in $\mathbf{Z}_{35}$
Can someone talk me through the steps how to do this? I am really lost on this one.
Thanks
Answer
Hint: $13$ and $35$ are relatively prime. Use the extended Euclidean algorithm to find the integers $x$ and $y$ such that:
$$13x + 35y = 1$$
From here, simply mod out by $35$:
$$13x \equiv 1 \pmod{35}$$
No comments:
Post a Comment