MHB Is $\text{Aut}(\mathbb{Z}_p)$ isomorphic to $\mathbb{Z}_{p-1}$?

[mathmari]

Hey!

I want to show that $\text{Aut}(\mathbb{Z}_p)$ is isomorphic to $\mathbb{Z}_{p-1}$.

The group $\mathbb{Z}_p$ is cylcic and is generated by one element. The possible generators are $\{1,2,\dots , p-1\}$.

Each automorphism maps each of the elements of the set $\{1,2,\dots , p-1\}$ to one of the elements $\{1,2,\dots , p-1\}$. So, we have the function $f_m(x)=mx\pmod p, \ 1\leq m\leq p-1$, right?

To show that $\text{Aut}(\mathbb{Z}_p)$ is isomorphic to $\mathbb{Z}_{p-1}$ do we define the function $$h:\text{Aut}(\mathbb{Z}_p)\rightarrow \mathbb{Z}_{p-1} \text{ with } \\ f_m\mapsto (m-1)\pmod {p-1} , \ 1\leq m\leq p-1$$ ? (Wondering)

 

[Deveno]

Nope.

You have the functions $f_m$ correct, but you have the isomorphism wrong.

To see this suppose $p = 5$ and consider $m = 2$.

Then $f_2(x) = 2x$ (mod $5$).

Now $(f_2 \circ f_2)(x) = 2(2x) = 4x$ (mod $5$). So $f_2 \circ f_2 = f_4$.

Under your mapping we have $f_2 \circ f_2 = f_4 \mapsto [3]_4$.

However $f_2 \mapsto [1]_5$ so:

$h(f_2 \circ f_2) = h(f_4) = [3]_4 \neq [2]_4 = [1]_4 + [1]_4 = h(f_2) + h(f_2)$.

You may find it easier to do the reverse isomorphism:

$\phi: \Bbb Z_{p-1} \to \text{Aut}(Z_p)$.

(Hint: show $\text{Aut}(Z_p) \cong (\Bbb Z_p)^{\times}$).

One caveat: showing $(\Bbb Z_p)^{\times}$ is cyclic is a non-trivial task, as explicitly demonstrating a generator is known to be a "hard problem". All the proofs I know are "non-constructive".

 

[mathmari]

Nope.

You have the functions $f_m$ correct, but you have the isomorphism wrong.

To see this suppose $p = 5$ and consider $m = 2$.

Then $f_2(x) = 2x$ (mod $5$).

Now $(f_2 \circ f_2)(x) = 2(2x) = 4x$ (mod $5$). So $f_2 \circ f_2 = f_4$.

Under your mapping we have $f_2 \circ f_2 = f_4 \mapsto [3]_4$.

However $f_2 \mapsto [1]_5$ so:

$h(f_2 \circ f_2) = h(f_4) = [3]_4 \neq [2]_4 = [1]_4 + [1]_4 = h(f_2) + h(f_2)$.

Ah ok... (Thinking)

You may find it easier to do the reverse isomorphism:

$\phi: \Bbb Z_{p-1} \to \text{Aut}(Z_p)$.

Do we consider then the function $$h: \mathbb{Z}_{p-1}\rightarrow \text{Aut}(\mathbb{Z}_p) \text{ with } \\ (m-1)\pmod {p-1}\mapsto f_m , \ 1\leq m\leq p-1$$ ? (Wondering)

(Hint: show $\text{Aut}(Z_p) \cong (\Bbb Z_p)^{\times}$).

Why do we have to show that? (Wondering)

 

[I like Serena]

Do we consider then the function $$h: \mathbb{Z}_{p-1}\rightarrow \text{Aut}(\mathbb{Z}_p) \text{ with } \\ (m-1)\bmod {p-1}\mapsto f_m , \ 1\leq m\leq p-1$$ ? (Wondering)

Why do we have to show that? (Wondering)

I'm afraid not. (Shake)
Note that $f_m\circ f_n = f_{m\times n}$.
That is, the composition of a function with arguments $m$ and $n$ maps to a product $m\times n$, which matches $\mathbb Z_p^\times$ instead of $\mathbb Z_{p-1}$.
Fortunately, those groups are isomorphic. (Nerd)

 

[Deveno]

Why do we have to show that? (Wondering)

That is the isomorphism I like Serena refers to in his post.

As I mentioned before, it's non-trivial to show that $(\Bbb Z_p)^{\times}$ is cyclic (it's pretty clear it is a group, namely the Group of units of the ring $\Bbb Z_p$ (which is actually a field)).

For any *specific* prime $p$, one can do this by exhibiting a generator: for example $[3]_4$ is a generator of $(\Bbb Z_5)^{\times} = \{[1]_5,[2]_5,[3]_5,[4]_5\}$ (under the operation of multiplication modulo 5), since:

$[3]_5^2 = [9]_5 = [4]_5$ (so $[3]_5$ does not have order 2; as it is not the identity ($[1]_5$), it also does not have order 1)

$[3]_5^3 = [27]_5 = [2]_5$ (so $[3]_5$ does not have order 3)

