4
$\begingroup$

I want to calculate $\frac{\overline{2}}{\overline{3}}$, $\frac{\overline{1}}{\overline{9}}$, $\frac{\overline{32}}{\overline{9}}$ in $\mathbb{Z}_7$.

About first example my book says: $\overline{3}*\overline{5}=\overline{15}=\overline{1}$, then $\frac{\overline{1}}{\overline{3}}=\overline{5}$; and finally $\frac{\overline{2}}{\overline{3}}=\overline{10}=\overline{3}$. It's pretty clear, except first step? From where 5 and 3 came out?

Regards

  • 2
    $\mathbb{Z}_7$ is tiny. To find the inverse of something, try stuff until you find something that works, though there are shortcuts, barely needed. What is the inverse of 9 aka 2? Can you think of something which when multiplied by $2$ gives $1$ more than a multiple of $7$? Surely $4$ jumps to mind. (Now you know the inverse of $2$ for any $\mathbb{Z}_n$ with $n$ odd. Others are less simple for $n$ big.)2012-02-02

1 Answers 1

2

Expanding on Arturo Magidin's comment, there is an algorithm that finds the inverse of an element $\overline{a} \in \mathbb{Z}_n$ (which doesn't involve checking all elements), assuming such inverse exists. Indeed, the inverse of $\overline{a}$ exists if and only if $a$ and $n$ are coprime, and therefore, since $\gcd(a, n) = 1$, Bézout's Identity implies that $\exists \ \alpha, \ \beta \in \mathbb{Z}$ such that $\alpha a + \beta n = 1$. $\alpha$ and $\beta$ can be determined with the Extended Euclidean Algorithm. Now, you have: $\alpha a = 1- \beta n \equiv 1 \ \left(\text{mod} \ n \right) \Rightarrow \overline{\alpha} = \overline{a}^{-1} \ \text{in} \ \mathbb{Z}_n $ so the inverse of $\overline{a}$ has been determined. If you want to calculate $\frac{\overline{b}}{\overline{a}}$, simply multiply $\overline{b}$ by $\overline{\alpha}$.
As pointed out in the comments, if you are dealing with small $n$'s, such as $7$, checking all other elements of $\mathbb{Z}_n$ is probably faster then determining the coefficients of the Bézout Identity; however for large $n$'s the Extended Euclidean Algorithm is more efficient then an exhaustive check: the first has time complexity $O(\log^2(n))$ while the latter $O(n)$ (see Buchmann - an Introduction to Cryptography).