Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It is easy to verify that the set $(\mathbb{Z}/n\mathbb{Z})^\times$ is closed under multiplication in the sense that $a, b ∈ (\mathbb{Z}/n\mathbb{Z})^\times$ implies $ab ∈ (\mathbb{Z}/n\mathbb{Z})^\times$, and is closed under inverses in the sense that $a ∈ (\mathbb{Z}/n\mathbb{Z})^\times$ implies $a^{-1} ∈ (\mathbb{Z}/n\mathbb{Z})^\times$.

The question is the following:

Firstly, are $a$ and $b$ referring to each equivalence class of integers modulo $n$?

Secondly, by $a^{-1}$, what is this referring to? If $a$ is the equivalence class, I cannot see (or I am not sure) how I can make inverse set.

share|improve this question
add comment

6 Answers

up vote 6 down vote accepted

To the first question, just quoting your intro, "$a,b\in(\mathbb{Z}/n\mathbb{Z})^{\times}$". So if $\mathbb{Z}/n\mathbb{Z}$ is a set of equivalence classes, then yes, $a$ and $b$ are equivalence classes.

To the second question, $a^{-1}$ is an equivalence class such that $aa^{-1}$ is the equivalence class of $1$. In general, there is no quick formula to find an element of $a^{-1}$ given $a$. Instead, since a representative $A$ of $a$ and $n$ are relatively prime, the Euclidean algorithm provides solutions to the equation $$AB + nt = 1$$ Then mod $n$, $AB\equiv 1$. So the Euclidean algorithm will lead you to a representative of $a^{-1}$.

Now, to back-peddle a little bit, actually there is a rather simple formula for a representative of $a^{-1}$, given a representative $A$ of $a$. Take $B=A^{\varphi(n)-1}$, where $\varphi$ is Euler's totient function. Then $AB=A^{\varphi(n)}\equiv1\mod{n}$. The problem with this "simple" formula is that it's not computationally efficient. For example, if $n=97$, the Euclidean algorithm quickly tells us that $2^{-1}=49$. But this formula would give us $2^{96}$, which is tiresome to compute even if we reduce at every multiplication.

share|improve this answer
add comment

The notation $a \in (\mathbb{Z} / n \mathbb{Z})^\times$ means the variable $a$ is being used to denote an element of $(\mathbb{Z} / n \mathbb{Z})^\times$.

If you are representing elements of $(\mathbb{Z} / n \mathbb{Z})^\times$ as equivalence classes, then $a$, being an element of $(\mathbb{Z} / n \mathbb{Z})^\times$, has a representation as an equivalence class.

The structure $(\mathbb{Z} / n \mathbb{Z})^\times$ is an abelian group. It has a group operation, an inverse, and a neutral element. As we are writing this group with multiplicative notation, we adopt the default notation ${}^{-1}$ for the inverse operation of the group.

As an aside, I think focusing on an object "being" an equivalence class really obscures the simplicity of what's going on. Equivalence classes are frequently just a technical set-theoretic trick.

One rather good notation for elements of the ring $\mathbb{Z} / n \mathbb{Z}$ is that elements are represented by integers. Not just integers in the range $\{ 0, 1, \cdots, n-1\}$, but any integer. The same element has many notations; for example, '3' and '10' are two separate notations for the same element of $\mathbb{Z} / 7 \mathbb{Z}$.

It may help to add a decoration to help keep track of when you are using '3' to denote an element of $\mathbb{Z}$ and when you are using it to denote an element of $\mathbb{Z} / 7 \mathbb{Z}$: common choices are $\overline{3}$ and $[3]$, or sometimes $[3]_7$.

If you are representing the elements of $\mathbb{Z} / n \mathbb{Z}$ as equivalence classes, then the element $[3]$ is notation for the element represented by the equivalence class of 3. Despite that fact, you usually shouldn't be thinking "$[3]$ is an equivalence class": you should be thinking "$[3]$ is the element of $\mathbb{Z} / n \mathbb{Z}$ that comes from the integer 3".

share|improve this answer
add comment

Well $2\cdot 3\equiv 1\; \text{mod}\ 5$, so $2$ and $3$ are multiplicative inverses $\text{ mod } 5$.

How to find the inverse of a number modulo a prime number was the topic of one of my previous answers. Modulo a composite number, inverses don't always exist.

See Calculating the Modular Multiplicative Inverse without all those strange looking symbols for the way to find the inverse of $322$ mod $701$. It turns out to be $455$

share|improve this answer
add comment

First: yes, $a$ and $b$ represent the equivalence classes modulo $n$.

Second: Well, $a^{-1}$ is not the inverse as a rational number. Rather, it is the unique equivalence class modulo $n$ (if it exists) such that $aa^{-1}$ is congruent to 1 modulo $n$. And for existence, this inverse exists if and only if $a$ is coprime to $n$.

share|improve this answer
add comment

Firstly, yes.

Secondly, by $a^{-1}$ we mean the unique equivalence class such that multiplication of (the equivalence class) $a$ with $a^{-1}$ gives (the equivalence class of) $1.$

For example in $(\mathbb Z/4\mathbb Z)^\times=\{1,3\}$ we have $1\cdot 1\equiv 1$ so $1^{-1}=1$ and $3\cdot 3=9\equiv 1$ so $3^{-1}=3.$

share|improve this answer
add comment

It is also standard to identify $(\mathbf Z/n \mathbf Z)$, which is typically defined algebraically as a set of equivalence classes, with the integers $\{0, \dots, n-1 \}$. One thing to note is that $(\mathbf Z/n \mathbf Z)$ is essentially finitary, so the representation as integers is sometimes useful (but less convenient algebraically)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.