$[3]_5^4 = [81]_5 = [1]_5$, so $[3]_5$ has order $4$, is thus a generator, and $(\Bbb Z_5)$ is cyclic (of order $4$).

So here is one possible isomorphism from $((\Bbb Z_5)^{\times},\ast) \to (\Bbb Z_4,+)$:

$[1]_5 \mapsto [0]_4$
$[3]_5 \mapsto [1]_4$
$[4]_5 \mapsto [2]_4$
$[2]_5 \mapsto [3]_4$

Essentially, we are mapping $[3^k]_5 \mapsto [k]_4$.

Note this is not just "subtracting one", it's a little trickier.

Unfortunately, it is a LOT harder to try to figure out what a generator might be for the group of units of $\Bbb Z_p$ for an arbitrary $p$. So some cleverness is required.

 

[mathmari]

I got stuck right now... Can we not show immediately that $\text{Aut}(\mathbb{Z}_p)$ is isomorphic to $\mathbb{Z}_{p-1}$ without using $\mathbb{Z}_p^{\times}$ ? (Wondering)

 

[Deveno]

Do you know what a "discrete log" is?

Unless you are familiar with this type of function, showing the isomorphism directly is hard to explain.

 

[I like Serena]

I think we can turn it around and pick:
$$h:\mathbb Z_{p-1} \to \text{Aut}(\mathbb{Z}_p)$$
That way we don't need a discrete log, but just a power.

It means we need to find $h$ such that:
$$h(m+n) = h(m) \circ h(n)$$

I would still recommend putting in an extra step through $\mathbb{Z}_p^{\times}$ to figure out which function we need.
That is:
$$\mathbb Z_{p-1} \overset{h_2}\longrightarrow\mathbb Z_{p}^\times \overset{h_1}\longrightarrow \text{Aut}(\mathbb Z_{p}) $$
with $h_1$ such that $h_1(m\times n) = h_1(m) \circ h_1(n)$ and with $h_2$ such that $h_2(m + n) = h_2(m) \times h_2(n)$.
Then $h = h_1 \circ h_2$ is the function we're looking for. (Thinking)

 

[Deveno]

I think we can turn it around and pick:
$$h:\mathbb Z_{p-1} \to \text{Aut}(\mathbb{Z}_p)$$
That way we don't need a discrete log, but just a power.

It means we need to find $h$ such that:
$$h(m+n) = h(m) \circ h(n)$$

I would still recommend putting in an extra step through $\mathbb{Z}_p^{\times}$ to figure out which function we need.
That is:
$$\mathbb Z_{p-1} \overset{h_2}\longrightarrow\mathbb Z_{p}^\times \overset{h_1}\longrightarrow \text{Aut}(\mathbb Z_{p}) $$
with $h_1$ such that $h_1(m\times n) = h_1(m) \circ h_1(n)$ and with $h_2$ such that $h_2(m + n) = h_2(m) \times h_2(n)$.
Then $h = h_1 \circ h_2$ is the function we're looking for. (Thinking)

See post #2. (Wink)

 

[mathmari]

We have that $(\Bbb Z_p)^{\times}$ is cyclic with generator, say $g$.

Could you give me some hints you we could prove that $(\Bbb Z_p)^{\times}$ is cyclic? (Wondering)

Then each element can be written in the form $g^i$ for some $i$.

$$\mathbb Z_{p-1} \overset{h_2}\longrightarrow\mathbb Z_{p}^\times \overset{h_1}\longrightarrow \text{Aut}(\mathbb Z_{p}) $$
with $h_1$ such that $h_1(m\times n) = h_1(m) \circ h_1(n)$ and with $h_2$ such that $h_2(m + n) = h_2(m) \times h_2(n)$.
Then $h = h_1 \circ h_2$ is the function we're looking for. (Thinking)

So can we define the following functions $$h_2: \mathbb Z_{p-1}\rightarrow Z_{p}^\times \\ m\mapsto g^m$$ and $$h_1: Z_{p}^\times\rightarrow \text{Aut}(\mathbb Z_{p}) \\ g^m\mapsto f_{g^m}$$ or not? (Wondering)

 

[mathmari]

So can we define the following functions $$h_2: \mathbb Z_{p-1}\rightarrow Z_{p}^\times \\ m\mapsto g^m$$ and $$h_1: Z_{p}^\times\rightarrow \text{Aut}(\mathbb Z_{p}) \\ g^m\mapsto f_{g^m}$$ or not? (Wondering)

Would we have to show that $h_1$ and $h_2$ are homomorphism? Would their composition be also an homomorphism? (Wondering)

 

[I like Serena]

We have that $(\Bbb Z_p)^{\times}$ is cyclic with generator, say $g$.

Could you give me some hints you we could prove that $(\Bbb Z_p)^{\times}$ is cyclic?

It says so here.
As Deveno already said, the proof is not trivial.
Perhaps it's in your course material? (Wondering)

Then each element can be written in the form $g^i$ for some $i$.

So can we define the following functions $$h_2: \mathbb Z_{p-1}\rightarrow Z_{p}^\times \\ m\mapsto g^m$$ and $$h_1: Z_{p}^\times\rightarrow \text{Aut}(\mathbb Z_{p}) \\ g^m\mapsto f_{g^m}$$ or not?

