# U(n) as an External Direct Product

• fishturtle1
In summary: I think i get it now, the two pairs of relatively prime numbers are not necessarily going to be relatively prime to each other. So in general there is no solution for ##x##. but in this case we can find an ##x## using the chinese remainder theorem, since ##s## and ##t## are relatively prime. so ##x \equiv b(\operatorname{mod} s)## and ##x \equiv a(\operatorname{mod} t)## will give us the solution for ##x##?Correct, in general there may not exist a solution for ##x##. However, since ##s## and ##t## are relatively prime, the Chinese Remainder Theorem guarantees a solution. You can use the
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.

Last edited:
fishturtle1 said:
##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##?

andrewkirk said:
I don't understand this statement.

andrewkirk said:
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##.

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?

fishturtle1 said:
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##.

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

(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)##?

fishturtle1 said:
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.

Last edited:
fishturtle1 said:
(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)|\,.##

fresh_42 said:
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

fresh_42 said:

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
fishturtle1 said:
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.

## What is the definition of "U(n) as an External Direct Product"?

"U(n) as an External Direct Product" refers to a mathematical concept where a group U(n) is decomposed into a direct product of two groups, typically a cyclic group and a symmetric group. This decomposition allows for a more efficient way to study the properties of U(n) and its elements.

## What is the significance of studying U(n) as an External Direct Product?

Studying U(n) as an External Direct Product allows for a better understanding of the group's structure and properties. It also provides insights into the relationships between different groups and helps in solving complex mathematical problems.

## How is U(n) decomposed into a direct product?

U(n) is decomposed into a direct product by finding a suitable cyclic group and symmetric group that satisfy certain conditions. These conditions include the order of the groups and the index of the cyclic group in U(n).

## What are the applications of U(n) as an External Direct Product?

The concept of U(n) as an External Direct Product has applications in various areas of mathematics, including group theory, number theory, and algebraic geometry. It is also used in cryptography and coding theory for efficient error correction techniques.

## Are there any limitations or drawbacks to studying U(n) as an External Direct Product?

While studying U(n) as an External Direct Product can provide valuable insights, it may not always be applicable or useful for all situations. Additionally, the decomposition process can be complex and time-consuming, making it challenging to apply in certain scenarios.

• Calculus and Beyond Homework Help
Replies
5
Views
3K
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
6
Views
2K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
2
Views
496
• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
12
Views
1K
• Linear and Abstract Algebra
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
0
Views
573
• Calculus and Beyond Homework Help
Replies
16
Views
1K