# [SOLVED]Elementary Group Theory

#### Poirot

##### Banned
Let G be a group, |G|=n and m an integer such that gcd(m,n)=1.

(i) show that $x^m=y^m$ implies $x=y$

(ii)Hence show that for all g in G there is a unique x such that $x^m=g$

(i) there exist a, b such that am+bn=1 so that $m^{-1}=a (mod n)$.

Hence $x^m=y^m ->x=y$ ok?

(ii) (i) shows uniqueness. Not sure about existence. Cheers.

#### caffeinemachine

##### Well-known member
MHB Math Scholar
Let G be a group, |G|=n and m an integer such that gcd(m,n)=1.

(i) show that $x^m=y^m$ implies $x=y$

(ii)Hence show that for all g in G there is a unique x such that $x^m=g$

(i) there exist a, b such that am+bn=1 so that $m^{-1}=a (mod n)$.

Hence $x^m=y^m ->x=y$ ok?

(ii) (i) shows uniqueness. Not sure about existence. Cheers.
To show existence in (ii) define $f:G\rightarrow G$ as $f(g)=g^m$. We know that $f$ is an injective map. Since $G$ is finite, $f$ is also surjective. Hence...

#### Poirot

##### Banned
Very clever. I know in part (i) that am+bn=1 ->$m^{-1}=a$ mod(n), but I've attempted to derive this and have failed.

#### caffeinemachine

##### Well-known member
MHB Math Scholar
Very clever. I know in part (i) that am+bn=1 ->$m^{-1}=a$ mod(n), but I've attempted to derive this and have failed.
Are you asking why is it true that $\gcd (m,n)=1 \Rightarrow \exists a,b\in \mathbb{Z}$ such that $am+bn=1$??

#### Poirot

##### Banned
Are you asking why is it true that $\gcd (m,n)=1 \Rightarrow \exists a,b\in \mathbb{Z}$ such that $am+bn=1$??
Actually forget about it. am = 1 (mod n) because am - 1 is a multiple of n (which is what I was asking)

#### caffeinemachine

##### Well-known member
MHB Math Scholar
Actually forget about it. am = 1 (mod n) because am - 1 is a multiple of n (which is what I was asking)
Okay.

#### Deveno

##### Well-known member
MHB Math Scholar
you can also write it this way:

since $am+bn = 1$

$x^m = y^m \implies (x^m)^a = (y^m)^a$

$\implies x^{am} = y^{am} \implies (x^{am})(e^b) = (y^{am})(e^b)$

$\implies (x^{am})((x^n)^b) = (y^{am})((y^n)^b)$

$\implies (x^{am})(x^{bn}) = (y^{am})(y^{bn})$

$\implies x^{am+bn} = y^{am+bn} \implies x = y$

as an example of how this works, suppose $G = \{e,a,a^2\}$

and we have $x^2 = y^2$.

if $x = e$, then $y = e$ since $G$ has no elements of order 2.

if $x = a$, then $e^2 = e$, and $(a^2)^2 = a$, so $y$ must be $a$.

if $x = a^2$, then $e^2 = e$ and $(a)^2 = a^2$ but $x^2 = a$, so $y = a^2$.

what are the a and b in this case?

clearly 1 = (-1)2 + (1)3

so $x = x^{am+bn} = (x^2)^{-1}(x^3)^1 = x^{-2}$

the map $G \to G$ given by $g \to g^2$ is:

$e \to e$
$a \to a^2$
$a^2 \to a$ <--clearly bijective (in this case it's just the inversion map).

those "fun facts" we learned about factoring integers into primes in grade school, turn out to be useful after all.