Yep. That's it!
Can you prove that it's an isomorphism? (Wondering)

Would we have to show that $h_1$ and $h_2$ are homomorphism? Would their composition be also an homomorphism?

Yes, we should show they are homomorphisms.
And we should show that the composition of 2 homomorphisms is a homomorphism as well. (Sweating)

 

[mathmari]

Can you prove that it's an isomorphism? (Wondering)
Yes, we should show they are homomorphisms.
And we should show that the composition of 2 homomorphisms is a homomorphism as well. (Sweating)

We have that $h_2$ is 1-1 because each element of $\mathbb Z_{p-1}$ is mapped to an unique element of $Z_{p}^\times$.
Furthermore, $h_2$ is onto because for each element of $Z_{p}^\times$ there is an element of $\mathbb Z_{p-1}$ that is mapped to that. Similar for $h_1$:
We have that $h_1$ is 1-1 because each element of $Z_{p}^\times$ is mapped to an unique element of $\text{Aut}(\mathbb Z_{p})$.
Furthermore, $h_1$ is onto because for each element of $ \text{Aut}(\mathbb Z_{p})$ there is an element of $Z_{p}^\times$ that is mapped to that. Is this correct? (Wondering) How can we show that their composition is also 1-1 and onto? (Wondering)

We have the following:
$$h_2(m+n)=g^{m+n}=g^mg^n=h_2(m)h_2(n)$$
So $h_2$ is an homomorphism.

$$h_1(g^m\cdot g^n)=h_1(g^{m+n})=f_{g^{m+n}}$$

How could we continue? (Wondering)

 

[I like Serena]

Is this correct? (Wondering)

Yep. (Nod)

How can we show that their composition is also 1-1 and onto? (Wondering)

Each element in $\text{Aut}(\mathbb Z_p)$ has exactly 1 original under $h_1$ in $(\mathbb Z_p)^\times$ and in turn that original has again exactly 1 original under $h_2$ in $\mathbb Z_{p-1}$.
Therefore each element in $\text{Aut}(\mathbb Z_p)$ has exactly 1 original under the composition $h$ in $\mathbb Z_{p-1}$.
Thus $h$ is bijective. (Thinking)

More generally, the composition of 2 bijections is a bijection. (Nerd)

$$h_1(g^m\cdot g^n)=h_1(g^{m+n})=f_{g^{m+n}}$$

How could we continue? (Wondering)

Let's simplify it a bit.
For any $a,b \in (\mathbb Z_p)^\times$ and any $x \in \mathbb Z_p$ we have:
$$h_1(a\times b)(x)=f_{a \times b}(x) = (ab)x = a(bx) = f_a(f_b(x)) = (h_1(a) \circ h_1(b))(x)$$
Therefore:
$$h_1(a\times b) = h_1(a) \circ h_1(b)$$That leaves proving that the composition of 2 homomorphisms is a homomorphism. (Thinking)

 

[mathmari]

Each element in $\text{Aut}(\mathbb Z_p)$ has exactly 1 original under $h_1$ in $(\mathbb Z_p)^\times$ and in turn that original has again exactly 1 original under $h_2$ in $\mathbb Z_{p-1}$.
Therefore each element in $\text{Aut}(\mathbb Z_p)$ has exactly 1 original under the composition $h$ in $\mathbb Z_{p-1}$.
Thus $h$ is bijective. (Thinking)

More generally, the composition of 2 bijections is a bijection. (Nerd)

Let's simplify it a bit.
For any $a,b \in (\mathbb Z_p)^\times$ and any $x \in \mathbb Z_p$ we have:
$$h_1(a\times b)(x)=f_{a \times b}(x) = (ab)x = a(bx) = f_a(f_b(x)) = (h_1(a) \circ h_1(b))(x)$$
Therefore:
$$h_1(a\times b) = h_1(a) \circ h_1(b)$$That leaves proving that the composition of 2 homomorphisms is a homomorphism. (Thinking)

Ah ok... (Thinking)

I think we can turn it around and pick:
$$h:\mathbb Z_{p-1} \to \text{Aut}(\mathbb{Z}_p)$$
That way we don't need a discrete log, but just a power.

When we pick $h:\mathbb Z_{p-1} \to \text{Aut}(\mathbb{Z}_p)$, could we show that the two groups are isomorphic to each other immediately? (Wondering)

Or is the composition necessary? (Wondering)

 

[I like Serena]

When we pick $h:\mathbb Z_{p-1} \to \text{Aut}(\mathbb{Z}_p)$, could we show that the two groups are isomorphic to each other immediately? (Wondering)

Or is the composition necessary? (Wondering)

Only if we would have a proposition to do it with and I don't think we do.
As it is, we need the non-trivial proposition that $\mathbb Z_{p-1} \simeq \mathbb Z_p^\times$, while $\mathbb Z_p^\times \simeq \text{Aut}(\mathbb Z_p)$ is pretty straight forward.
So we could define the isomorphism directly, but we can't prove that it's an isomorphism directly. (Thinking)