U(n) as an External Direct Product

[fishturtle1]

Homework Statement

EDIT: $U(n)$ is the set of relatively prime numbers less than $n$ and $U_k(n) = \lbrace x \epsilon U(n) : x \equiv 1 (\operatorname{mod} k) \rbrace$.

I'm trying to finish the proof of this statement(s): Suppose $s$ and $t$ are relatively prime. Then $U(st) \approx U(s) \oplus U(t)$.

Moreover, $U_{s}(st)$ is isomorphic to $U(t)$ and $U_t(st)$ is isomoprhic to $U(s)$.

Proof: An ismorphism from $U(st)$ to $U(s) \oplus U(t)$ is $x \rightarrow (x \operatorname{mod} s, x \operatorname{mod} t)$; an ismorphism from $U_s(st)$ to $U(t)$ is $x \rightarrow x \operatorname{mod} t$; an isomorphism from $U_t(st)$ to $U(s)$ is $x \rightarrow x \operatorname{mod} s$. We leave the verification that these makings are isomorphism's to the reader. (See ex. 9, 17, 19 in Chapter 0).

Homework Equations

Exercises from chapter 0:

9) Let $n$ be a fixed positive integer greater than 1. If $a \operatorname{mod} n = a'$ and $b \operatorname{mod} n = b'$, prove that $(a+ b) \operatorname{mod} n = (a' + b') \operatorname{mod} n$ and $(ab) \operatorname{mod} n = (a'b') \operatorname{mod} n$.

17) Let $a, b, s, t$ be integers. If $a \operatorname{mod} st = b \operatorname{mod} st$, show that $a \operatorname{mod} s = b \operatorname{mod} s$ and $a \operatorname{mod} t = b \operatorname{mod} t$.

17b) We also conclude the converse of 17) is true when $\gcd(a,b) = 1$.

19) Show that $\gcd(a, bc) = 1$ iff $\gcd(a,b) = 1$ and $\gcd(a, c) = 1$.

The Attempt at a Solution

First I want to show if $\gcd(s,t) = 1$ then $U(st) \approx U(s) \oplus U(t)$.

Proof: Define a function $\phi : U(st) \rightarrow U(s) \oplus U(t)$ as $\phi(x) = (x \operatorname{mod} s, x \operatorname{mod} t)$.

(one to one): Suppose $\phi(x) = \phi(y)$. Then $x \equiv y (\operatorname{mod} s)$ and $x \equiv y (\operatorname{mod} t)$. By 17b), $x \equiv y (\operatorname{mod} st)$.

(onto): Let $(a \operatorname{mod} s, b \operatorname{mod} t) \epsilon U(s) \oplus U(t)$. We want to find some $c \epsilon U(st)$ such that $\phi(c) = (a \operatorname{mod} s, b \operatorname{mod} t)$. This would mean $c = a + sk$ and $c = b + tl$ for some integers $k, l$.

(operation preserving): Let $x, y \epsilon U(st)$. Observe, $\phi(x) \phi(y) = (x \operatorname{mod} s, x \operatorname{mod} t)(y \operatorname{mod} s, y \operatorname{mod} t) = (xy \operatorname{mod} s, xy \operatorname{mod} t) = \phi(xy)$.

My question is how to proceed on the onto part?

edit2: for the second part we want to show $U_s(st) \approx U(t)$.

Proof: Define a function $\phi: U_s(st) \rightarrow U(t)$ as $\phi(x) \equiv x (\operatorname{mod} t)$.
Let $x, y \epsilon U_s(st)$.
(one to one): Suppose $\phi(x) = \phi(y)$. Then $x \equiv y (\operatorname{mod} t)$. Since $1 \equiv 1 (\operatorname{mod} s$ and $\gcd(s,t) = 1$, we have $x\cdot 1 \equiv y\cdot 1(\operatorname{mod} st)$.

(onto): Let $z \epsilon U(t)$. We need an $l$ such that $l \equiv 1(\operatorname{mod} s)$ and $l \equiv z(\operatorname{mod} t)$. This means $l = 1 + sm = z + tn$ for some integers $m,n$...

(operation preserving): $\phi(x)\phi(y) \equiv xy (\operatorname{mod} t) \equiv \phi(xy)$.

On this one I'm also not sure how to do the onto part.

 

[andrewkirk]

$U(n)$ is the set of relatively prime numbers less than $n$

I don't understand this statement. For most $n$ there will be multiple sets of relatively prime numbers less than them. For instance for $n=10$ the relatively prime sets include:

{2,3}, {2,3,5},{2,9,5},{7,4,9},{2,3,5,7}, {2, 5, 7, 9}

More specification is needed in order for $U(n)$ to denote a unique object that depends only on $n$. Do you perhaps mean that $U(n)$ is the set of numbers less than $n$ that are relatively prime to $n$?

 

[fresh_42]

I don't understand this statement.

I read it as $U(n)=\mathbb{Z}_n^*$.

 

[fishturtle1]

I don't understand this statement. For most $n$ there will be multiple sets of relatively prime numbers less than them. For instance for $n=10$ the relatively prime sets include:

{2,3}, {2,3,5},{2,9,5},{7,4,9},{2,3,5,7}, {2, 5, 7, 9}

More specification is needed in order for $U(n)$ to denote a unique object that depends only on $n$. Do you perhaps mean that $U(n)$ is the set of numbers less than $n$ that are relatively prime to $n$?

Sorry, yes thats' what I meant, This is the definition from the book: for each $n>1$ , we define $U(n)$ to be the set of all positive integers less than $n$ and relatively prime to $n$. Then $U(n)$ is a group under multiplication modulo $n$.

 

[fishturtle1]

For the first proof to show onto:

We have $x \equiv a (\operatorname{mod} s)$ and $x \equiv b (\operatorname{mod} t)$ where $\gcd(s, t) = 1$. So $x = a + sk$ for some integer $k$. Substituting we have $a + sk \equiv b (\operatorname{mod} t)$ so $k \equiv s^{-1}(b-a) \operatorname{mod} t$, so $k = s^{-1}(b-a) + t\cdot l$ for some integer $l$. Substituting back into $x$ gives $x = a + s(s^{-1}(b-a) + t\cdot l) = a + (b-a) + stl = b + stl$... so $x \equiv b (\operatorname{mod} st)$? what am i doing wrong, please?

 

[fresh_42]

For the first proof to show onto:

We have $x \equiv a (\operatorname{mod} s)$ and $x \equiv b (\operatorname{mod} t)$ where $\gcd(s, t) = 1$. So $x = a + sk$ for some integer $k$. Substituting we have $a + sk \equiv b (\operatorname{mod} t)$ so $k \equiv s^{-1}(b-a) \operatorname{mod} t$, so $k = s^{-1}(b-a) + t\cdot l$ for some integer $l$. Substituting back into $x$ gives $x = a + s(s^{-1}(b-a) + t\cdot l) = a + (b-a) + stl = b + stl$... so $x \equiv b (\operatorname{mod} st)$? what am i doing wrong, please?

You have $x \equiv a (\operatorname{mod} s)$ and $y \equiv b (\operatorname{mod} t)$ with $(x,s)=(y,t)=1$.

 

[fishturtle1]

You have $x \equiv a (\operatorname{mod} s)$ and $y \equiv b (\operatorname{mod} t)$ with $(x,s)=(y,t)=1$.

Thanks for the reply, I'm sorry if your hint is going completely over my head...

(onto): Let $(a (\operatorname{mod} s), b (\operatorname{mod} t))$ be an element of $U(s) \oplus U(t)$. We need an $x$ in $U(st)$ such that $\phi(x) = (x (\operatorname{mod} s), x (\operatorname{mod} t)) = (a (\operatorname{mod} s), b (\operatorname{mod} t))$, i.e., $x \equiv a (\operatorname{mod} s)$ and $x \equiv b (\operatorname{mod} t)$. Since $a$ is in $U(s)$ and $b$ is in $U(t)$, we have $(a, s) = 1$ and $(b, t) = 1$. Equivalently, $(x, s) = 1$ and $(x, t) = 1$. Edit: So $(x, st) = 1$ which implies $x$ would be an element of $U(st)$.. but i haven't shown an $x$ exists.

Why do we have $y \equiv b (\operatorname{mod} t)$ in post #4, instead of $x \equiv b (\operatorname{mod} t)$?

 

[fresh_42]

Why do we have $y \equiv b (\operatorname{mod} t)$ in post #4, instead of $x \equiv b (\operatorname{mod} t)$?

You have to pick an arbitrary element from $U(s)\oplus U(t)$. That is a pair $(x,y)$ with $(x,s)=1$ and $(y,t)=1$. You can as well write $x=a$ and $y=b$, but they are not necessarily the same. For this element you have to find an element $c\in U(st)$, that is $(c,st)=1$ with $c\equiv x \operatorname{mod}s$ and $c\equiv y \operatorname{mod}t$.

If you start with $x=y$ what is left to show? An arbitrary element of $U(s) \oplus U(t)$ looks like $(x,y)$.

I was probably confused by your notation $(a \operatorname{mod}s,b \operatorname{mod}t)$ plus it was late here, which is why I haven't had an idea I was sure of it will work.

The easiest way I know of would be counting elements. You already have an embedding $U(st) \hookrightarrow U(s) \oplus U(t)$. If you can show that they have equally many elements you are done. Of course this implies to use the multiplicativity of a certain function, so the real question will remain: why is it multiplicative? However, this is in your list of exercises above.

 

[fresh_42]

For your second question:

(one to one): Suppose $\phi(x) = \phi(y)$. Then $x \equiv y (\operatorname{mod} t).$

So far, so good. But now I'm lost. What do you mean?

Since $1 \equiv 1 (\operatorname{mod} s$ and $\gcd(s,t) = 1$, we have $x\cdot 1 \equiv y\cdot 1(\operatorname{mod} st).$

We have $x\equiv y \,(t)$ by construction, resp. assumption $\phi(x) = \phi(y)$. This leads to $x\stackrel{(*)}{\equiv} y\,(st)$ by $(s,t)=1$ (why?). Since $x,y \in U_s(st)$ we also know $x,y \equiv 1\, (s)\,.$

I think you need a reference for $(*)$ or a proof.

As for surjectivity: I think the element name $l$ isn't necessary here, as we do not change it by $\phi$. But I couldn't follow you anyway. We have an element $z\in U(t)$, that is $(z,t)=1$ or $1=pz+qt$ by Bézout's Lemma. We need to show: $z \equiv 1\, (s)$ and $(z,st)=1$. Since the former implies the latter, we only need to show $z \equiv 1\, (s)\,$

That means, from $1=Az+Bt$ and $1=Cs+Dt$ we must deduce $s\,|\,(z-1)$.
Alternatively, we can again use a counting argument, that is, we have to count $|U_s(st)|\,.$

 

[fishturtle1]

You have to pick an arbitrary element from $U(s)\oplus U(t)$. That is a pair $(x,y)$ with $(x,s)=1$ and $(y,t)=1$. You can as well write $x=a$ and $y=b$, but they are not necessarily the same. For this element you have to find an element $c\in U(st)$, that is $(c,st)=1$ with $c\equiv x \operatorname{mod}s$ and $c\equiv y \operatorname{mod}t$.

If you start with $x=y$ what is left to show? An arbitrary element of $U(s) \oplus U(t)$ looks like $(x,y)$.

I was probably confused by your notation $(a \operatorname{mod}s,b \operatorname{mod}t)$ plus it was late here, which is why I haven't had an idea I was sure of it will work.

The easiest way I know of would be counting elements. You already have an embedding $U(st) \hookrightarrow U(s) \oplus U(t)$. If you can show that they have equally many elements you are done. Of course this implies to use the multiplicativity of a certain function, so the real question will remain: why is it multiplicative? However, this is in your list of exercises above.

Let $\psi$ denote the Euler phi function. We can write $s$ and $t$ in their prime factorizations as $s = p_1^{a_1}p_2^{a_2}...p_n^{a_n}$ and $t = q_1^{b_1}q_2^{b_2}...q_m^{b_m}$ for some integers $n$ and $m$. Then $\psi(s)\psi(t) = \prod_{i=1}^{n} \frac{p_i - 1}{p_i} p_i^{a_i} \cdot \prod_{j=1}^{m} \frac{q_j - 1}{q_j} q_j^{b_j} = \psi(st)$ since $\gcd(s,t) = 1$. This means the $\vert U(st) \vert = \vert U(s) \vert \cdot \vert U(t) \vert = \vert U(s) \oplus U(t) \vert$. Since we've shown one to oneness, it follows $\phi$ is bijective.

I don't think i proved Euler phi function is multiplicative, i think i just restated what I wanted to prove... what do you think?
Also I think i could use 19) to show Euler phi function is multiplicative.. still thinking on that

 

[fishturtle1]

For your second question:

So far, so good. But now I'm lost. What do you mean?

We have $x\equiv y \,(t)$ by construction, resp. assumption $\phi(x) = \phi(y)$. This leads to $x\stackrel{(*)}{\equiv} y\,(st)$ by $(s,t)=1$ (why?). Since $x,y \in U_s(st)$ we also know $x,y \equiv 1\, (s)\,.$

I think you need a reference for $(*)$ or a proof.

We're showing $\phi: U_s(st) \rightarrow U(t)$ defined as $\phi(x) = x (\operatorname{mod} t)$ is one to one. Let $x,y$ be elements in $U_s(st)$. Suppose $\phi(x) = \phi(y)$. Then $x \equiv y (\operatorname{mod} t)$. We also have $x \equiv 1 \equiv y (\operatorname{mod} s$. So $x = y + tk$ and $x = y + sl$ for some integers $k$ and $l$. This implies $tk = sl$. Since $\gcd(s,t) = 1$, we have $s \vert k$. So $tk = tsl'$ for some integer $l'$. By substitution, $x = y + tsl'$ which can be rewritten as $x \equiv y (\operatorname{mod} st)$.

still doing the onto part.. will post when I have something.. Thank you for your responses

 

[fresh_42]

I don't think i proved Euler phi function is multiplicative, i think i just restated what I wanted to prove... what do you think?
Also I think i could use 19) to show Euler phi function is multiplicative.. still thinking on that

Just a little remark: Euler's phi-function is called this way, because we usually write it as $\varphi(n)$, not $\psi(n)$.

Yes, these are all equivalent. $\varphi(st)=\varphi(s)\varphi(t)$ is the same as $|U(st)|=|U(s)|\cdot |U(t)|\,.$ So if one holds, then necessarily the other one, too. You have proven the left one by counting the elements, so the right one follows. I would had mentioned that $\gcd(s,t)=1$ means that all $p_i\neq q_j$ and thus there will be no double counting. Ex. 19 is in principle also this statement. If $a$ is coprime to $(st)$ with $b=s$ and $c=t$, i.e. counted by $\varphi(st)$, then it's also counted in $\varphi(s)$ and $\varphi(t)$ and vice versa.