2

Reading a book about Group Theory I came across the following statement and its proof:

Given $(\mathbb{Z}_n,+)$ (meaning the group of integers modulo $n$ with binary operation of addition) prove that for every $0\leq a\leq n-1: \langle a\rangle=\langle\gcd(a,n)\rangle$.

The way $\langle a\rangle\leq\langle\gcd(a,n)\rangle$ is clear to me.

The way $\langle a\rangle\geq\langle\gcd(a,n)\rangle$ isn't. If the latter one is correct then the following exists: assume $n=8$, $a=6$ then $\gcd(8,6)=2$ then there exist an integer $x$ such that $6x=2$.

What am I missing?

egreg
  • 238,574
Yaron Scherf
  • 313
  • 1
    I am the langle rangle fairy, here to tell you that \langle \rangle looks much better than < > as angle brackets. – Arthur Oct 30 '18 at 11:10

1 Answers1

1

What you're missing is that you're working $\mod{n}$.

Using your example of $n=8, a=6$, we have $6\cdot 3 \equiv 2 \pmod{8}$. That is, in $\mathbb{Z}_8$, $6\cdot 3 = 2$.

paw88789
  • 40,402