- #1

fishturtle1

- 394

- 82

## 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: