Doubts in finding multiplicative inverse for integers $\mod n$.

Question

I am reading into the text Groups & Symmetry, by Oggier, Bruckstein, as available freely here on ntu website.
On page#81 in Corollary 1, there is stated that :

'Thus $ax = 1+(-y)n$ and $\overline{x}$ is the inverse of $a$.
Conversely, if there is an $\overline{x}$ such that $\overline{ax}$ =$\overline{1}$ then $ax = 1+yn \iff ax - yn =1$ for some $y\in \mathbb{Z}$...'

Also, in the title of the corollary, it states :
$\{\overline{a},\,\,|\,\,\gcd(a,n)\}.$

I have three questions :
(i) Inverse of $a$ is stated to be : $\overline{x}$, so it should be true that $\overline{x}=\frac{1+(-y)n}a$.

(ii) The second line is even more confusing, as has $\overline{ax}=\overline{1}$ rather than $a\overline{x}=1$.

(iii) The title is also not understandable, as states: $\{\overline{a},\,\,|\,\,\gcd(a,n)\}.$ Cannot understand why took $\overline{a},$?

Answer 1

(i) $\bar x\in\Bbb Z/n\Bbb Z$ and $\frac{1+(-y)n}{a}\in\Bbb Q$, hence the equality makes no sense. Instead, the inverse is given by the implicit definition $\bar a\bar x=\bar x\bar a = \bar 1$.

(ii) I'd say the error is in the beginning as we are looking for the inverse of an element of $\Bbb Z/n\Bbb Z$, not for an element of $\Bbb Z$, so it should say "Thus ... $\bar x$ is the inverse of $\bar a$.", i.e., $\bar a$ is our element of $\Bbb Z/n\Bbb Z$ (and $a\in\Bbb Z$ a representative of it). Then of course $\bar a\bar x=\overline{ax}=\bar 1$ makes sense.

(iii) Indeed, $\{\,\bar a,\mid \gcd(a,n)=1\,\}$ does not parse with that comma.

Answer 2

Note that in this context — in the context of integers modulo $n$ — we have two related "things" for each integer $x$ (or whatever letter): the integer $x\in\mathbb{Z}$ itself, and its residue class $\overline{x}\in\mathbb{Z}/n\mathbb{Z}$. What may be confusing is that there's a lot of going back and forth between the two — but it's still important to always clearly understand what we're talking about.

(i) First of all, it's sloppy notation on the authors' part — it should be $\overline{a}$, not just "$a$". To answer your question: as you wrote it, $\overline{x}=\frac{1+(-y)n}a$ doesn't quite make sense because the left-hand side is in $\mathbb{Z}/n\mathbb{Z}$ but the right-hand side is in $\mathbb{Z}$. It is true, though, that $x=\frac{1+(-y)n}a$ here, as an equality in $\mathbb{Z}$. Writing something like this with bars, however, wouldn't make sense, because there's no such thing as division in $\mathbb{Z}/n\mathbb{Z}$.

(ii) That actually makes perfect sense. $a\in\mathbb{Z}$ and $x\in\mathbb{Z}$ are two integers, and we certainly can multiply them together to get a new integer $ax\in\mathbb{Z}$. Now think of it as a new single number (which it is!), and put a bar on it to form its residue class modulo $n$.

(iii) Since the statement of the corollary talks about "integers modulo $n$", it is about elements with bars on them, hence $\overline{a}$ in the title. The notation "$\{\overline{a}\mid\gcd(a,n)=1\}$" says that for each (usual) integer $a$ that is coprime with $n$ we're going to form its residue class $\overline{a}$ and take it into our set — remember that it must be a subset of "integers modulo $n$", i.e. of $\mathbb{Z}/n\mathbb{Z}$, not of the usual integers $\mathbb{Z}$.